摘要：本文對一些排序算法進行了簡單分析，并給出了的代碼實現(xiàn)。平均時間復(fù)雜度不好分析，它是冒泡排序是穩(wěn)定的排序算法。冒泡排序是原地排序算法原地排序指的是空間復(fù)雜度是的排序算法。歸并排序，會將數(shù)組從中間分成左右兩部分。

本文對一些排序算法進行了簡單分析，并給出了 javascript 的代碼實現(xiàn)。因為本文包含了大量的排序算法，所以分析不會非常詳細，適合有對排序算法有一定了解的同學(xué)。
本文內(nèi)容其實不是很多，就是代碼占了很多行。

默認需要排序的數(shù)據(jù)結(jié)構(gòu)為數(shù)組，時間復(fù)雜度為平均時間復(fù)雜度。

下面代碼實現(xiàn)，排序默認都是 從小到大 排序。

我的 js 代碼實現(xiàn)都放在 github：https://github.com/F-star/js-...

代碼僅供參考。

假設(shè)要進行冒泡排序的數(shù)據(jù)長度為 n。

冒泡排序會進行多次的冒泡操作，每次都會相鄰數(shù)據(jù)比較，如果前一個數(shù)據(jù)比后一個數(shù)據(jù)大，就交換它們的位置（即讓大的數(shù)據(jù)放在后面）。這樣每次交換，至少有一個元素會移動到排序后應(yīng)該在的位置。重復(fù)冒泡 n（或者說 n-1） 次，就完成了排序。

詳細來說，第 i（i 從 0 開始） 趟冒泡會對數(shù)組的前 n - i 個元素進行比較和交換操作，要對比的次數(shù)是 size - i - 1。

冒泡排序總共要進行 n-1 次冒泡（當(dāng)然你可以說是 n 次冒泡，不過最后一次冒泡只有一個元素，不用進行比較）。

有時候，可能只進行了 n 次冒泡，數(shù)組就已經(jīng)是有序的了，甚至數(shù)組本來就是有序的。這時候我們希望：當(dāng)發(fā)現(xiàn)一次冒泡后，數(shù)組有序，就停止下一次的冒泡，返回當(dāng)前的數(shù)組。

這時候我們可以在每一趟的冒泡前，聲明一個變量 exchangeFlag，將其設(shè)置為 true。冒泡過程中，如果發(fā)生了數(shù)據(jù)交換，就將 exchangeFlag 設(shè)置為 false。結(jié)束一趟冒泡后，我們就可以通過 exchangeFlag 知道 數(shù)據(jù)是否發(fā)生過交換。如果沒有發(fā)生交換，就說明數(shù)組有序，直接返回該數(shù)組即可；否則說明還沒有排好序，繼續(xù)下一趟冒泡。

const bubbleSort = (a) => {
    // 每次遍歷找到最大（?。┑臄?shù)放到最后面的位置。
    // 優(yōu)化：如果某次冒泡操作沒有數(shù)據(jù)交換，說明已經(jīng)有序了。

    // 雙重循環(huán)。
    if (a.length <= 1) return a;
    // 這里的 i < len 改成 i < len - 1 也是正確的，因為最后第 len - 1次并不會執(zhí)行。
    for (let i = 0, len = a.length; i < len; i++) {
        let exchangeFlag = false;   // 是否發(fā)生過換
        for (let j = 0; j < len - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                [a[j], a[j + 1]] = [a[j + 1], a[j]];
                exchangeFlag = true;
            }
            
        }
        console.log(a)
        if (exchangeFlag == false) return a;
    }
}

// 測試
let array = [199, 3, 1, 2, 8, 21,4, 100, 8];
console.log (bubbleSort(array));

最好時間復(fù)雜度是 O(n)，即第一趟進行 n-1 次比較后，發(fā)現(xiàn)原數(shù)組是有序的，結(jié)束冒泡。

最壞時間復(fù)雜度是 O(n^2)，當(dāng)原數(shù)組剛好是倒序排列時，即需要進行 n 次冒泡，要進行 (n-1) + (n-2) ... + 1 次比較后，用等比數(shù)列求和公式求和后并化簡，即可求出最壞時間復(fù)雜度。

平均時間復(fù)雜度不好分析，它是 O(n^2)

這里的“穩(wěn)定”指的是：排序后，值相等的數(shù)據(jù)的前后順序保持不變。

相鄰數(shù)據(jù)如果相等，不交換位置即可。

原地排序指的是空間復(fù)雜度是 O(1) 的排序算法。

冒泡排序只做了相鄰數(shù)據(jù)交換，另外有兩個臨時變量（交換時的臨時變量、flag），只需要常量級的臨時空間，空間復(fù)雜度為 O(1)

插入排序。本質(zhì)是從 未排序的區(qū)域 內(nèi)取出數(shù)據(jù)，放到 已排序區(qū)域 內(nèi)，這個取出的數(shù)據(jù)會和已排序的區(qū)間內(nèi)數(shù)據(jù)一一對比，找到正確的位置插入。

我們直接將數(shù)組分為 已排序區(qū)域 和 未排序區(qū)域。剛開始開始，已排序區(qū)域只有一個元素，即數(shù)組的第一個元素。插入的方式有兩種：從前往后查找插入 和 從后往前查找插入。這里我選擇 從后往前查找插入。

const insertionSort = a => {
    for (let i = 0, len = a.length; i < len; i++) {
        let curr = a[i];     // 存儲當(dāng)前值，排序的時候，它對應(yīng)的索引指向的值可能會在排序時被覆蓋
        for (let j = i - 1; j >= 0;j--) {
            if (curr < a[j]) {
                a[j + 1] = a[j];
            } else {
                break;
            }
            // 找到位置（0 或 curr >= a[j]時）
            a[j] = curr;
        }
    } 
    return a;
}

當(dāng)要排序的數(shù)據(jù)是有序的，我們每次插入已排序的區(qū)域，只需要比較一次，一共比較 n-1 次就結(jié)束了（注意這里是從后往前遍歷已排序區(qū)域）。所以最好時間復(fù)雜度為 O(n)。

最壞時間復(fù)雜度是 O(n^2)，是數(shù)據(jù)剛好是倒序的情況，每次都要遍歷完 已排序區(qū)域的所有數(shù)據(jù)。

遍歷已排序區(qū)域時，值相同的時候，放到最后的位置即可。

不需要額外空間，是在數(shù)組上進行數(shù)據(jù)交換，所以插入排序是原地排序算法。

選擇排序也有一個 已排序區(qū)域 和一個 未排序區(qū)域。它和插入排序不同的地方在于：選擇排序是從 未排序區(qū)域 中找出最小的值，放到 已排序區(qū)域的末尾。

為了減少內(nèi)存消耗，我們也是直接在數(shù)組上進行數(shù)據(jù)的交換。

插入排序和冒泡排序的時間復(fù)雜度都是 O(n^2)，元素交換次數(shù)也相同，但插入排序更優(yōu)秀。原因是冒泡排序的交換，需要一個 tmp 的中間變量，來進行兩個元素交換，這就變成了 3 個賦值操作。而插入排序（從后往前遍歷已排序區(qū)域），不需要中間遍歷，它是直接一些元素后移覆蓋，只要1個賦值操作。

冒泡排序中數(shù)據(jù)的交換操作：
if (a[j] > a[j+1]) { // 交換
   int tmp = a[j];
   a[j] = a[j+1];
   a[j+1] = tmp;
   flag = true;
}
 
插入排序中數(shù)據(jù)的移動操作：
if (a[j] > value) {
  a[j+1] = a[j];  // 數(shù)據(jù)移動
} else {
  break;
}

此外，插入排序還可以進行優(yōu)化，變成 希爾排序。這里不具體說。

const selectionSort = a => {
    let tmp;
    for (let i = 0, len = a.length; i < len; i++) {

        let min = a[i],     // 保存最小值，用于比較大小。
            minIndex = i;   // 保存未排序區(qū)間中，最小值對應(yīng)的索引（方便進行元素交換）
        for (let j = i; j < len; j++) {
            if (a[j] < min) {
                minIndex = j;
                min =a[j]
            }
        }
        tmp = a[minIndex];
        a[minIndex] = a[i];
        a[i] = tmp;
    }
    return a;
}

最好時間復(fù)雜度是 O(n^2)。因為每次從未排序區(qū)域內(nèi)找出最小值，都要遍歷未排序區(qū)域內(nèi)的所有元素，一共要查找 n-1 次，所以時間復(fù)雜度是 O(n^2)。

最壞時間復(fù)雜度也是 O(n^2)，理由同上。

我們找到為排序區(qū)域的最小元素，會交換該元素和 排序區(qū)域的下一個位置的元素（即排序區(qū)域的第一個元素），然后 i 后移。只做了元素的交換，且只用到了常數(shù)級的內(nèi)存空間（交換兩個數(shù)據(jù)需要的一個臨時遍歷），因此選擇排序是原地排序算法。

不穩(wěn)定，是因為每次都要找最小值和前面的元素進行交換，這樣會破壞穩(wěn)定性。舉個反例來證明：3 3 2, 第一次交換后，為 2 3 3，此時兩個 3 的相對順序就改變了。

當(dāng)然你可以額外的創(chuàng)建一個大小為數(shù)組長度的空數(shù)組，來作為 已排序區(qū)域。這樣做就不需要交換元素，可以做到排序穩(wěn)定，但這樣做耗費了額外的內(nèi)存，變成了非原地排序算法。

歸并排序用到了 分治思想。分治思想的核心是：將一個大問題分解成多個小的問題，解決后合并為原問題。分治通常用遞歸來實現(xiàn)。分治和遞歸的區(qū)別是，分治是一種解決問題的處理思想，遞歸是一種編程技巧。

歸并排序，會將數(shù)組從中間分成左右兩部分。然后對這兩個部分各自繼續(xù)從中間分成兩部分，直到無法再分。然后將分開的兩部分進行排序合并（合并后數(shù)組有序），不停地往上排序合并，最終合并成一個有序數(shù)組。

說明下 merge 函數(shù)。它是將兩個有序數(shù)組合并為一個有序數(shù)組，做法是創(chuàng)建一個空數(shù)組，長度為兩個有序數(shù)組的大的一個。設(shè)置指針 i 和 j 分指向兩個數(shù)組的第一個元素，取其中小的加入數(shù)組，對應(yīng)的數(shù)組的指針后移。重復(fù)上面這個過程，直到一個數(shù)組為空，就將另一個數(shù)組的剩余元素都推入新數(shù)組。

另外，merge() 函數(shù)可以借助 哨兵 進行優(yōu)化處理。具體我沒研究，有空再考慮實現(xiàn)。

歸并的代碼實現(xiàn)用到了遞歸，所以代碼不是很好看懂。

const mergeSort = a => {
    mergeSortC(a, 0, a.length - 1)
    return a;
}

const mergeSortC = (a, p, r) => {
    if (p >= r) return
    let q = Math.floor( (p + r) / 2 ); // 這樣取中間值，right.length >= left.length
    mergeSortC(a, p, q);
    mergeSortC(a, q+1, r);
    merge(a, p, q, r)  // p->q （q+1）->r 區(qū)域的兩個數(shù)組合并。
}

/**
 * merge方法（將兩個有序數(shù)組合并成一個有序數(shù)組）
 */
function merge(a, p, q, r) {
    let i = p,
        j = q+1,
        m = new Array(r - q);    // 保存合并數(shù)據(jù)的數(shù)組
    
    let k = 0;
    while (i <= q && j <= r) {
        if (a[i] <= a[j]) {
            m[k] = a[i];
            i++;
        } else {
            m[k] = a[j]
            j++;
        }
        k++;
    }

    // 首先找出兩個數(shù)組中，有剩余的元素的數(shù)組。
    // 然后將剩余元素依次放入數(shù)組 m。
    let start = i,
        end = q;
    if (j <= r) {
        start = j;
        end = r;
    }

    while (start <= end) {
        m[k] = a[start];
        start++;
        k++;
    }
    // m的數(shù)據(jù)拷貝到 a。
    for(let i = p; i <= r; i++) {
        a[i] = m[i-p];
    }
}

以下為簡單推導(dǎo)過程，摘自 專欄-「數(shù)據(jù)結(jié)構(gòu)與算法之美」。

問題a分解為子問題 b 和 c，設(shè)求解 a、b、c 的時間為 T(a)、T(b)、Y(c)，則有

T(a) = T(b) + T(c) + K

而合并兩個有序子數(shù)組的時間復(fù)雜度是 O(n)，于是有

T(1) = C；   n=1 時，只需要常量級的執(zhí)行時間，所以表示為 C。
T(n) = 2*T(n/2) + n； n>1

化簡后，得到 T(n)=Cn+nlog2n。所以歸并排序的時間復(fù)雜度是 O(nlogn)。

歸并交換元素的情況發(fā)生在 合并 過程，只要讓比較左右兩個子數(shù)組時發(fā)現(xiàn)相等時，取左邊數(shù)組的元素，就可以保證有序了。

依然歸并排序非常優(yōu)秀（指時間復(fù)雜度），但，它的空間復(fù)雜度是 O(n)。因為進行合并操作時，需要申請一個臨時數(shù)組，該數(shù)組的長度最大不會超過 n。

快速排序，簡稱 “快排”?？炫攀褂玫氖欠謪^(qū)思想。

快排會取數(shù)組中的一個元素作為 pivot（分區(qū)點），將數(shù)組分為三部分：

小于 pivot 的部分

pivot

大于或等于 pivot 的部分。

我們?nèi)∽笥覂蛇叺淖訑?shù)組，執(zhí)行和上面所說的操作，直到區(qū)間縮小為0，此時整個數(shù)組就變成有序的了。

在歸并排序中，我們用到一個 merge() 合并函數(shù)，而在快排中，我們也有一個 partition() 分區(qū)方法。該方法的作用是根據(jù)提供的區(qū)間范圍，隨機取一個 pivot，將該區(qū)間的數(shù)組的數(shù)據(jù)進行交換，最終將小于 pivot 的放左邊，大于 pivot 的放右邊，然后返回此時 pivot 的下標(biāo)，作為下一次 遞歸 的參考點。

partition() 分區(qū)函數(shù)有一種巧妙的實現(xiàn)方式，可以實現(xiàn)原地排序。處理方式有點類似 選擇排序。首先我們選一個 pivot，pivot 后的元素全都往前移動一個單位，然后pivot 放到末尾。接著我們將從左往右遍歷數(shù)組，如果元素小于 pivot，就放入 “已處理區(qū)域”，具體操作就是類似插入操作那種，進行直接地交換；如果沒有就不做操作，繼續(xù)下一個元素，直到結(jié)束。最后將 pivot 也放 “已處理區(qū)間”。這樣就實現(xiàn)了原地排序了。

另外，對 partition 進行適當(dāng)?shù)母脑?，就可以實現(xiàn) “查找無序數(shù)組內(nèi)第k大元素” 的算法。

const quickSort = a => {
    quickSortC(a, 0, a.length - 1)
    return a;
}

/**
 * 遞歸函數(shù)
 * 參數(shù)意義同 partition 方法。
 */
function quickSortC(a, q, r) {
    if (q >= r) {
        // 提供的數(shù)組長度為1時，結(jié)束迭代。
        return a;
    }
    let p = partition(a, q, r);
    quickSortC(a, q, p - 1);
    quickSortC(a, p + 1, r);
}

/**
 * 隨機選擇一個元素作為 pivot，進行原地分區(qū)，最后返回其下標(biāo)
 * 
 * @param {Array} a 要排序的數(shù)組
 * @param {number} p 起始索引
 * @param {number} r 結(jié)束索引
 * @return 基準(zhǔn)的索引值，用于后續(xù)的遞歸。
 */
export function partition(a, p, r) {
    // pivot 默認取最后一個，如果取得不是最后一個，就和最后一個交換位置。
    let pivot = a[r],
        tmp,
        i = p;     // 已排序區(qū)間的末尾索引。
    // 類似選擇排序，把小于 pivot 的元素，放到 已處理區(qū)間
    for (; p < r; p++) {
        if (a[p] < pivot) {
            // 將 a[i] 放到 已處理區(qū)間。
            tmp = a[p];
            a[p] = a[i];
            a[i] = tmp;    // 這里可以簡寫為 [x, y] = [y, x]
            i++;
        }
    }

    // 將 pivot（即a[r]）也放進 已處理區(qū)間
    tmp = a[i];
    a[i] = a[r];
    a[r] = tmp;   
    return i;   
}

快速排序和歸并排序都用到了分治思想，遞推公式和遞歸代碼很很相似。它們的區(qū)別在于：歸并排序是 由下而上 的，排序的過程發(fā)生在子數(shù)組合并過程。而快速排序是 由上而下 的，分區(qū)的時候，數(shù)組就開始趨向于有序，直到最后區(qū)間長度為1，數(shù)組就變得有序。

快排的時間復(fù)雜度遞推求解公式跟歸并是相同的。所以，快排的時間復(fù)雜度也是 O(nlogn)。但這個公式成立的前提是每次分區(qū)都能正好將區(qū)間平分（即最好時間復(fù)雜度）。

當(dāng)然平均復(fù)雜度也是 O(nlongn)，不過不好推導(dǎo)，就不分析。

極端情況下，數(shù)組的數(shù)據(jù)已經(jīng)有序，且取最后一個元素為 pivot，這樣的分區(qū)是及其不均等的，共需要做大約 n 次的分區(qū)操作，才能完成快排。每次分區(qū)平均要掃描約 n/2 個元素。所以，快排的最壞時間復(fù)雜度是 O(n^2)

快速排序的分區(qū)過程，涉及到了交換操作，該交換操作類似 選擇排序，是不穩(wěn)定的排序。

為了實現(xiàn)原地排序，我們前面對 parition 分區(qū)函數(shù)進行了巧妙的處理。

大概就是這樣，做了簡單的總結(jié)。如果文章有錯誤的地方，請給我留言。

還有一些排序打算下次再更新，可能會新開一篇文章，也可能直接修改這篇文章。

數(shù)據(jù)結(jié)構(gòu)與算法之美