python選擇排序，[轉載] python選擇排序二元選擇_選擇排序：簡單選擇排序（Simple Selection Sort）

參考鏈接： Python中選擇排序Selection Sort

基本思想：

python選擇排序，?在要排序的一組數中，選出最小(或者最大)的一個數與第1個位置的數交換；然后在剩下的數當中再找最小(或者最大)的與第2個位置的數交換，依次類推，直到第n-1個元素(倒數第二個數)和第n個元素(最后一個數)比較為止。

?簡單選擇排序示例

?初始值： 3 1 5 7 2 4 9 6

python excel？?第一趟： 1 3 5 7 2 4 9 6

?第二趟： 1 2 5 7 3 4 9 6

?第三趟： 1 2 3 7 5 4 9 6

python排序函數、?第四趟： 1 2 3 4 5 7 9 6

?第五趟： 1 2 3 4 5 7 9 6

?第六趟： 1 2 3 4 5 6 9 7

python元祖，?第七趟： 1 2 3 4 5 6 7 9

?第八趟： 1 2 3 4 5 6 7 9

?操作方法：

python編程？?第一趟，從n 個記錄中找出關鍵碼最小的記錄與第一個記錄交換；

?第二趟，從第二個記錄開始的n-1 個記錄中再選出關鍵碼最小的記錄與第二個記錄交換；

?......

?第 i 趟，則從第 i 個記錄開始的 n-i+1 個記錄中選出關鍵碼最小的記錄與第 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");

?}

?// 獲取數組最小值下標

?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;

?}

?算法的改進(二元選擇排序)

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

?// 二元選擇排序

?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);

?}

?}

?總結

?在簡單選擇排序過程中，所需移動記錄的次數比較少。最好情況下，即待排序記錄初始狀態就已經是正序排列了，則不需要移動記錄。

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

?簡單選擇排序是不穩定排序。