引言

上篇文章中我們分析了冒泡排序，我們知道了冒泡排序可能需要N次交換和N次比較。
N次比較在所難免，但N次交換是必須的么？
今天我們介紹的選擇排序方法只需要一次交換。

思路

思路也很簡單：每趟從待排序的序列中選擇最小的元素，放到已排序序列末尾；

這里通過交換實現原地排序。

我們對該序列進行排序：

是不是和冒泡排序很相似，左邊橙色部分是已排序序列，右邊是待排序序列，且右邊必不小于左邊。
并且，可以看到：2、3、7趟并沒有發生交換。

代碼

/*** 每趟排序從i右邊找到最小的元素，和i交換(選擇)* @param a* @param <E>*/
public static <E extends Comparable<? super E>> void selectionSort(E[] a) {for (int i = 0; i < a.length; i++) {int minIndex = i;for (int j = i + 1; j < a.length ; j++) {//找到右邊最小元素索引if (a[j].compareTo(a[minIndex]) < 0) {minIndex = j;}}swap(a,i,minIndex);//System.out.println("i=" + i + Arrays.toString(a));}
}private static <E> void swap(E[] array, int i, int j) {if (i == j) return;E tmp = array[i];array[i] = array[j];array[j] = tmp;
}

復雜度和穩定性

• 時間復雜度

共N次迭代，在第k次迭代中，找到最小元素$O(N?k)$
因此總體復雜度為 $O(N^2)$

• 穩定性

簡單選擇排序由于選出最小值后需要交換位置,位置一變就會變得不穩定。
例如序列5 8 5 2 9， 我們知道第一遍，第一個元素5會和2交換，那么原序列中2個5的相對前后順序就被破壞了，所以選擇排序不是一個穩定的排序算法