基本思想：

在要排序的一組數(shù)中，選出最小（或者最大）的一個(gè)數(shù)與第1個(gè)位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最小（或者最大）的與第2個(gè)位置的數(shù)交換，依次類推，直到第n-1個(gè)元素（倒數(shù)第二個(gè)數(shù)）和第n個(gè)元素（最后一個(gè)數(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 個(gè)記錄中找出關(guān)鍵碼最小的記錄與第一個(gè)記錄交換；

第二趟，從第二個(gè)記錄開始的n-1 個(gè)記錄中再選出關(guān)鍵碼最小的記錄與第二個(gè)記錄交換；

......

第 i 趟，則從第 i 個(gè)記錄開始的 n-i+1 個(gè)記錄中選出關(guān)鍵碼最小的記錄與第 i 個(gè)記錄交換，直到整個(gè)序列按關(guān)鍵碼有序。

算法的實(shí)現(xiàn)：

// 輸出數(shù)組內(nèi)容
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ù)組最小值下標(biāo)
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); // 獲取最小元素的下標(biāo)
        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;
}

算法的改進(jìn)（二元選擇排序）

簡單選擇排序，每趟循環(huán)只能確定一個(gè)元素排序后的定位。我們可以考慮改進(jìn)為每趟循環(huán)確定兩個(gè)元素（當(dāng)前趟最大和最小記錄）的位置,從而減少排序所需的循環(huán)次數(shù)。改進(jìn)后對n個(gè)數(shù)據(jù)進(jìn)行排序，最多只需進(jìn)行[n/2]趟循環(huán)即可。具體實(shí)現(xiàn)如下：

// 二元選擇排序
void SelectSort2(int array[], int length) {
    int i, j, min, max;
    for (i = 0; i < length / 2; i ++) { // i 跑 n / 2 趟排序就會(huì)排序完成
        min = max = i; // 先將 min 和 max 都指向待排序的第一個(gè)元素
        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]調(diào)換
        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);
    }
}

總結(jié)

在簡單選擇排序過程中，所需移動(dòng)記錄的次數(shù)比較少。最好情況下，即待排序記錄初始狀態(tài)就已經(jīng)是正序排列了，則不需要移動(dòng)記錄。

最壞情況下，即待排序記錄初始狀態(tài)是按第一條記錄最大，之后的記錄從小到大順序排列，則需要移動(dòng)記錄的次數(shù)最多為3（n-1）。簡單選擇排序過程中需要進(jìn)行的比較次數(shù)與初始狀態(tài)下待排序的記錄序列的排列情況無關(guān)。當(dāng)i=1時(shí)，需進(jìn)行n-1次比較；當(dāng)i=2時(shí)，需進(jìn)行n-2次比較；依次類推，共需要進(jìn)行的比較次數(shù)是(n-1)+(n-2)+…+2+1=n(n-1)/2，即進(jìn)行比較操作的時(shí)間復(fù)雜度為O(n^2)，進(jìn)行移動(dòng)操作的時(shí)間復(fù)雜度為O(n)。

簡單選擇排序是不穩(wěn)定排序。