作為一名程序員，算法是一個(gè)沒法回避的話題，因?yàn)樗梢哉f是專業(yè)與不專業(yè)的一條分界線。想要在未來有更高的技術(shù)造詣，學(xué)會(huì)數(shù)據(jù)結(jié)構(gòu)算法知識(shí)是必須的。互聯(lián)網(wǎng)技術(shù)發(fā)展到今天，已經(jīng)有很多算法了，而排序算法算是最好的入門算法，因?yàn)樗容^簡(jiǎn)單，而且能讓你迅速了解計(jì)算機(jī)的計(jì)算思維方式。學(xué)習(xí)了常用排序算法之后，我決定做個(gè)總結(jié)。

0.算法的特性

輸入：一個(gè)算法必須有零個(gè)或以上輸入量。
輸出：一個(gè)算法應(yīng)有一個(gè)或以上輸出量。
明確性：算法的描敘必須無歧義，實(shí)際運(yùn)行結(jié)果是確定的
有限性：必須在有限個(gè)步驟內(nèi)結(jié)束
有效性: 又稱可行性,能夠被執(zhí)行者實(shí)現(xiàn)
————高德納《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》

算法的學(xué)習(xí)最重要的是學(xué)會(huì)計(jì)算機(jī)的思維方式，這是精髓也是難點(diǎn)。

• 當(dāng)你遇到思路障礙怎么辦?

• 將抽象的問題轉(zhuǎn)化為具體的問題
• 將沒見過的問題轉(zhuǎn)化為見過的問題

本人的學(xué)習(xí)方法是先用偽代碼實(shí)現(xiàn)或者畫流程圖梳理一遍思路，再用JS實(shí)現(xiàn)具體細(xì)節(jié)。

算法流程圖.jpg

1. 冒泡算法（BUBBLE）

冒泡算法用通俗一點(diǎn)的話說，可以理解為“一個(gè)教官（計(jì)算機(jī)）伸出雙手，從頭開始，按順序依次選擇兩個(gè)人排列站位”。
專業(yè)的理解應(yīng)該是，計(jì)算機(jī)遍歷整個(gè)數(shù)組，每次選擇兩個(gè)數(shù)進(jìn)行排序，小的放前面大的往后放，重復(fù)這個(gè)步驟直到不再需要交換了，也就是說數(shù)組已經(jīng)排列完成。每比較一輪，都會(huì)選出最大的一個(gè)放到當(dāng)前排列數(shù)組的最后。

1.首選選中兩個(gè)數(shù)，準(zhǔn)備進(jìn)行比較

冒泡1.PNG

2. 7>3，所以7往后放，再往后選擇7和30比較

冒泡2.PNG

3. 以此類推比較完第一輪，最大的40被放到了最后

冒泡3.PNG

4. 重復(fù)進(jìn)行前三個(gè)步驟，最后就會(huì)得到一組從小到大排列的數(shù)組。

冒泡4.PNG

實(shí)現(xiàn)代碼

function sort(array){
    for(i=0;i<array.length;i++){
        for(j=0;j<array.length-1;j++){
            if(array[j]<=array[j+1]){

            }else{
                swap(array,j,j+1)
            }
        }
    }
    return array
}
function swap(array,a,b){
    var temp=array[a]
    array[a]=array[b]
    array[b]=temp
}
console.log(sort([3,5,2,21,1]))
console.log(sort([1,3,3,1,1]))
console.log(sort([1]))
console.log(sort([]))

2選擇排序(SELECT)

選擇排序可以通俗理解為第一個(gè)人指著后面的人說，你們中最小的站在我前面來。
專業(yè)的理解：每一次標(biāo)記待排序數(shù)據(jù)元素的第一個(gè)元素為被比較元素，然后往后遍歷，選出最小的存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。每一輪遍歷完，都會(huì)選出當(dāng)前數(shù)組里最小的放在最前面。

1. 標(biāo)記第一個(gè)元素，拿后面的元素與它比較

   
   
   選擇1.PNG

   2. 選出了當(dāng)前待排數(shù)組里最小的元素

   
   
   選擇2.PNG
   3. 將最初標(biāo)記的元素與最小元素交換位置，一輪遍歷結(jié)束。下一輪標(biāo)記21。
   
   選擇3.PNG

   4. 重復(fù)以上步驟，經(jīng)過多輪比較得到一組從小到大排列的數(shù)組。

   
   
   選擇4.PNG

實(shí)現(xiàn)代碼

function sort(array) {
    var indexofMin,i,j
    for(i=0;i<array.length;i++){
           indexofMin=i
       for(j=i+1;j<array.length;j++){
                if(array[j]<array[indexofMin]){
                    indexofMin=j
                }if(indexofMin!==i){
                    swap(array,i,indexofMin)
                }
       }
        
    }
   return array
}
function swap(array,a,b){
    var temp=array[a]
    array[a]=array[b]
    array[b]=temp
}
console.log(sort([3,5,2,21,1]))
console.log(sort([1,3,3,1,1]))
console.log(sort([1]))
console.log(sort([]))

3. 插入排序(INSERT)

插入排序通俗理解：“起牌算法”，和打撲克牌時(shí)起牌方法基本一樣。我們手里已經(jīng)有一副牌，然后選擇一張牌找到它應(yīng)該放的位置，放入，這樣就能將一張張牌都放到正確的位置了。
專業(yè)理解：將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序。是穩(wěn)定的排序方法。

1. 第一輪標(biāo)記48，往前看14與48比較

   
   
   插入1.PNG

   2. ，48>14，不需要變換位置

   
   
   插入2.PNG
   3.第二輪標(biāo)記25，往前看與25比較
   
   插入3.PNG

   4.48>25，把它們倆換位置，25繼續(xù)與前面的14比較

   
   
   插入4.PNG
   5. 25>14，不用交換，此時(shí)25在前兩個(gè)元素中應(yīng)該放的位置已經(jīng)確定，放入此位置。第三輪標(biāo)記24
   
   插入5.PNG
   6. 24分別與前三個(gè)元素比較，比25和48小，所以預(yù)備放在它們之前
   
   插入6.PNG
   7. 25與剩下的14比較，大于14，所以確定最終位置之后，插入。
   
   插入7.PNG
   8. 重復(fù)以上步驟，經(jīng)過多輪比較得到一組從小到大排列的數(shù)組。
   
   插入8.PNG

實(shí)現(xiàn)代碼

var numbers = [21,34,1,3,53,2]
var temp,i,j
for(i=1;i<numbers.length;i++){
    temp=numbers[i]
    for(j=i-1;j>=0&&temp<numbers[j];j--){
        
        numbers[j+1]=numbers[j]
    }
    numbers[j+1]=temp
}
console.log(numbers)

快速排序（QUICK）

快速排序，它又稱為自私算法，它優(yōu)先讓每個(gè)元素找到自己所在的位置，每次排序都實(shí)現(xiàn)“比我大的都在我右邊，比我小的都在我左邊”而不去計(jì)較它們的位置關(guān)系。

1. 第一輪選擇第一個(gè)元素，然后依次拿后面的元素與它比較

   
   
   快速1.PNG

   2. 在比較的過程中，將后面的元素分成兩部分放置，比34大的放一邊，比34小的放另一邊

   
   
   快速2.PNG
   3. 都比較完之后，將34放到中間
   
   快速3.PNG

   4. 第二輪選擇11

   
   
   快速4.PNG
   5. 將34之前的元素與11進(jìn)行比較，然后重復(fù)比較步驟，把11放到它的位置
   
   快速6.PNG
   6. 重復(fù)以上步驟，經(jīng)過多輪比較得到一組從小到大排列的數(shù)組。
   
   快速7.PNG

實(shí)現(xiàn)代碼

function sort(array){
    if(array.length<=1){
        return array;
    }
    var len = Math.floor(array.length/2);
    var cur = array.splice(len,1);
    var left = [];
    var right = [];
    for(var i=0;i<array.length;i++){
        if(cur>array[i]){
            left.push(array[i]);
        }else{
            right.push(array[i]);
        }
    }
    return sort(left).concat(cur,sort(right));
}

時(shí)間復(fù)雜度

• 選擇排序、冒泡排序和插入
  n+（n-1）+（n-2）+（n-3）···=n^2
• 快速排序
  • nlog2n
  • 快速排序有個(gè)缺點(diǎn)，如果給定的數(shù)組是已經(jīng)排好的或者是反序的就不能造成達(dá)到快速的目的了，那么此時(shí)它的時(shí)間復(fù)雜度跟前三種一樣。解決方案是使用隨機(jī)快速排序，即 不從第一個(gè)開始標(biāo)記。

其它排序

除了以上幾種排序之外，還有歸并排序（MERGE）、統(tǒng)計(jì)排序（COUNT）、基數(shù)排序（RADIX）等。了解詳情請(qǐng)點(diǎn)擊:[visualgo]