冒泡排序和雞尾酒排序的代碼分析

冒泡排序

　　冒泡排序（buble sort）是一個比較入門的排序演算法。顧名思義，它根據將最大（或最小）的數依次冒泡從而實現排序。

　　如下圖所示，白色部分為待排序數組，紅色部分為已找出的“較大的”數，每次迭代只需從白色部分找出其中最大的數字，直至找出n-1個“較大的”數後，數組已排序。

　　註：找出n-1個“較大的”數即可，因為最後一個必定為最小的數。

代碼：

var s = [8, 7, 6, 5, 4, 3, 2, 1];
var bubleSort = function(array) {
    var temp;
    for(var i=0; i < array.length-1; i++) {　　　　//外層迴圈7次
        for(var j=0; j < array.length - i - 1; j++) {　　//已有i個較大數被冒泡，比較次數為n-i-1
            if(array[j] > array[j+1]) {
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
};
bubleSort(s);
console.log(s);
//=>[ 1, 2, 3, 4, 5, 6, 7, 8 ]

代碼分析：採用嵌套的for迴圈實現。其中外層迴圈控制找出”較大的“數的個數（n - 1）；內層迴圈控制找出第i個”較大的“數需要比較的次數（n - 1 - i），因為已有i個”較大的“數被冒泡，因此越到後面需要比較的次數就越少。

迴圈不變式：

　　第 1 次迴圈結束時，最後一個為最大數；

　　第 i 次迴圈結束時，s[n - i, n - 1]為按序排列的"較大"數；

　　...

　　第 n 次迴圈結束時，s[1，n - 1]為按序排列的"較大"數，而s[0]必定為最小數，因此整個數組已按序排列。

添加一行代碼在控制台觀察程式過程：

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

雞尾酒排序

　　雞尾酒排序（cocktail sort）對冒泡排序進行了優化，使得外層迴圈一次能找出兩個已排序的數（最大和最小），可以理解為”雙向“的冒泡排序。

　　註：因為雞尾酒排序外層迴圈一次能找出兩個排序數，故其外層迴圈次數折半，而內層迴圈則為兩個併列的for迴圈（分別控制正向和反向）。總的來說，雞尾酒排序大多數情況下要比冒泡排序效率高。

代碼：

var s = [8, 7, 6, 5, 4, 3, 2, 1];
var cocktailSort = function(array) {
    var count = 0; 
    var temp;
    for(var i = 0; i < array.length/2; i++) {　　//外層迴圈次數折半
        for(var j = count; j < array.length - count -1; j++) {　　//一次正向迴圈
            if(array[j] > array[j+1]) {
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
        count++;　　　　//記錄已找出"較大"數個數
        for(var k = array.length - 1 - count; k > count - 1; k--) {　　//一次反向迴圈
            if(array[k] < array[k-1]) {
                temp = array[k];
                array[k] = array[k-1];
                array[k-1] = temp;
            }
        }
    }
};
cocktailSort(s);
console.log(s);
//=>[ 1, 2, 3, 4, 5, 6, 7, 8 ]

代碼分析：外層迴圈次數折半，因為外層迴圈一次內層已包含一次往返；內層正向迴圈找出"較大"數，其中起點為count（當前找出"較大"數個數）；內層反向迴圈的起點為n - 1 - count（該輪"較大"數的前一位），終點為count - 1（當前找出的"較小"數個數）。

迴圈不變式：

　　第 1 次迴圈結束時：第n個數為最大數，第1個數為最小數；

　　第 i 次迴圈結束時：s[n-i ,n-1]為按序排列的"較大"數，s[0, i-1]為按序排列的"較小"數；

　　...

　　第 n 次迴圈結束時： s[n - n/2, n-1]為按序排列的"較大數"，s[0, n/2-1]為按序排列的"較小"數，故整個數組已按序排列。

在控制台觀察輸出：

var s = [8, 7, 6, 5, 4, 3, 2, 1];
var cocktailSort = function(array) {
    var count = 0; 
    var temp;
    for(var i = 0; i < array.length/2; i++) {
        for(var j = count; j < array.length - count -1; j++) {
            if(array[j] > array[j+1]) {
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
        count++;
        for(var k = array.length - 1 - count; k > count - 1; k--) {
            if(array[k] < array[k-1]) {
                temp = array[k];
                array[k] = array[k-1];
                array[k-1] = temp;
            }
        }
        console.log(array);
    }
};
cocktailSort(s);
console.log(s);
//=>[ 1, 7, 6, 5, 4, 3, 2, 8 ]
    [ 1, 2, 6, 5, 4, 3, 7, 8 ]
    [ 1, 2, 3, 5, 4, 6, 7, 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]）時，冒泡排序和雞尾酒排序的結果過程均會做很多"無用功"。可以在迴圈內部定義一個flag，當某一輪迴圈數組元素不再發生交換時，便可認為數組已按序排列：

var s = [1,2,3,4,5,8,6,7];
var cocktailSort = function(array) {
    var count = 0; 
    var temp;
    for(var i = 0; i < array.length/2; i++) {
        var flag = false;　　//定義flag
        for(var j = count; j < array.length - count -1; j++) {
            if(array[j] > array[j+1]) {
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                flag = true;　　//當發生交換時，改變flag的值為true
            }
        }
        count++;
        for(var k = array.length - 1 - count; k > count - 1; k--) {
            if(array[k] < array[k-1]) {
                temp = array[k];
                array[k] = array[k-1];
                array[k-1] = temp;
                flag = true;　　//當發生交換時，改變flag的值true
            }
        }
        console.log(array);
        if(!flag)
            break;
    }
};
cocktailSort(s);
//=>[ 1, 2, 3, 4, 5, 6, 7, 8 ]　　//輸出結果顯示，演算法會提前結束
    [ 1, 2, 3, 4, 5, 6, 7, 8 ]

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

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