摘要：假設(shè)要對(duì)數(shù)組進(jìn)行歸并排序，步驟是先將劃分為兩個(gè)數(shù)組和即把數(shù)組從中間分開(kāi)再分別對(duì)數(shù)組重復(fù)步驟的操作，逐步劃分，直到不能再劃分為止每個(gè)子數(shù)組只剩下一個(gè)元素，這樣，劃分的過(guò)程就結(jié)束了。

算法描述：

從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序

取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描

如果該元素（已排序）大于新元素，將該元素移到下一位置

重復(fù)步驟 3，直到找到已排序的元素小于或者等于新元素的位置

將新元素插入到該位置后

重復(fù)步驟 2~5

var arr = [5, 6, 3, 1, 8, 7, 2, 4];
for(let i = 1;i= 0 ; j -- ){
        console.log("單次比較數(shù)據(jù)："+arr[myIndex]+"---"+arr[j])
        if(arr[myIndex] < arr[j]){
            [arr[myIndex],arr[j]] = [arr[j],arr[myIndex]];
            myIndex = j;
        }else{
          break;
        }
        console.log("數(shù)組"+arr);
    }
}

時(shí)間復(fù)雜度 O(n^2)
運(yùn)行過(guò)程

算法描述

直接從待排序數(shù)組中選擇一個(gè)最小（或最大）數(shù)字，放入新數(shù)組中。

假定第一個(gè)數(shù)字是最小的，然后依次和后面的比較，哪個(gè)小哪個(gè)就記錄當(dāng)前那個(gè)的下標(biāo)。

記錄完下標(biāo)了之后替換第一個(gè)和那個(gè)最小數(shù)字的位置

依次執(zhí)行上述步驟，只不過(guò)最小的位置依次累加

var arr = [5, 6, 3, 1, 8, 7, 2, 4];
for(let i = 0; i < arr.length - 1;i++){
    console.log("次數(shù)"+Number(i+1))
    let minIndex = i;
    for(let j = i ;j < arr.length - 1; j++){
         console.log("單次比較數(shù)據(jù):"+arr[minIndex]+"---"+arr[j+1])
         if(arr[minIndex] > arr[j+1]){
            minIndex = j+1;
         }
    }
    [arr[minIndex],arr[i]] = [arr[i],arr[minIndex]];
    console.log("數(shù)組"+arr);

}

時(shí)間復(fù)雜度 O(n^2)

運(yùn)行過(guò)程

就幾種算法來(lái)看，感覺(jué)冒泡是比較慢的

算法描述：

比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。

對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。

針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

var arr = [5, 6, 3, 1, 8, 7, 2, 4];
let count = 0;
for(let i = arr.length ; i > 0; i --){
    console.log("次數(shù)"+i);
    for(let j = 1; j < i; j ++){
        console.log("單次比較數(shù)據(jù):"+arr[j]+"----"+arr[j-1])
        if(arr[j] < arr[j-1]){
            [arr[j],arr[j-1]] = [arr[j-1],arr[j]]
        }
    }
    console.log(arr);
}

時(shí)間復(fù)雜度 O(n^2)

運(yùn)行過(guò)程

歸并排序的圖可能一下看不懂，是因?yàn)閳D代表的是運(yùn)行的過(guò)程,主要看算法描述

歸并排序：其基本思想是分治策略，先進(jìn)行劃分，然后再進(jìn)行合并。
假設(shè)要對(duì)數(shù)組C進(jìn)行歸并排序，步驟是：
1.先將C劃分為兩個(gè)數(shù)組A和B（即把數(shù)組C從中間分開(kāi)）
2.再分別對(duì)數(shù)組A、B重復(fù)步驟1的操作，逐步劃分，直到不能再劃分為止(每個(gè)子數(shù)組只剩下一個(gè)元素)，這樣，劃分的過(guò)程就結(jié)束了。
如： [12 20 30 21 15 33 26 19 40 25]
劃分為: [12 20 30 21 15] [33 26 19 40 25]

       [12 20]      [30 21 15]       [33 26]       [19 40 25]
     [12]  [20]   [30]  [21 15]     [33]  [26]    [19]    [40 25]
     [12]  [20]   [30] [21] [15]    [33]  [26]    [19]   [40] [25]

3.然后從下層往上層不斷合并數(shù)組，每一層合并相鄰的兩個(gè)子數(shù)組，合并的過(guò)程是每次從待合并的兩個(gè)子數(shù)組中選取一個(gè)最小的元素，然后把這個(gè)元素放到合并后的數(shù)組中，不斷重復(fù)直到把兩個(gè)子數(shù)組的元素都放到合并后的數(shù)組為止。
4.依次類推，直到合并到最上層結(jié)束，這時(shí)數(shù)據(jù)的排序已經(jīng)完成了。

var arr = [5, 6, 3, 1, 8, 7, 2, 4,9];
function mergeSort(arr){
    if(arr.length === 1){
        return arr;
    }
    let midIndex = Math.floor(arr.length / 2);
    let leftArr = arr.slice(0,midIndex);
    let rightArr = arr.slice(midIndex);
    console.log("拆分?jǐn)?shù)組"+leftArr+"------"+rightArr)
    return mergeFn(mergeSort(leftArr),mergeSort(rightArr));
}.
function mergeFn(left,right){
    let tmp = [];
    console.log(left + "----" + right);
    while (left.length && right.length) {
        console.log("單次比較數(shù)據(jù)："+left[0]+"和"+right[0]+"誰(shuí)小誰(shuí)所在的數(shù)組就被shift掉一個(gè)")
        if (left[0] < right[0]){
          tmp.push(left.shift());
        }
        else{
          tmp.push(right.shift());
        }
        console.log(tmp);
    }
    let arra = tmp.concat(left, right);
    console.log("本次比較完畢:"+arra);

    return arra;

}
mergeSort(arr);

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

運(yùn)行過(guò)程，看了運(yùn)行過(guò)程就能看懂圖了，也知道js函數(shù)里的參數(shù)有函數(shù)的情況下的執(zhí)行順序是自左向右

圖上的運(yùn)行方式是按照基準(zhǔn)是第0號(hào)位算的，看起來(lái)稍微有點(diǎn)亂，不過(guò)只要知道快排是怎么算的就好了

算法描述：

在數(shù)據(jù)集之中，選擇一個(gè)元素作為”基準(zhǔn)”（pivot）。

所有小于”基準(zhǔn)”的元素，都移到”基準(zhǔn)”的左邊；所有大于”基準(zhǔn)”的元素，都移到”基準(zhǔn)”的右邊。這個(gè)操作稱為分區(qū) (partition)操作，分區(qū)操作結(jié)束后，基準(zhǔn)元素所處的位置就是最終排序后它的位置。

對(duì)”基準(zhǔn)”左邊和右邊的兩個(gè)子集，不斷重復(fù)第一步和第二步，直到所有子集只剩下一個(gè)元素為止。

var arr = [5, 6, 3, 1, 8, 7, 2, 4];
function quickSort(arr){
    if(arr.length <= 1){
        return arr;
    }
    //找基準(zhǔn)
    let midIndex = Math.floor(arr.length/2);
    //剔除基準(zhǔn)值
    let midNum = arr.splice(midIndex,1)[0];
    console.log("基準(zhǔn)值:"+midNum);
    let leftArr = [],rightArr=[];
    for(let i = 0 ; i < arr.length; i++){
        //小于基準(zhǔn)的進(jìn)左邊，大于的進(jìn)右邊
        arr[i] < midNum ? leftArr.push(arr[i]) : rightArr.push(arr[i])
    }
    console.log("小于基準(zhǔn)值的數(shù)組："+leftArr);
    console.log("大于基準(zhǔn)值的數(shù)組:"+rightArr);
    return quickSort(leftArr).concat(midNum,quickSort(rightArr));
}
quickSort(arr);

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

運(yùn)行過(guò)程

這個(gè)運(yùn)行過(guò)程是按照基準(zhǔn)為0號(hào)位算的；

可以看到，快速排序和歸并排序是比較快。而且快排更容易理解更好寫(xiě)一些。