算法介绍
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧
1.算法步骤
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复第二步，直到所有元素均排序完毕。
2.动图演示
3.例子
4.代码实现
Python 代码实现
def selection_sort(our_list): n = len(our_list) for i in range(n-1): mark = i for j in range(i+1,n): # 如果有比当前ourlist[mark]还小的值，则更新mark的值，让新的最小值与后续元素继续比较 if our_list[j] < our_list[mark]: mark = j # 找到最小元素的下标值，进行交换，如果ourlist[i]已经是最小值 # 即nmark值在内循环中没改变过，则不需要交换元素 if mark != i: our_list[i],our_list[mark] = our_list[mark],our_list[i] return our_list
C++ 代码实现
void Selection_sort(int a[], int n) { int min = a[0]; for (int i = 0; i < n - 1; i++) { int mark = i;//记录最小值的位置 for (int j = i + 1; j < n; j++) { if (a[j] < min) { mark = j;//更新最小值的位置 min = a[mark];//更新最小值 } } if (mark != i) { swap(a[mark], a[i]);//交换，使得最小值放在i的位置 } } }
JavaScript 代码实现
function selectionSort(arr) { var len = arr.length; var minIndex, temp; for (var i = 0; i < len - 1; i++) { minIndex = i; for (var j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) { // 寻找最小的数 minIndex = j; // 将最小数的索引保存 } } temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } return arr; }
Go 代码实现
func selectionSort(arr []int) []int { length := len(arr) for i := 0; i < length-1; i++ { min := i for j := i + 1; j < length; j++ { if arr[min] > arr[j] { min = j } } arr[i], arr[min] = arr[min], arr[i] } return arr }
Java 代码实现
public class SelectionSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); // 总共要经过 N-1 轮比较 for (int i = 0; i < arr.length - 1; i++) { int min = i; // 每轮需要比较的次数 N-i for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[min]) { // 记录目前能找到的最小值元素的下标 min = j; } } // 将找到的最小值和i位置所在的值进行交换 if (i != min) { int tmp = arr[i]; arr[i] = arr[min]; arr[min] = tmp; } } return arr; } }
PHP 代码实现
function selectionSort($arr) { $len = count($arr); for ($i = 0; $i < $len - 1; $i++) { $minIndex = $i; for ($j = $i + 1; $j < $len; $j++) { if ($arr[$j] < $arr[$minIndex]) { $minIndex = $j; } } $temp = $arr[$i]; $arr[$i] = $arr[$minIndex]; $arr[$minIndex] = $temp; } return $arr; }
C# 代码实现
static void selection_sort<T>(T[] arr) where T : System.IComparable<T>{//整數或浮點數皆可使用 int i, j, min, len = arr.Length; T temp; for (i = 0; i < len - 1; i++) { min = i; for (j = i + 1; j < len; j++) if (arr[min].CompareTo(arr[j]) > 0) min = j; temp = arr[min]; arr[min] = arr[i]; arr[i] = temp; } }
SWift 代码实现
import Foundation /// 选择排序 /// /// - Parameter list: 需要排序的数组 func selectionSort(_ list: inout [Int]) -> Void { for j in 0..<list.count - 1 { var minIndex = j for i in j..<list.count { if list[minIndex] > list[i] { minIndex = i } } list.swapAt(j, minIndex) } }
部分摘自https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/2.selectionSort.md
5.总结与优化
优化
同时找出最小值与最大值放在数列两侧，两边逐渐逼近，循环次数会减少一些
优化代码
def selectsort(arr): n = len(arr) for i in range(n//2):# 两边同时找，只需要一半的循环 min_mark = i # 最小值标记 max_mark = n-i-1 # 最大值标记 for j in range(i+1,n-i): if arr[j] < arr[min_mark]: min_mark = j # 存在更小的，更新最小值标记 if min_mark != i: arr[i],arr[min_mark] = arr[min_mark],arr[i] # 交换 for j in range(n-i-2,i,-1):# 从后往前遍历 if arr[j] > arr[max_mark]: max_mark = j # 存在更大的，更新最大值标记 if max_mark != (n-i-1): arr[n-i-1],arr[max_mark] = arr[max_mark],arr[n-i-1] # 交换 return arr
总结
选择排序是种不稳定的排序，虽然代码有优化，但平均时间复杂度始终为 O(n²) ,有兴趣的可以了解下堆排序（需要有树的基础），时间复杂度可以优化至O(nlog2n)
每日一句
Actions speak louder than words. (行动比语言更响亮）
