基本思想
??????簡(jiǎn)單選擇排序是通過(guò)n-i次關(guān)鍵字的比較，從n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄队魏，并和第i個(gè)記錄進(jìn)行交換宛篇。
簡(jiǎn)單選擇排序算法
void selectSort(int[] array) {
int length = array.length;
int min = 0;
for (int i = 0; i < length - 1; i++) {
// 將當(dāng)前下標(biāo)定義為最小值下標(biāo)
min = i;
for (int j = i + 1; j < length; j++) {
if (array[min] > array[j]) {
min = j;
}
}
if (i != min) {
swap(array, i, min);
}
}
}
??????假定待排序序列為{9,1,5,8,3,7,4,6,2}，對(duì)i從0循環(huán)到7：
- 當(dāng)i=0時(shí)嗜价，array[i]=9腋妙，min=0默怨，j=1到8，比較array[min]與array[j]的大小骤素，當(dāng)j=1時(shí)最小匙睹，所以min=1愚屁，最終交換array[1]與array[0]的值：PS：這里雖然比較了8次但只交換了數(shù)據(jù)一次
-
當(dāng)i=1時(shí)，array[i]=9痕檬，min=1集绰，j=2到8，比較array[min]與array[j]的大小谆棺，當(dāng)j=8時(shí)最小，所以min=8罕袋，最終交換array[8]與array[1]的值：
- 之后的數(shù)據(jù)比較和交換完全雷同改淑，最多經(jīng)過(guò)8次交換即可完成排序工作。
優(yōu)點(diǎn)：交換移動(dòng)數(shù)據(jù)的次數(shù)非常少浴讯，節(jié)約了相應(yīng)的時(shí)間
簡(jiǎn)單選擇排序算法時(shí)間復(fù)雜度分析
??????對(duì)于比較而言朵夏，無(wú)論最好還是最壞的情況下，比較的次數(shù)都是一樣多的：第i趟排序需要進(jìn)行n-i次關(guān)鍵字的比較榆纽，所以共需要比較(n-1)+(n-2)+(n-3)+······+1次仰猖，就是n(n-1)/2次比較；對(duì)于交換而言奈籽，最好情況下交換0次饥侵，最壞情況下交換n-1次。
??????基于最終的時(shí)間復(fù)雜度是比較與交互次數(shù)的和衣屏，所以它的時(shí)間復(fù)雜度為O(n^2)
雖然簡(jiǎn)單選擇排序與冒泡排序的時(shí)間復(fù)雜度均為O(n^2)躏升，但是簡(jiǎn)單選擇排序在性能上還是略優(yōu)于冒泡排序的。
