基本思想
這是思路最簡單的排序算法。
- 找到數(shù)組中最小的那個元素匪蟀；
- 將它和數(shù)組的第一個元素交換位置（如果第一個元素就是最小元素椎麦，那么它就和自己交換）；
- 在剩下的元素中找出最小的元素材彪，將它與剩余元素中的第一個元素交換（即數(shù)組第二個元素）观挎；
- 重復執(zhí)行 3 ，直到將整個數(shù)組排序段化。
運行軌跡
代碼實現(xiàn)
根據(jù)排序算法類的模板實現(xiàn)選擇排序（提醒：點藍字查看詳情）
/**
* 選擇排序
*
* @author TinyDolphin
* 2017/11/1 14:20.
*/
public class Selection {
/**
* 排序?qū)崿F(xiàn)
* @param arr 待排序數(shù)組
*/
public static void sort(Comparable[] arr) {
int length = arr.length;//數(shù)組長度
for (int indexI = 0; indexI < length; indexI++) {
// 將arr[indexI]和arr[indexI+1...length]中最小的元素交換
int min = indexI; // 最小元素的索引
for (int indexJ = indexI + 1; indexJ < length; indexJ++) {
if (less(arr[indexJ], arr[min])) {
min = indexJ;
}
}
exch(arr, indexI, min);
}
}
/**
* 比較兩個元素的大小
* @param comparableA 待比較元素A
* @param comparableB 待比較元素B
* @return 若 A < B,返回 true,否則返回 false
*/
private static boolean less(Comparable comparableA, Comparable comparableB) {
return comparableA.compareTo(comparableB) < 0;
}
/**
* 將兩個元素交換位置
* @param arr 待交換元素所在的數(shù)組
* @param indexI 第一個元素索引
* @param indexJ 第二個元素索引
*/
private static void exch(Comparable[] arr, int indexI, int indexJ) {
Comparable temp = arr[indexI];
arr[indexI] = arr[indexJ];
arr[indexJ] = temp;
}
/**
* 打印數(shù)組的內(nèi)容
* @param arr 待打印的數(shù)組
*/
private static void show(Comparable[] arr) {
for (int index = 0; index < arr.length; index++) {
System.out.print(arr[index] + " ");
}
System.out.println();
}
/**
* 判斷數(shù)組是否有序
* @param arr 待判斷數(shù)組
* @return 若數(shù)組有序嘁捷，返回 true，否則返回 false
*/
public static boolean isSort(Comparable[] arr) {
for (int index = 1; index < arr.length; index++) {
if (less(arr[index], arr[index - 1])) {
return false;
}
}
return true;
}
public static void main(String[] args) {
Integer[] arr = new Integer[]{14, 23, 21, 17, 20, 49, 24, 77, 54, 47, 31};
sort(arr);
assert isSort(arr);
show(arr); //14 17 20 21 23 24 31 47 49 54 77
}
}
性能分析
交換元素的代碼寫在內(nèi)循環(huán)之外显熏，每次交換都能排定一個元素雄嚣，因此交換的總次數(shù)是 N。所以算法的時間效率取決于比較的次數(shù)喘蟆。
查看代碼可以精準得到缓升，0 到 N-1 的任意 indexI 都會進行一次交換和 N-1-indexI 次比較，所以對于長度為 N 的數(shù)組蕴轨，選擇排序需要大約 N2/2 次比較和 N 次交換港谊。
選擇排序的特點
①、運行時間和輸入無關橙弱。為了找出最小的元素而掃描一遍數(shù)組并不能為下一遍掃描提供什么信息歧寺；
②、數(shù)據(jù)移動是最小的膘螟。每次交換都會改變兩個數(shù)組元素的值成福，因此選擇排序用了 N 次交換——交換次數(shù)和數(shù)組的大小是線性關系碾局。（其他大部分排序算法的增長數(shù)量級都是線性對數(shù)或是平方級別的）
優(yōu)化方案
試想荆残，上述方案中的主要思路是，每次遍歷剩余元素净当，找出其中最小值内斯，只排定最小值蕴潦。（原有方案）
我們這樣，每次遍歷剩余元素的時候俘闯，找出其中最小值和最大值潭苞，并排定最小值和最大值。（優(yōu)化方案）
這樣遍歷的次數(shù)會減少一半真朗。時間復雜度是O（N/2 * N /2）此疹，還是平方級別的。但是運行時間有了相應的減少遮婶。
優(yōu)化方案之后的運行軌跡
優(yōu)化代碼
public static void sortPlus(Comparable[] arr) {
for (int left = 0, right = arr.length - 1; left < right; left++, right--) {
int min = left; // 記錄最小值
int max = right; // 記錄最大值
for (int index = left; index <= right; index++) {
if (less(arr[index], arr[min])) {
min = index;
}
if (less(arr[max], arr[index])) {
max = index;
}
}
// 將最小值交換到 left 的位置
exch(arr, left, min);
//此處是先排最小值的位置蝗碎，所以得考慮最大值（arr[max]）在最小位置（left）的情況。
if (left == max) {
max = min;
}
exch(arr, right, max);
}
}
測試代碼
public static void main(String[] args) {
int length = 10000; // 上萬級別
Integer[] arr = new Integer[length];
for (int index = 0; index < length; index++) {
arr[index] = new Random().nextInt(length) + 1;
}
Integer[] arr2 = new Integer[length];
System.arraycopy(arr, 0, arr2, 0, length); // 數(shù)組復制的最優(yōu)選擇
long start = System.currentTimeMillis();
sort(arr);
long end = System.currentTimeMillis();
System.out.println("sort()耗費時間：" + (end - start) + "ms");
assert isSort(arr);
start = System.currentTimeMillis();
sortPlus(arr2);
end = System.currentTimeMillis();
System.out.println("sortPlus()耗費時間：" + (end - start) + "ms");
assert isSort(arr);
}
其中數(shù)組復制的最優(yōu)方法來自：Java中數(shù)組復制的四種方法
注意：編譯器默認不適用 assert 檢測（但是junit測試中適用）旗扑，所以要使用時要添加參數(shù)虛擬機啟動參數(shù) -ea 具體添加過程蹦骑，請參照eclipse 和 IDEA 設置虛擬機啟動參數(shù)
結論
雖然選擇排序算法簡單，但是其優(yōu)化方案是非常好的一個優(yōu)化思路臀防，也可以考慮使用在別的算法上眠菇，不要僅僅局限于此。
