版權(quán)聲明：本文源自簡書tianma荤堪，轉(zhuǎn)載請務(wù)必注明出處：http://www.reibang.com/p/e45b7c94ebab
概念
簡單選擇排序是選擇類的排序铆惑，算法原理：第i次排序（1≤ i ≤n-1）蒲障，從待排序的n-i+1個記錄中袖裕， 進行n-i次關(guān)鍵字比較，從n-i+1個記錄中選出最小的息楔，并和第i-1個記錄進行交換妒峦。
演示
比如我們待排序的數(shù)組是 {9, 1, 5, 8, 3, 7, 4, 6, 2}
第1趟排序重斑，1最小，與第0個位置9進行交換： 1 9 5 8 3 7 4 6 2
第2趟排序肯骇，2最小窥浪，與第1個位置9進行交換： 1 2 5 8 3 7 4 6 9
第3趟排序，3最小笛丙，與第2個位置5進行交換： 1 2 3 8 5 7 4 6 9
第4趟排序漾脂，4最小，與第3個位置8進行交換： 1 2 3 4 5 7 8 6 9
第5趟排序胚鸯，5最小骨稿，第4個位置是5無須交換： 1 2 3 4 5 7 8 6 9
第6趟排序，6最小姜钳，與第5個位置7進行交換： 1 2 3 4 5 6 8 7 9
第7趟排序坦冠，7最小，與第6個位置8進行交換： 1 2 3 4 5 6 7 8 9
第8趟排序傲须，8最小，第7個位置是8無須交換： 1 2 3 4 5 6 7 8 9
其實就是每一趟排序?qū)?dāng)前未排序序列中的最小的記錄與未排序序列的最前端的位置進行交換趟脂。
Java實現(xiàn)
// 定義接口
interface Sorter {
/**
* 將數(shù)組按升序排序
*/
int[] sort(int[] arr);
/**
* 交換數(shù)組arr中的第i個位置和第j個位置的關(guān)鍵字
*/
default void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
//選擇排序
class SelectionSorter implements Sorter {
@Override
public int[] sort(int[] arr) {
selectSort(arr);
return arr;
}
private void selectSort(int[] arr) {
int i, j, min;
int len = arr.length;
for (i = 0; i < len - 1; i++) {
min = i; // min記錄最小值的下標(biāo)
for (j = i + 1; j < len; j++) { // 循環(huán)i之后的數(shù)據(jù)
if (arr[j] < arr[min]) // 發(fā)現(xiàn)有小于當(dāng)前最小值的關(guān)鍵字
min = j; // 將該下標(biāo)賦值給min
}
if (i != min) // 如果i和min不等泰讽，在i之后的數(shù)據(jù)中找到了最小值，則需要arr[i]于arr[min]進行交換
swap(arr, i, min);
}
}
}
復(fù)雜度
時間復(fù)雜度：
對于比較次數(shù)而言昔期，無論最好最差情況已卸，其比較次數(shù)都是一樣的：第i趟排序需要進行n-i次比較，此時比較次數(shù)=(n-1)+(n-2)+...+1 = n*(n-1)/2硼一；
對于交換次數(shù)而言累澡，其最好情況為順序表，交換次數(shù)為0次般贼；最差情況為逆序表愧哟，交換次數(shù)為n-1次，那么平均情況則為(n-1)/2次交換哼蛆；
由于時間復(fù)雜度取決于比較次數(shù)和交換次數(shù)總和蕊梧，故而交換排序的時間復(fù)雜度為O(n^2)。
因為相較于冒泡排序腮介，選擇排序的交換次數(shù)要少肥矢，所以選擇排序的性能要優(yōu)于冒泡排序。
空間復(fù)雜度：
最好情況=最壞情況=平均情況=O(1)
