基本思想：
在要排序的一組數(shù)中蛀序，選出最小（或者最大）的一個數(shù)與第1個位置的數(shù)交換徐裸；然后在剩下的數(shù)當中再找最小（或者最大）的與第2個位置的數(shù)交換譬正，依次類推檬姥，直到第n-1個元素（倒數(shù)第二個數(shù)）和第n個元素（最后一個數(shù)）比較為止粉怕。
簡單選擇排序示例
初始值： 3 1 5 7 2 4 9 6
第一趟： 1 3 5 7 2 4 9 6
第二趟： 1 2 5 7 3 4 9 6
第三趟： 1 2 3 7 5 4 9 6
第四趟： 1 2 3 4 5 7 9 6
第五趟： 1 2 3 4 5 7 9 6
第六趟： 1 2 3 4 5 6 9 7
第七趟： 1 2 3 4 5 6 7 9
第八趟： 1 2 3 4 5 6 7 9
操作方法：
第一趟，從n 個記錄中找出關鍵碼最小的記錄與第一個記錄交換贫贝；
第二趟蛉谜，從第二個記錄開始的n-1 個記錄中再選出關鍵碼最小的記錄與第二個記錄交換崇堵；
......
第 i 趟，則從第 i 個記錄開始的 n-i+1 個記錄中選出關鍵碼最小的記錄與第 i 個記錄交換狰贯，直到整個序列按關鍵碼有序赏廓。
算法的實現(xiàn)：
// 輸出數(shù)組內容
void print(int array[], int length, int i) {
printf("i=%d:",i);
for (int j = 0; j < length; j++) {
printf(" %d ", array[j]);
}
printf("\n");
}
// 獲取數(shù)組最小值下標
int SelectMinKey(int array[], int length, int i) {
int k = i;
for (int j = i + 1; j < length; j ++) {
if (array[k] > array[j]) {
k = j;
}
}
return k;
}
// 簡單選擇排序（Simple Selection Sort）
void SelectSort(int array[], int length) {
int key, temp;
for (int i = 0; i < length; i ++) {
key = SelectMinKey(array, length, i); // 獲取最小元素的下標
if (key != i) { // 最小元素與第i位置元素交換
temp = array[i];
array[i] = array[key];
array[key] = temp;
}
print(array, length, i);
}
}
int main(int argc, const char * argv[]) {
int arraySelectSort[8] = { 3, 1, 5, 7, 2, 4, 9, 6 };
SelectSort(arraySelectSort, 8);
printf("\n");
return 0;
}
算法的改進（二元選擇排序）
簡單選擇排序，每趟循環(huán)只能確定一個元素排序后的定位摸柄。我們可以考慮改進為每趟循環(huán)確定兩個元素（當前趟最大和最小記錄）的位置,從而減少排序所需的循環(huán)次數(shù)既忆。改進后對n個數(shù)據(jù)進行排序，最多只需進行[n/2]趟循環(huán)即可患雇。具體實現(xiàn)如下：
// 二元選擇排序
void SelectSort2(int array[], int length) {
int i, j, min, max;
for (i = 0; i < length / 2; i ++) { // i 跑 n / 2 趟排序就會排序完成
min = max = i; // 先將 min 和 max 都指向待排序的第一個元素
for(j = i; j < length - i; j ++) {
if (array[j] < array[min]) {
min = j;
continue;
}
if (array[j] > array[max]) {
max = j;
}
}
// 將最小值放在第i處，將最大值放在第length-i-1處
// 注意:這里不能把 array[max]匾乓、array[min] 直接和 array[i] 和 array[length-i-1]調換
int maxtemp = array[max];
int mintemp = array[min];
array[max] = array[length-i-1];
array[min] = array[i];
array[i] = mintemp;
array[length-i-1] = maxtemp;
print(array, 8, i);
}
}
總結
在簡單選擇排序過程中又谋，所需移動記錄的次數(shù)比較少。最好情況下彰亥，即待排序記錄初始狀態(tài)就已經是正序排列了，則不需要移動記錄继阻。
最壞情況下废酷，即待排序記錄初始狀態(tài)是按第一條記錄最大，之后的記錄從小到大順序排列澈蟆，則需要移動記錄的次數(shù)最多為3（n-1）。簡單選擇排序過程中需要進行的比較次數(shù)與初始狀態(tài)下待排序的記錄序列的排列情況無關趴俘。當i=1時睹簇，需進行n-1次比較；當i=2時磨淌，需進行n-2次比較凿渊；依次類推，共需要進行的比較次數(shù)是(n-1)+(n-2)+…+2+1=n(n-1)/2嗽元，即進行比較操作的時間復雜度為O(n^2)，進行移動操作的時間復雜度為O(n)淤翔。
簡單選擇排序是不穩(wěn)定排序。
