數據結構與演算法排序

1. 數據結構與演算法--堆和堆排序

堆排序是一種原地的、時間復雜度為 O(nlogn) 的排序演算法。

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

對於每個節點的值都大於等於子樹中每個節點值的堆，我們叫做 「大頂堆」 。對於每個節點的值都小於等於子樹中每個節點值的堆，我們叫做 「小頂堆」 。

完全二叉樹比較適合用數組來存儲。用數組來存儲完全二叉樹是非常節省存儲空間的。下標可以直接計算出左右字數的下標。（數組中下標為 i 的節點，左子節點下標為 i∗2 ，右子節點下標為 i∗2+1，父節點的下標為 i/2​ 。）

如果我們把新插入的元素放到堆的最後，你可以看我畫的這個圖，是不是不符合堆的特性了？於是，我們就需要進行調整，讓其重新滿足堆的特性，這個過程我們起了一個名字，就叫做 堆化（heapify） 。
堆化實際上有兩種，從下往上和從上往下。這里我先講從下往上的堆化方法。
堆化非常簡單，就是順著節點所在的路徑，向上或者向下，對比，然後交換。

我們把最後一個節點放到堆頂，然後利用同樣的父子節點對比方法。對於不滿足父子節點大小關系的，互換兩個節點，並且重復進行這個過程，直到父子節點之間滿足大小關系為止。這就是 從上往下的堆化方法 。

一個包含 n 個節點的完全二叉樹，樹的高度不會超過 log2​n。堆化的過程是順著節點所在路徑比較交換的，所以堆化的時間復雜度跟樹的高度成正比，也就是 O(logn)。插入數據和刪除堆頂元素的主要邏輯就是堆化，所以，往堆中插入一個元素和刪除堆頂元素的時間復雜度都是 O(logn)。

這里我們藉助於堆這種數據結構實現的排序演算法，就叫做堆排序。這種排序方法的時間復雜度非常穩定，是 O(nlogn)，並且它還是原地排序演算法。

從後往前處理數組，並且每個數據都是從上往下堆化。
因為葉子節點往下堆化只能自己跟自己比較，所以我們直接從最後一個非葉子節點開始，依次堆化就行了。

建堆的時間復雜度就是 O(n)。 推導過程見 極客時間--數據結構與演算法之美

建堆結束之後，數組中的數據已經是按照大頂堆的特性來組織的。數組中的第一個元素就是堆頂，也就是最大的元素。我們把它跟最後一個元素交換，那最大元素就放到了下標為 n 的位置。
這個過程有點類似上面講的「刪除堆頂元素」的操作，當堆頂元素移除之後，我們把下標為 n 的元素放到堆頂，然後再通過堆化的方法，將剩下的 n−1 個元素重新構建成堆。堆化完成之後，我們再取堆頂的元素，放到下標是 n−1 的位置，一直重復這個過程，直到最後堆中只剩下標為 1 的一個元素，排序工作就完成了。

整個堆排序的過程，都只需要極個別臨時存儲空間，所以堆排序是原地排序演算法。堆排序包括建堆和排序兩個操作，建堆過程的時間復雜度是 O(n)，排序過程的時間復雜度是 O(nlogn)，所以，堆排序整體的時間復雜度是 O(nlogn)。
堆排序不是穩定的排序演算法，因為在排序的過程，存在將堆的最後一個節點跟堆頂節點互換的操作，所以就有可能改變值相同數據的原始相對順序。

堆這種數據結構幾個非常重要的應用：優先順序隊列、求 Top K 和求中位數。

假設我們有 100 個小文件，每個文件的大小是 100MB，每個文件中存儲的都是有序的字元串。我們希望將這些 100 個小文件合並成一個有序的大文件。這里就會用到優先順序隊列。
這里就可以用到優先順序隊列，也可以說是堆。我們將從小文件中取出來的字元串放入到小頂堆中，那堆頂的元素，也就是優先順序隊列隊首的元素，就是最小的字元串。我們將這個字元串放入到大文件中，並將其從堆中刪除。然後再從小文件中取出下一個字元串，放入到堆中。循環這個過程，就可以將 100 個小文件中的數據依次放入到大文件中。

我們可以用優先順序隊列來解決。我們按照任務設定的執行時間，將這些任務存儲在優先順序隊列中，隊列首部（也就是小頂堆的堆頂）存儲的是最先執行的任務。

如何在一個包含 n 個數據的數組中，查找前 K 大數據呢？我們可以維護一個大小為 K 的小頂堆，順序遍歷數組，從數組中取出數據與堆頂元素比較。如果比堆頂元素大，我們就把堆頂元素刪除，並且將這個元素插入到堆中；如果比堆頂元素小，則不做處理，繼續遍歷數組。這樣等數組中的數據都遍歷完之後，堆中的數據就是前 K 大數據了。

中位數，顧名思義，就是處在中間位置的那個數。
使用兩個堆：一個大頂堆， 一個小頂堆。 小頂堆中的數據都大於大頂堆中的數據。
如果新加入的數據小於等於大頂堆的堆頂元素，我們就將這個新數據插入到大頂堆；否則，我們就將這個新數據插入到小頂堆。
也就是說，如果有 n 個數據，n 是偶數，我們從小到大排序，那前 2n​ 個數據存儲在大頂堆中，後 2n​ 個數據存儲在小頂堆中。這樣，大頂堆中的堆頂元素就是我們要找的中位數。如果 n 是奇數，情況是類似的，大頂堆就存儲 2n​+1 個數據，小頂堆中就存儲 2n​ 個數據。

極客時間--數據結構與演算法之美--28 | 堆和堆排序：為什麼說堆排序沒有快速排序快？

2. 數據結構-八大排序超詳解（附動圖+實現詳解+總結）

數據結構八大排序超詳解：

1. 插入排序：

   • 特點：逐個將元素插入到已排序的部分中，穩定排序。
   • 時間復雜度：O。
   • 空間復雜度：O。
   • 適用場景：適用於少量數據的排序或輸入數組基本有序的情況。

2. 希爾排序：

   • 特點：插入排序的改進版，通過引入gap來加快排序速度，但不保證穩定。
   • 時間復雜度：約為O，難以精確計算。
   • 空間復雜度：O。
   • 適用場景：作為插入排序的改進，適用於中等規模數據的排序。

3. 選擇排序：

   • 特點：每次從未排序部分選擇最小的元素放到已排序部分的末尾，不穩定排序。
   • 時間復雜度：O。
   • 空間復雜度：O。
   • 適用場景：數據規模較小且對穩定性無要求時。

4. 堆排序：

   • 特點：利用堆數據結構進行排序，平均時間復雜度為O，不保證穩定。
   • 時間復雜度：O。
   • 空間復雜度：O。
   • 適用場景：需要快速排序且對穩定性無要求的大規模數據。

5. 冒泡排序：

   • 特點：通過相鄰元素的比較和交換來排序，穩定排序。
   • 時間復雜度：O。
   • 空間復雜度：O。
   • 適用場景：數據規模較小且對穩定性有要求時。

6. 快速排序：

   • 特點：分治法的典範，平均時間復雜度為O，最壞情況下退化到O，空間復雜度為O，不穩定。
   • 時間復雜度：平均O，最壞O。
   • 空間復雜度：O。
   • 適用場景：大規模數據的快速排序，但對穩定性無要求。

7. 歸並排序：

   • 特點：分治法的另一種實現，穩定排序，空間復雜度為O。
   • 時間復雜度：O。
   • 空間復雜度：O。
   • 適用場景：需要穩定排序且對空間開銷有一定容忍度的大規模數據。

8. 計數排序：

   • 特點：在特定條件下時間復雜度為O，但需要額外的空間來存儲計數信息，且受限於數據范圍。
   • 時間復雜度：O。
   • 空間復雜度：O。
   • 適用場景：數據范圍有限且需要高效排序時。

總結：八大排序演算法各有其優勢和適用場景，在實際編程中應根據具體需求選擇合適的排序演算法。從基礎到高效，從穩定到不穩定，這些排序演算法共同構成了數據結構中的排序樂章。