選擇排序和插入排序--學習筆記

插入排序和選擇排序--學習筆記

　　從《演算法導論》學習了插入排序，選擇排序是在課後練習出現的，代碼用javascript編寫。

　　首先，瞭解一下插入排序和選擇排序。類似玩撲克游戲，如下圖（摘自《演算法導論》-- 插入排序的附圖）：

　　插入排序和選擇排序就像兩個不同習慣的人：一個人喜歡一張一張地摸牌（插入排序），而另一個人則喜歡等發牌員發完牌拿在手上一起調整（選擇排序）。

插入排序

　　插入排序類似於一張一張地摸牌，其中，在手上的牌已經排序，而在桌子上的牌則是待排序的牌，因此，第一張牌肯定是已排序的，迴圈應該從第二張牌開始。

　　《演算法導論》中插入排序過程附圖：

　　其中，灰色為已排序部分，黑色為正在排序（剛摸到的牌），白色為未排序（還在桌面的牌）。可初步設計為，外層迴圈控制待比較的未知元素個數，而內層迴圈則為當前正在排序的元素（當前元素）與其前面的元素逐一比較。

　　js代碼：

 1 var s = [5, 4, 3, 2, 1];
 2 var insertSort = function(array) {
 3     var key;　　　　//記錄當前排序元素（摸到的牌）
 4     var j;
 5     for(var i = 1; i < array.length; i++) {
 6         key = array[i];
 7         j = i - 1;
 8         while(j >= 0 && key < array[j]) {
 9             array[j+1] = array[j];
10             j--;
11         }
12         array[j+1] = key;　　　　//在合適的位置，用當前排序的元素替換
13     }
14     return array;
15 };
16 insertSort(s);
17 console.log(insertSort(s));
18 //=>[ 1, 2, 3, 4, 5 ]

　演算法用一個for迴圈和一個嵌套的while迴圈實現。需要註意的是，while迴圈內部調整當前元素之前的元素的位置，但while迴圈結束時得到的數組並沒有包含原數組的所有元素，而是在第12行的時候將當前元素（摸到的牌）替換。

　　修改代碼觀察演算法過程：

var s = [5, 4, 3, 2, 1];
var insertSort = function(array) {
    var key;　　　　//記錄當前排序元素（摸到的牌）
    var j;
    for(var i = 1; i < array.length; i++) {
        key = array[i];
        j = i - 1;
        while(j >= 0 && key < array[j]) {
            array[j+1] = array[j];
            j--;
        }
        console.log(array);
        array[j+1] = key;　　　　//在合適的位置，用當前排序元素替換
        console.log(array);
    }
};
insertSort(s);
//=>[ 5, 5, 3, 2, 1 ]　　//整個while迴圈結束時
    [ 4, 5, 3, 2, 1 ]　　//下一個for迴圈開始前
    [ 4, 4, 5, 2, 1 ]
    [ 3, 4, 5, 2, 1 ]
    [ 3, 3, 4, 5, 1 ]
    [ 2, 3, 4, 5, 1 ]
    [ 2, 2, 3, 4, 5 ]
    [ 1, 2, 3, 4, 5 ]

選擇排序

　　選擇排序類似於，在桌子上抓起一把牌（不知道有沒有排序），把牌攤開後，從裡面選出最小（或最大）的一張牌，然後與左邊第一張牌交換（不同的地方是正常人給牌排序時一般直接插入而不是交換）；接著從剩下的牌中找出第二小的牌，與左邊第二張牌交換；...直到找出n - 1張較小的牌交換，則成功排序。

代碼：

 1 var s = [5, 2, 1, 6, 8, 7, 4, 3];
 2 var selectSort = function(array) {
 3     var temp, flag;　　//flag記錄剩下元素中"最小"數的下標
 4     for(var i = 0; i < array.length - 1; i++) {
 5         flag = i;
 6         for(var j = i; j < array.length; j++) {
 7             if(array[j] <= array[flag]) {
 8                 flag = j;
 9             } 
10         }
11         temp = array[i];
12         array[i] = array[flag];
13         array[flag] = temp;　　　　//交換
14     }
15 };
16 selectSort(s);
17 console.log(s);
18 //=>[ 1, 2, 3, 4, 5, 6, 7, 8 ]

修改代碼顯示排序過程：

var s = [5, 2, 1, 6, 8, 7, 4, 3];
var selectSort = function(array) {
    var temp, flag;
    for(var i = 0; i < array.length - 1; i++) {
        flag = i;
        for(var j = i; j < array.length; j++) {
            if(array[j] <= array[flag]) {
                flag = j;
            } 
        }

        temp = array[i];
        array[i] = array[flag];
        array[flag] = temp;

        console.log(array);
    }
};
selectSort(s);
console.log(s);
//=>[ 1, 2, 5, 6, 8, 7, 4, 3 ]
    [ 1, 2, 5, 6, 8, 7, 4, 3 ]
    [ 1, 2, 3, 6, 8, 7, 4, 5 ]
    [ 1, 2, 3, 4, 8, 7, 6, 5 ]
    [ 1, 2, 3, 4, 5, 7, 6, 8 ]
    [ 1, 2, 3, 4, 5, 6, 7, 8 ]
    [ 1, 2, 3, 4, 5, 6, 7, 8 ]
    [ 1, 2, 3, 4, 5, 6, 7, 8 ]

 　　可見，每次外層for迴圈都能找出一個“最小”數，並與前面適合位置的數進行交換。

----------------------------------------------------------------------------------------------------------

　　因為筆者還處在學習階段，文中出現很多不規範或者錯誤之處，還望各位看官賜教。

　　另外，十分感謝《演算法導論》。

　　註：本文為個人學習隨筆，僅供個人學習，如有雷同，敬請原諒！