JavaScript 數據結構與算法之美 - 歸并排序、快速排序、希爾排序、堆排序

haitiancoder 發布于2019-08-26 10:20 / 3493人閱讀

摘要：之所以把歸并排序快速排序希爾排序堆排序放在一起比較，是因為它們的平均時間復雜度都為。歸并排序是一種穩定的排序方法。因此，快速排序并不穩定。希爾排序思想先將整個待排序的記錄序列分割成為若干子序列。

1. 前言

算法為王。

想學好前端，先練好內功，只有內功深厚者，前端之路才會走得更遠。

筆者寫的 JavaScript 數據結構與算法之美 系列用的語言是 JavaScript ，旨在入門數據結構與算法和方便以后復習。

之所以把歸并排序、快速排序、希爾排序、堆排序放在一起比較，是因為它們的平均時間復雜度都為 O(nlogn)。

請大家帶著問題：快排和歸并用的都是分治思想，遞推公式和遞歸代碼也非常相似，那它們的區別在哪里呢 ? 來閱讀下文。

2. 歸并排序（Merge Sort）

思想

排序一個數組，我們先把數組從中間分成前后兩部分，然后對前后兩部分分別排序，再將排好序的兩部分合并在一起，這樣整個數組就都有序了。

歸并排序采用的是分治思想。

分治，顧名思義，就是分而治之，將一個大問題分解成小的子問題來解決。小的子問題解決了，大問題也就解決了。

注：x >> 1 是位運算中的右移運算，表示右移一位，等同于 x 除以 2 再取整，即 x >> 1 === Math.floor(x / 2) 。

實現

const mergeSort = arr => {
    //采用自上而下的遞歸方法
    const len = arr.length;
    if (len < 2) {
        return arr;
    }
    // length >> 1 和 Math.floor(len / 2) 等價
    let middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle); // 拆分為兩個子數組
    return merge(mergeSort(left), mergeSort(right));
};

const merge = (left, right) => {
    const result = [];

    while (left.length && right.length) {
        // 注意: 判斷的條件是小于或等于，如果只是小于，那么排序將不穩定.
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length) result.push(left.shift());

    while (right.length) result.push(right.shift());

    return result;
};

測試

// 測試
const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.time("歸并排序耗時");
console.log("arr :", mergeSort(arr));
console.timeEnd("歸并排序耗時");
// arr : [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
// 歸并排序耗時: 0.739990234375ms

分析

第一，歸并排序是原地排序算法嗎？

這是因為歸并排序的合并函數，在合并兩個有序數組為一個有序數組時，需要借助額外的存儲空間。
實際上，盡管每次合并操作都需要申請額外的內存空間，但在合并完成之后，臨時開辟的內存空間就被釋放掉了。在任意時刻，CPU 只會有一個函數在執行，也就只會有一個臨時的內存空間在使用。臨時內存空間最大也不會超過 n 個數據的大小，所以空間復雜度是 O(n)。
所以，歸并排序不是原地排序算法。

第二，歸并排序是穩定的排序算法嗎？

merge 方法里面的 left[0] <= right[0] ，保證了值相同的元素，在合并前后的先后順序不變。歸并排序是一種穩定的排序方法。

第三，歸并排序的時間復雜度是多少？

從效率上看，歸并排序可算是排序算法中的佼佼者。假設數組長度為 n，那么拆分數組共需 logn 步, 又每步都是一個普通的合并子數組的過程，時間復雜度為 O(n)，故其綜合時間復雜度為 O(nlogn)。
最佳情況：T(n) = O(nlogn)。
最差情況：T(n) = O(nlogn)。
平均情況：T(n) = O(nlogn)。

動畫

3. 快速排序（Quick Sort）

快速排序的特點就是快，而且效率高！它是處理大數據最快的排序算法之一。

思想

先找到一個基準點（一般指數組的中部），然后數組被該基準點分為兩部分，依次與該基準點數據比較，如果比它小，放左邊；反之，放右邊。

左右分別用一個空數組去存儲比較后的數據。

最后遞歸執行上述操作，直到數組長度 <= 1;

特點：快速，常用。

缺點：需要另外聲明兩個數組，浪費了內存空間資源。

實現

方法一：

const quickSort1 = arr => {
    if (arr.length <= 1) {
        return arr;
    }
    //取基準點
    const midIndex = Math.floor(arr.length / 2);
    //取基準點的值，splice(index,1) 則返回的是含有被刪除的元素的數組。
    const valArr = arr.splice(midIndex, 1);
    const midIndexVal = valArr[0];
    const left = []; //存放比基準點小的數組
    const right = []; //存放比基準點大的數組
    //遍歷數組，進行判斷分配
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < midIndexVal) {
            left.push(arr[i]); //比基準點小的放在左邊數組
        } else {
            right.push(arr[i]); //比基準點大的放在右邊數組
        }
    }
    //遞歸執行以上操作，對左右兩個數組進行操作，直到數組長度為 <= 1
    return quickSort1(left).concat(midIndexVal, quickSort1(right));
};
const array2 = [5, 4, 3, 2, 1];
console.log("quickSort1 ", quickSort1(array2));
// quickSort1: [1, 2, 3, 4, 5]

方法二：

// 快速排序
const quickSort = (arr, left, right) => {
    let len = arr.length,
        partitionIndex;
    left = typeof left != "number" ? 0 : left;
    right = typeof right != "number" ? len - 1 : right;

    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);
    }
    return arr;
};

const partition = (arr, left, right) => {
    //分區操作
    let pivot = left, //設定基準值（pivot）
        index = pivot + 1;
    for (let i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }
    }
    swap(arr, pivot, index - 1);
    return index - 1;
};

const swap = (arr, i, j) => {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
};

測試

// 測試
const array = [5, 4, 3, 2, 1];
console.log("原始array:", array);
const newArr = quickSort(array);
console.log("newArr:", newArr);
// 原始 array: ?[5, 4, 3, 2, 1]
// newArr: ?   [1, 4, 3, 2, 5]

分析

第一，快速排序是原地排序算法嗎？

因為 partition() 函數進行分區時，不需要很多額外的內存空間，所以快排是原地排序算法。

第二，快速排序是穩定的排序算法嗎？

和選擇排序相似，快速排序每次交換的元素都有可能不是相鄰的，因此它有可能打破原來值為相同的元素之間的順序。因此，快速排序并不穩定。

第三，快速排序的時間復雜度是多少？

極端的例子：如果數組中的數據原來已經是有序的了，比如 1，3，5，6，8。如果我們每次選擇最后一個元素作為 pivot，那每次分區得到的兩個區間都是不均等的。我們需要進行大約 n 次分區操作，才能完成快排的整個過程。每次分區我們平均要掃描大約 n / 2 個元素，這種情況下，快排的時間復雜度就從 O(nlogn) 退化成了 O(n²)。
最佳情況：T(n) = O(nlogn)。
最差情況：T(n) = O(n²)。
平均情況：T(n) = O(nlogn)。

動畫

解答開篇問題

快排和歸并用的都是分治思想，遞推公式和遞歸代碼也非常相似，那它們的區別在哪里呢？

可以發現：

歸并排序的處理過程是由下而上的，先處理子問題，然后再合并。

而快排正好相反，它的處理過程是由上而下的，先分區，然后再處理子問題。

歸并排序雖然是穩定的、時間復雜度為 O(nlogn) 的排序算法，但是它是非原地排序算法。

歸并之所以是非原地排序算法，主要原因是合并函數無法在原地執行。

快速排序通過設計巧妙的原地分區函數，可以實現原地排序，解決了歸并排序占用太多內存的問題。

4. 希爾排序（Shell Sort）

思想

先將整個待排序的記錄序列分割成為若干子序列。

分別進行直接插入排序。

待整個序列中的記錄基本有序時，再對全體記錄進行依次直接插入排序。

過程

舉個易于理解的例子：[35, 33, 42, 10, 14, 19, 27, 44]，我們采取間隔 4。創建一個位于 4 個位置間隔的所有值的虛擬子列表。下面這些值是 { 35, 14 }，{ 33, 19 }，{ 42, 27 } 和 { 10, 44 }。

我們比較每個子列表中的值，并在原始數組中交換它們（如果需要）。完成此步驟后，新數組應如下所示。

然后，我們采用 2 的間隔，這個間隙產生兩個子列表：{ 14, 27, 35, 42 }， { 19, 10, 33, 44 }。

我們比較并交換原始數組中的值（如果需要）。完成此步驟后，數組變成：[14, 10, 27, 19, 35, 33, 42, 44]，圖如下所示，10 與 19 的位置互換一下。

最后，我們使用值間隔 1 對數組的其余部分進行排序，Shell sort 使用插入排序對數組進行排序。

實現

const shellSort = arr => {
    let len = arr.length,
        temp,
        gap = 1;
    console.time("希爾排序耗時");
    while (gap < len / 3) {
        //動態定義間隔序列
        gap = gap * 3 + 1;
    }
    for (gap; gap > 0; gap = Math.floor(gap / 3)) {
        for (let i = gap; i < len; i++) {
            temp = arr[i];
            let j = i - gap;
            for (; j >= 0 && arr[j] > temp; j -= gap) {
                arr[j + gap] = arr[j];
            }
            arr[j + gap] = temp;
            console.log("arr  :", arr);
        }
    }
    console.timeEnd("希爾排序耗時");
    return arr;
};

測試

// 測試
const array = [35, 33, 42, 10, 14, 19, 27, 44];
console.log("原始array:", array);
const newArr = shellSort(array);
console.log("newArr:", newArr);
// 原始 array: ??[35, 33, 42, 10, 14, 19, 27, 44]
// arr      : ??[14, 33, 42, 10, 35, 19, 27, 44]
// arr      : ??[14, 19, 42, 10, 35, 33, 27, 44]
// arr      : ??[14, 19, 27, 10, 35, 33, 42, 44]
// arr      : ??[14, 19, 27, 10, 35, 33, 42, 44]
// arr      : ??[14, 19, 27, 10, 35, 33, 42, 44]
// arr      : ??[14, 19, 27, 10, 35, 33, 42, 44]
// arr      : ??[10, 14, 19, 27, 35, 33, 42, 44]
// arr      : ??[10, 14, 19, 27, 35, 33, 42, 44]
// arr      : ??[10, 14, 19, 27, 33, 35, 42, 44]
// arr      : ??[10, 14, 19, 27, 33, 35, 42, 44]
// arr      : ??[10, 14, 19, 27, 33, 35, 42, 44]
// 希爾排序耗時: 3.592041015625ms
// newArr: ?   [10, 14, 19, 27, 33, 35, 42, 44]

分析

第一，希爾排序是原地排序算法嗎？

希爾排序過程中，只涉及相鄰數據的交換操作，只需要常量級的臨時空間，空間復雜度為 O(1) 。所以，希爾排序是原地排序算法。

第二，希爾排序是穩定的排序算法嗎？

我們知道，單次直接插入排序是穩定的，它不會改變相同元素之間的相對順序，但在多次不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，可能導致相同元素相對順序發生變化。
因此，希爾排序不穩定。

第三，希爾排序的時間復雜度是多少？

最佳情況：T(n) = O(n logn)。
最差情況：T(n) = O(n (log(n))²)。
平均情況：T(n) = 取決于間隙序列。

動畫

5. 堆排序（Heap Sort）

堆的定義

堆其實是一種特殊的樹。只要滿足這兩點，它就是一個堆。

堆是一個完全二叉樹。

完全二叉樹：除了最后一層，其他層的節點個數都是滿的，最后一層的節點都靠左排列。

堆中每一個節點的值都必須大于等于（或小于等于）其子樹中每個節點的值。

也可以說：堆中每個節點的值都大于等于（或者小于等于）其左右子節點的值。這兩種表述是等價的。

對于每個節點的值都大于等于子樹中每個節點值的堆，我們叫作大頂堆。
對于每個節點的值都小于等于子樹中每個節點值的堆，我們叫作小頂堆。

其中圖 1 和圖 2 是大頂堆，圖 3 是小頂堆，圖 4 不是堆。除此之外，從圖中還可以看出來，對于同一組數據，我們可以構建多種不同形態的堆。

思想

將初始待排序關鍵字序列 (R1, R2 .... Rn) 構建成大頂堆，此堆為初始的無序區；

將堆頂元素 R[1] 與最后一個元素 R[n] 交換，此時得到新的無序區 (R1, R2, ..... Rn-1) 和新的有序區 (Rn) ，且滿足 R[1, 2 ... n-1] <= R[n]。

由于交換后新的堆頂 R[1] 可能違反堆的性質，因此需要對當前無序區 (R1, R2 ...... Rn-1) 調整為新堆，然后再次將 R[1] 與無序區最后一個元素交換，得到新的無序區 (R1, R2 .... Rn-2) 和新的有序區 (Rn-1, Rn)。不斷重復此過程，直到有序區的元素個數為 n - 1，則整個排序過程完成。

實現

// 堆排序
const heapSort = array => {
    console.time("堆排序耗時");
    // 初始化大頂堆，從第一個非葉子結點開始
    for (let i = Math.floor(array.length / 2 - 1); i >= 0; i--) {
        heapify(array, i, array.length);
    }
    // 排序，每一次 for 循環找出一個當前最大值，數組長度減一
    for (let i = Math.floor(array.length - 1); i > 0; i--) {
        // 根節點與最后一個節點交換
        swap(array, 0, i);
        // 從根節點開始調整，并且最后一個結點已經為當前最大值，不需要再參與比較，所以第三個參數為 i，即比較到最后一個結點前一個即可
        heapify(array, 0, i);
    }
    console.timeEnd("堆排序耗時");
    return array;
};

// 交換兩個節點
const swap = (array, i, j) => {
    let temp = array[i];
    array[i] = array[j];
    array[j] = temp;
};

// 將 i 結點以下的堆整理為大頂堆，注意這一步實現的基礎實際上是：
// 假設結點 i 以下的子堆已經是一個大頂堆，heapify 函數實現的
// 功能是實際上是：找到 結點 i 在包括結點 i 的堆中的正確位置。
// 后面將寫一個 for 循環，從第一個非葉子結點開始，對每一個非葉子結點
// 都執行 heapify 操作，所以就滿足了結點 i 以下的子堆已經是一大頂堆
const heapify = (array, i, length) => {
    let temp = array[i]; // 當前父節點
    // j < length 的目的是對結點 i 以下的結點全部做順序調整
    for (let j = 2 * i + 1; j < length; j = 2 * j + 1) {
        temp = array[i]; // 將 array[i] 取出，整個過程相當于找到 array[i] 應處于的位置
        if (j + 1 < length && array[j] < array[j + 1]) {
            j++; // 找到兩個孩子中較大的一個，再與父節點比較
        }
        if (temp < array[j]) {
            swap(array, i, j); // 如果父節點小于子節點:交換；否則跳出
            i = j; // 交換后，temp 的下標變為 j
        } else {
            break;
        }
    }
};

測試

const array = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2];
console.log("原始array:", array);
const newArr = heapSort(array);
console.log("newArr:", newArr);
// 原始 array: ?[4, 6, 8, 5, 9, 1, 2, 5, 3, 2]
// 堆排序耗時: 0.15087890625ms
// newArr: ?   [1, 2, 2, 3, 4, 5, 5, 6, 8, 9]

分析

第一，堆排序是原地排序算法嗎？

整個堆排序的過程，都只需要極個別臨時存儲空間，所以堆排序是原地排序算法。

第二，堆排序是穩定的排序算法嗎？

因為在排序的過程，存在將堆的最后一個節點跟堆頂節點互換的操作，所以就有可能改變值相同數據的原始相對順序。
所以，堆排序是不穩定的排序算法。

第三，堆排序的時間復雜度是多少？

堆排序包括建堆和排序兩個操作，建堆過程的時間復雜度是 O(n)，排序過程的時間復雜度是 O(nlogn)，所以，堆排序整體的時間復雜度是 O(nlogn)。
最佳情況：T(n) = O(nlogn)。
最差情況：T(n) = O(nlogn)。
平均情況：T(n) = O(nlogn)。

動畫

6. 排序算法的復雜性對比

復雜性對比

算法可視化工具

算法可視化工具 algorithm-visualizer
算法可視化工具 algorithm-visualizer 是一個交互式的在線平臺，可以從代碼中可視化算法，還可以看到代碼執行的過程。

效果如下圖。

旨在通過交互式可視化的執行來揭示算法背后的機制。

算法可視化來源 https://visualgo.net/en

效果如下圖。

https://www.ee.ryerson.ca

illustrated-algorithms

變量和操作的可視化表示增強了控制流和實際源代碼。您可以快速前進和后退執行，以密切觀察算法的工作方式。

7. 文章輸出計劃

JavaScript 數據結構與算法之美 的系列文章，堅持 3 - 7 天左右更新一篇，暫定計劃如下表。

如果有錯誤或者不嚴謹的地方，請務必給予指正，十分感謝。

8. 最后

文中所有的代碼及測試事例都已經放到我的 GitHub 上了。

覺得有用？喜歡就收藏，順便點個贊吧。

參考文章：

JS 實現堆排序

數據結構與算法之美

十大經典排序算法總結（JavaScript 描述）

JS 中可能用得到的全部的排序算法

GPU云服務器云服務器歸并排序算法堆排序算法快速排序算法希爾排序

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/106010.html

JavaScript 數據結構與算法之美 - 十大經典排序算法匯總

摘要：筆者寫的數據結構與算法之美系列用的語言是，旨在入門數據結構與算法和方便以后復習。這應該是目前較為簡單的十大經典排序算法的文章講解了吧。比如原本在的前面，而，排序之后，在的后面十大經典排序算法冒泡排序思想冒泡排序只會操作相鄰的兩個數據。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言算法為王。想學好前端，先練好內功，內功不行，就...

zsy888 2019-08-26 10:27 評論0 收藏0
JavaScript 數據結構與算法之美 - 冒泡排序、插入排序、選擇排序

摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因為它們的平均時間復雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩定的排序算法。選擇排序思路選擇排序算法的實現思路有點類似插入排序，也分已排序區間和未排序區間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言算法為王。想學好前端，先練好內功，...

canger 2019-08-26 10:15 評論0 收藏0
優秀程序員都應該學習的 GitHub 上開源的數據結構與算法項目

摘要：強烈推薦上值得前端學習的數據結構與算法項目，包含圖的演示過程與視頻講解。該倉庫包含了多種基于的算法與數據結構，提供進一步閱讀的解釋和鏈接。數據結構和算法必知必會的個代碼實現。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言算法為王。想學好前端，先練好內功，內功不行，就算招式練的再花哨，終究成不了高手；只有內功深厚者，前端之路才會走得...

cheukyin 2019-08-26 10:17 評論0 收藏0
JavaScript 數據結構與算法之美 - 桶排序、計數排序、基數排序

摘要：之所以把計數排序桶排序基數排序放在一起比較，是因為它們的平均時間復雜度都為。動畫計數排序思想找出待排序的數組中最大和最小的元素。桶排序計數排序能派上用場嗎手機號碼有位，范圍太大，顯然不適合用這兩種排序算法。 showImg(https://segmentfault.com/img/bVbuF9e?w=900&h=500); 1. 前言算法為王。想學好前端，先練好內功，只有內功深厚者...

Awbeci 2019-08-26 10:24 評論0 收藏0