摘要：前言前天看到知乎上有一篇文章在吐槽阮一峰老師的快速排序算法這里插一句題外話我覺得人非圣賢孰能無過盡信書不如無書學習的過程也就是不斷發(fā)現(xiàn)錯誤改正錯誤的過程有人幫我們糾正了這個錯誤我們應該開心但是我覺得不應該批判阮一峰老師他也在不斷地學習不斷地

前天看到知乎上有一篇文章在吐槽阮一峰老師的快速排序算法,這里插一句題外話,我覺得人非圣賢孰能無過,盡信書不如無書,學習的過程也就是不斷發(fā)現(xiàn)錯誤改正錯誤的過程,有人幫我們糾正了這個錯誤我們應該開心,但是我覺得不應該批判阮一峰老師,他也在不斷地學習,不斷地糾錯成長,所以大家都一樣,無所謂誤導,如果出錯的不是他,是更厲害的牛人呢?JavaScript的作者呢?所以大家都會出錯,我們也應該多思考,抱著懷疑的態(tài)度接納,時刻思考這是不是最優(yōu)的解法,還有沒有更好的呢,我想這才是我們應該做的.
而我,作為一個計算機專業(yè)的前端,卻不能很好地實現(xiàn)各種思想的排序算法,我覺得很慚愧,所以我就抽時間仔細查看了<<數(shù)據(jù)結構與算法分析：C語言描述+中文版.pdf>>這本書,下面我就對我理解的各種思想的排序算法做一下總結,希望可以給大家一些參考和收獲,如有不妥之處,煩請指出,也可以分享你們覺得更好地想法,我覺得大家一起學習一起進步是最快樂的事~

(1) 時間復雜度的概念
算法的時間復雜度是一個函數(shù),他定性地描述了某個算法的運行時間,常用大O符號,不包括這個函數(shù)的低階項和高階項系數(shù).
(2) 計算方法

一般情況下,算法中基本操作的執(zhí)行次數(shù)是問題規(guī)模n的某個函數(shù),用T(n)表示,若有某個輔助函數(shù)f(n),使得當n趨近于無窮大時,T(n)/f(n)的極限值為不為零的常數(shù),則f(n)是T(n)的同數(shù)量級函數(shù),記作T(n) = O(f(n)),稱O(f(n))為算法的漸進時間復雜度,簡稱為時間復雜度.

分析: 隨時模塊n的增大,算法的執(zhí)行時間的增長率和f(n)的增長率成正比,所以f(n)越小,算法的時間復雜度越低,算法的效率越高.

在計算時間復雜度的時候,先找出算法的基本操作,然后計算出基本操作的執(zhí)行次數(shù),找出T(n)的同數(shù)量級f(n)(它的同數(shù)量級一般有以下: 1, log?n,n,nlog?n,n的平方,n的三次方),若T(n) / f(n)求極限得到一常數(shù)c,則時間復雜度T(n) = O(f(n)):

舉例如下:

for(i = 1; i<= n; i++) {
    for(j = 1; j <= n; j++) {
        c[i][j] = 0;   // 該步驟屬于基本操作的執(zhí)行次數(shù): n的平方
        for( k= 1;k <= n; k++) {
            c[i][j] += a[i][k] * b[k][j];   // 該步驟屬于基本操作的執(zhí)行次數(shù): n的三次方
        }
    }
}

我們可以得到T(n) = n^3 + n^2,我們可以確定n^3為T(n)的同數(shù)量級,f(n)=n^3;然后T(n) / f(n) = 1 + 1/n 求極限為常數(shù)1,所以該算法的時間復雜度為:
T(n) = O(n^3);

說明: 為了方便我接下來都是使用N來代指數(shù)組元素個數(shù)的.
我的建議: 我建議大家先看代碼,看不懂代碼的時候?qū)χa看圖解,這樣方便更好的理解

冒泡排序的主要思想就是對一個長度為n的數(shù)組進行遍歷, i從n-1到1的,數(shù)組的前i個元素的最大值放在i位置上,假想冒泡排序是一個豎著的水柱,遍歷的過程就是,大的值(重的)不斷沉下來,小的值(輕的)不斷浮上去,這樣遍歷結束后,每個位置上的值都比他前面的值大,排序結束.

最壞情況下的時間復雜度: o(n^2);
最好情況下的時間復雜度: o(n^2);

function bubbleSort(arr) {
    for(var i = arr.length - 1; i > 1; i--) {
        for(var j=0; j < i; j++) {
            if(arr[j] > arr[j+1]) {
                var temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr;
}
var arr =  [34,8,64,51,32,21];
bubbleSort(arr);  // [8, 21, 32, 34, 51, 64]

function bubbleSort(arr, n) {
    if(n <= 1) {
        return arr;
    } else {
        for(var j=0; j < n - 1; j++) {
            if(arr[j] > arr[j+1]) {
                var temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
        return bubbleSort(arr, --n);
    }
}
var arr =  [34,8,64,51,32,21];
bubbleSort(arr, arr.length);  // [8, 21, 32, 34, 51, 64]

選擇排序的主要思想就是i 從 0 循環(huán)到到length - 1, 依次找出待排數(shù)組中從 i 到 length - 1 位置上的最小值放在 i 位置上.這樣最后得到的數(shù)組就是排好序的數(shù)組了.

最壞情況下的時間復雜度: o(n^2);
最好情況下的時間復雜度: o(n^2);

function selectSort(arr) {
    var len = arr.length, min = 0;
    for(var i = 0;i < len - 1; i++) {
        min = i;   // 默認最小值的位置
        for(var j = i + 1; j < len; j++){
            if(arr[min] > arr[j]) {
                min = j;
            }
        }
        if(min != i) {
            var temp = arr[min];arr[min] = arr[i]; arr[i] = temp;
        }  
    }
    return arr;
}
var arr =  [34,8,64,51,32,21];
selectSort(arr); 

function selectSort(arr, n, min) {
    var len = arr.length;
    if(n < len - 1) {
        for(var j = n + 1; j < len; j++){
            if(arr[min] > arr[j]) {
                min = j;
            }
        }
        if(min != n) {
            var temp = arr[min];arr[min] = arr[n]; arr[n] = temp;
        } 
        n++;
        return  selectSort(arr, n, min);
    }
    return arr;
}
var arr =  [34,8,64,51,32,21];
selectSort(arr, 0, 0); 

插入排序有 n-1 趟排序組成,對于 i=1 到 i=n-1 趟,內(nèi)層循環(huán)j從 i 到 1, 如果這其中有 j-1 位置上的元素大于 i 位置上的元素,就將該元素后移,知道條件不成立退出循環(huán),這個時候大的值都被移動到后面了,j這個位置就是i位置上的元素應該在的位置.這樣保證了每次循環(huán)i位置前的所有元素都是排好序的,新的循環(huán)就只需要 將 i 位置上的元素 和 j-1(也就是初始的 i-1) 位置上的元素作比較,如果大于則無需再往前比較,如果小于則繼續(xù)往前比較后移.

最壞情況下的時間復雜度: o(n^2);
最好情況下的時間復雜度: o(n);

function insertSort(arr) {
    var n = arr.length,temp = 0;
    for(var i = 1; i < n; i++) {
        temp = arr[i];
        for(j = i; j > 0 && arr[j-1] > temp; j--) {
            arr[j] = arr[j - 1];
        }
        arr[j] = temp;
    }
    return arr;
}
var arr =  [34,8,64,51,32,21];
insertSort(arr);  // [8, 21, 32, 34, 51, 64]

function insertSort(arr, n) {
    if(n > 0 && n < arr.length){
        var i = j = n, temp = arr[n];
        while(j > 0 && arr[j - 1] > temp) {
            arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = temp;
        i++;
        return insertSort(arr, i);
    }
    return arr;
}
var arr =  [34,8,64,51,32,21];
insertSort(arr, 1); // [8, 21, 32, 34, 51, 64]; // 這個函數(shù)的調(diào)用限定了第一次調(diào)用n的值只能傳1

顧名思義,快速排序是在實踐中最快的已知排序算法,它的平均運行時間是O(Nlog?N).快速排序的關鍵在于樞紐元的選取,有一種比較推薦的選取方法就是選取左端的值,右端的值,中間位置的值(L(left + right) / 2)這三個數(shù)的中位數(shù).舉例: 輸入為8,1,4,9,6,3,5,2,7,0, 左邊元素8, 右邊元素0,中間位置上的元素L(0+9)/2是4位置上的元素是6,L在表示向下取整.
8,0,6的中位數(shù),先排序0,6,8, 這三個數(shù)的中位數(shù)是6.

通過一趟排序?qū)⒁判虻牟糠址指畛瑟毩⒌膬刹糠?其中一部分數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小,然后再按此方法對這兩部分數(shù)據(jù)進行快速排序,整個排序過程可以遞歸進行,依次達到整個數(shù)據(jù)變成有序序列.

實現(xiàn)步驟

第一步: 設置兩個變量i,j,排序開始的時候: i=left,j=right-1,left和right分別表示要進行快速排序序列的起始索引和結束索引;

第二步: 從數(shù)組中隨機選取一個元素,將其與arr[left]進行交換,即privot = arr[left],保證每一次的基準值都在序列的最左邊;

第三步: 由j開始向前搜索,即由后開始向前搜索(j--),找到第一個小于privot 的值arr[j],將arr[i]與arr[j]互換;

第四步: 從i開始向后搜索,即由前開始向后搜索(i++),找到一個大于privot 的arr[i],將arr[i]與arr[j]互換;

第五步: 重復第三步和第四步,直到不滿足i

第六步: 重復第二步到第四步,依次對i位置左右兩邊的元素進行快速排序,直到left大于等于right為止.

平均情況下的時間復雜度: o(nlog?n);
最好情況下的時間復雜度: o(n);

function quickSort(arr, left, right) {
    if(left >= right) return;
    var i = left;
    var j = right - 1;
    var privot = arr[left];
    //console.log(privot);
    while(i < j) {
        while(i= privot) j--;
        arr[i] = arr[j];
        while(i
快速排序-非遞歸實現(xiàn)
function mainProduce(arr, left, right) {
        var i = left, j = right - 1;
        var rendomIndex = Math.floor(Math.random() * (j - i)) + left;
        var temp = arr[left];arr[left] = arr[rendomIndex];arr[rendomIndex] = temp;
        var privot = arr[left];
        while(i < j) {
            while(i= privot) j--;
            var temp = arr[i];arr[i] = arr[j];arr[j] = temp;
            while(i left + 1) {
                s.push(left);s.push(mid);
            }
            if(mid < right - 1) {
                s.push(mid + 1);s.push(right);
            }
            
            while(s.length !== 0) {
                right = s.pop();
                left = s.pop();
                mid = mainProduce(arr, left, right);
                if(mid > left + 1) {
                    s.push(left);s.push(mid);
                }
                if(mid < right - 1) {
                    s.push(mid + 1);s.push(right);
                }
            }
        }
        return arr;
    }
    var arr = [49,38,65,97,76,13,27,49,55,04];
    quickSort(arr, 0, arr.length);
    
2.5 希爾排序
2.5.1 主要思想
希爾排序是把記錄按照下標的一定增量分組,對每組使用插入排序;隨著增量逐漸減少,分割的數(shù)組越來越大,當增量減至1,整個數(shù)組排序完成,算法終止.
主要步驟

第一步: 選取一個增量d,初始值是Math.floor(len/2);
第二步: 然后將數(shù)組中間隔為增量d的組成新的分組,然后對這個分組的元素排序,完成排序后,增量除以2得到新的增量;
第三步: 重復第二步,直到增量為1,間隔為1的元素組成的分組就是整個數(shù)組,然后再對整個數(shù)組進行插入排序,得到最后排序后數(shù)組.

希爾排序是不穩(wěn)定的,它在不斷地交換的過程中會改變原來相等的元素的順序.
2.5.2 時間復雜度
平均情況下的時間復雜度: o(nlog?n);
最好情況下的時間復雜度: o(n);
2.5.3 排序過程圖解

圖片源于自百度百科: 圖片來源
2.5.4 代碼實現(xiàn):
希爾排序-遞歸實現(xiàn)
function shellSort(arr, increment) {
    var len = arr.length;
    if(increment > 0) {
        for(var i = increment; i < len; i++) {
            for(var j = i - increment; j >= 0 && arr[j] > arr[j + increment]; j -= increment) {
                    var temp = arr[j];
                    arr[j] = arr[j + increment];
                    arr[j + increment] = temp;
            }
        }
        return shellSort(arr, Math.floor(increment/2));
    }
     return arr; 
}
var arr = [49,38,65,97,76,13,27,49,55,04];
shellSort(arr, Math.floor(arr.length / 2));
 
希爾排序-非遞歸實現(xiàn)
function shellSort(arr) {
        var len = arr.length;
        for(var increment = Math.floor(len / 2); increment > 0; increment = Math.floor(increment / 2)) {
                for(var i = increment; i < len; i++) {
                        for(var j = i - increment; j >= 0 && arr[j] > arr[j + increment]; j -= increment) {
                                var temp = arr[j];
                                arr[j] = arr[j + increment];
                                arr[j + increment] = temp;
                        }
                }
        }
        return arr;
}
var arr = [49,38,65,97,76,13,27,49,55,04];
shellSort(arr);
 

2.6 歸并排序
2.6.1 主要思想
希爾排序的主要思想就是遞歸將數(shù)組層層分割,直到分割成最小的單元,然后再比較,提供一個新的空數(shù)組arrayC,將分割的左右兩個數(shù)組中小的數(shù)放進數(shù)組,然后再層層回溯向上合并.得到最終的arrayC就是排序后的數(shù)組.
2.6.2 時間復雜度
平均情況下的時間復雜度: O(nlog?n);
最好情況下的時間復雜度: O(nlog?n) ;
2.6.3 排序過程圖解

2.6.4 代碼實現(xiàn):
歸并排序-遞歸實現(xiàn)
var result = [];
function mergeArray(left, right) {
    result = [];
    while(left.length > 0 && right.length > 0) {
        if(left[0] < right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
            }
    }
    return result.concat(left).concat(right);
}
function mergerSort(arr) {
    if(arr.length <= 1) {
        return arr;
    }

    var middle = Math.floor(arr.length / 2);
    var left = arr.slice(0, middle);
    var right = arr.slice(middle);
    return mergeArray(mergerSort(left), mergerSort(right));
}
var arr = [49,38,65,97,76,13,27,49,55,04];
mergerSort(arr, 0, arr.length);
 
由于歸并排序的非遞歸實現(xiàn)比較復雜,我這里就不做講解了,我覺得如果真的需要用到,讀者可自行研究.
總結
這是我寫的最用心的一篇博客了,萬事開頭難,我已經(jīng)開頭了,就是一種突破.希望我可以繼續(xù)堅持下去,不斷充電,不斷輸出,成為一個優(yōu)秀的前端工程師,加油 ^-^ ^-^.
  歡迎幫我糾正錯誤和有疑問的人與我交流, it will be my pleasure.  我的qq號: 2510909248.
推薦閱讀
1) 十大經(jīng)典排序算法總結（JavaScript描述）