算法與數據結構是計算機學習路上的內功心法，也是學好編程語言的重要基礎。今天給大家介紹一下十大經典算法。

十大經典算法分別是：冒泡排序，插入排序，選擇排序，希爾排序，快速排序，歸并排序，桶排序，堆排序，計數排序，基數排序。

預備知識：算法穩定性

如果 a==b，排序前 a 在 b 的前面，排序后 a 在 b 的后面，只要會出現這種現象，我們則說這個算法不穩定（即使兩個相等的數，在排序的過程中不斷交換，有可能將后面的 b 交換到 a 的前面去）。

一、冒泡排序

冒泡排序（Bubble Sort）是基于交換的排序，它重復走過需要排序的元素，依次比較相鄰的兩個元素的大小，保證最后一個數字一定是最大的，即它的順序已經排好，下一輪只需要保證前面 n-1 個元素的順序即可。

之所以稱為冒泡，是因為最大/最小的數，每一次都往后面冒，就像是水里面的氣泡一樣。

排序的步驟如下：

從頭開始，比較相鄰的兩個數，如果第一個數比第二個數大，那么就交換它們位置。

從開始到最后一對比較完成，一輪結束后，最后一個元素的位置已經確定。

除了最后一個元素以外，前面的所有未排好序的元素重復前面兩個步驟。

重復前面 1 ～ 3 步驟，直到都已經排好序。

例如，我們需要對數組 [98，90，34，56，21] 進行從小到大排序，每一次都需要將數組最大的移動到數組尾部。那么排序的過程如下動圖所示：

二、選擇排序

前面說的冒泡排序是每一輪比較確定最后一個元素，中間過程不斷地交換。而選擇排序就是每次選擇剩下的元素中最小的那個元素，直到選擇完成。

排序的步驟如下：

• 從第一個元素開始，遍歷其后面的元素，找出其后面比它更小的元素，若有，則兩者交換，保證第一個元素最小。
• 對第二個元素一樣，遍歷其后面的元素，找出其后面比它更小的元素，若存在，則兩者交換，保證第二個元素在未排序的數中（除了第一個元素）最小。
• 依次類推，直到最后一個元素，那么數組就已經排好序了。

比如，現在我們需要對 [98，90，34，56，21] 進行排序，動態排序過程如下：

三、插入排序

選擇排序是每次選擇出最小的放到已經排好的數組后面，而插入排序是依次選擇一個元素，插入到前面已經排好序的數組中間，當然，這是需要已經排好的順序數組不斷移動。步驟描述如下：

從第一個元素開始，可以認為第一個元素已經排好順序。

取出后面一個元素 n，在前面已經排好順序的數組里從尾部往頭部遍歷，假設取出來的元素為 nums[i]，如果 num[i]>n，那么將 nums[i] 移動到后面一個位置，直到找到已經排序的元素小于或者等于新元素的位置，將 n 放到新空出來的位置上。如果沒有找到，那么 nums[i] 就是最小的元素，放在第一個位置。

重復上面的步驟 2，直到所有元素都插入到正確的位置。

以數組 [98，90，34，56，21] 為例，動態排序過程如下：

四、希爾排序

希爾排序（Shell’s Sort）又稱“縮小增量排序”（Diminishing Increment Sort），是插入排序的一種更高效的改進版本，同時該算法是首次沖破 O(n^2*n*2) 的算法之一。

插入排序的痛點在于不管是否是大部分有序，都會對元素進行比較，如果最小數在數組末尾，想要把它移動到數組的頭部是比較費勁的。希爾排序是在數組中采用跳躍式分組，按照某個增量 gap 進行分組，分為若干組，每一組分別進行插入排序。再逐步將增量 gap 縮小，再每一組進行插入排序，循環這個過程，直到增量為 1。

希爾排序基本步驟如下：

選擇一個增量 gap，一般開始是數組的一半，將數組元素按照間隔為 gap 分為若干個小組。

對每一個小組進行插入排序。

將 gap 縮小為一半，重新分組，重復步驟 2（直到 gap 為 1 的時候基本有序，稍微調整一下即可）。

以數組 [98，90，34，56，21，11，43，61] 為例子，排序的動圖如下：

五、快速排序

快速排序比較有趣，選擇數組的一個數作為基準數，一趟排序，將數組分割成為兩部分，一部分均小于/等于基準數，另外一部分大于/等于基準數。然后分別對基準數的左右兩部分繼續排序，直到序列有序。這體現了分而治之的思想，其中還應用到挖坑填數的策略。

算法的步驟如下：

從數組中挑一個元素作為基準數，一半情況下我們選擇第一個 nums[i]，保存為 standardNum，可以理解為 nums[i] 坑位的數被拎出來了，留下空的坑位。

取數組的左邊界索引為 i，右邊界索引 j，j 從右邊往左邊，尋找到比 standardNum 小的數，停下來，寫到 nums[i] 的坑位，nums[j] 的坑位空出來。 i 從左邊往右邊找，尋找比 standardNum 大的數，停下來，寫到 nums[j] 的坑位，這個時候，num[i] 的坑位空出來（前提是 i 和 j 不相撞）。

上面的 i 和 j 循環步驟 2，直到 i 和 j 相撞，將基準值 standardNum 寫到坑位 nums[i] 中，這時候，standardNum 左邊的數都小于等于它本身，右邊的數都大于等于它本身。

分別對 standardNum 左邊的子數組和右邊的子數組，循環執行前面的 1，2，3，直到不可再分，并且有序。

以數組 [61，90，34，56，21，11，43，68] 為例，動態排序過程如下：

六、歸并排序

前面學的快速排序，體現了分治的思想，但是不夠典型，而歸并排序則是非常典型的分治策略。歸并的總體思想是先將數組分割，再分割…分割到一個元素，然后再兩兩歸并排序，做到局部有序，不斷地歸并，直到數組又被全部合起來。

排序步驟大致如下：

• 將長度為 n 的數組分割成為 n/2 的兩個子數組。
• 子數組也不斷分割成為更小的子數組，直到不能分割。
• 最小子數組之間開始兩兩合并，合并之后的結果再合并。合并的時候可以申請一個臨時空間，利用兩個索引指針比較的方式，將兩個子數組的結果合并到臨時數組中去。
• 循環 3 步驟，直到合并成為長度為 n 的已經排序的數組。

以數組 [61，90，34，56，21，11，43，68] 為例，每一次都是對數組分成兩半，直至不能拆分，再兩兩合并，合并的時候相當于對有序的兩個子數組合并。

動態執行過程如下：

七、計數排序

計數排序，不是基于比較，而是基于計數。

計數排序步驟如下：

• 遍歷數組，找出最大值和最小值。
• 根據最大值和最小值，初始化對應的統計元素數量的數組。
• 遍歷元素，統計元素個數到新的數組。
• 遍歷統計的數組，按照順序輸出排序的數組元素。

假設有幾個青少年，他們年齡很接近，分別是 11、9、11、 13、12、14、15、13，現在需要給他們按照年齡排序。首先先遍歷一遍，找出最小的 min 和最大的元素 max，創建一個大小為 max - min + 1 的數組，再遍歷一次，統計數字個數，寫到數組中。

然后再遍歷一次統計數組，將每個元素置為前面一個元素加上自身，為什么這樣做呢？

為了讓統計數組存儲的元素值等于相應整數的最終排序位置，這樣我們就可以做到穩定排序，比如下面的 15 對應的是 8，也就是 15 在數組中出現的是第 8 個元素，從后面開始遍歷，我們就可以保持穩定性。

比如原數組從后往前遍歷到 13 的時候， 13 對應的位置是 6，那么此時從后往前遍歷到的第一個 13 就是在第 6 個元素位置。后面再遇到 13，就放到第 5 個元素位置，不會打亂它們的相對位置。

動態過程如下：

八、桶排序

桶排序，是指用多個桶存儲元素，每個桶有一個存儲范圍，先將元素按照范圍放到各個桶中，每個桶中是一個子數組，然后再對每個子數組進行排序，最后合并子數組，成為最終有序的數組。這其實和計數排序很相似，只不過計數排序每個桶只有一個元素，而且桶的值為元素的個數。

桶排序的具體步驟：

• 遍歷數組，查找數組的最大最小值，設置桶的區間（非必需），初始化一定數量的桶，每個桶對應一定的數值區間。
• 遍歷數組，將每一個數，放到對應的桶中。
• 對每一個非空的桶進行分別排序（桶內部的排序可以選擇 JDK 自帶排序）。
• 將桶中的子數組拼接成為最終的排序數組。

以數組 [98，90，34，56，21，11，43，61] 為例，桶排序的動態過程：

先遍歷查找出 max 為 98， min 為 11，數組大小為 8，（ 98 - 11 ）/8 + 1 = 11，桶的個數為 11。先把元素按照區間放進去，對每一個桶分別排序，然后再把桶的元素連起來放在數組中，排序就完成了。

九、堆排序

堆排序，就是利用大頂堆或者小頂堆來設計的排序算法，是一種選擇排序。堆是一種完全二叉樹：

• 大頂堆：每個節點的數值都大于或者等于其左右孩子節點的數值。
• 小頂堆：每個節點的數值都小于或者等于其左右孩子節點的數值。

我們一般使用數組來對堆結構進行存儲，下面我們只說大頂堆（元素按照從小到大排序），假設數組為 nums[]，則第 i 個數滿足：num[i] >= nums[2i+1] 且 num[i] >= nums[2i+2]，第 i 個數在堆上的左節點就是數組中下標索引 2i+1 的元素，其右節點就是數組中下標索引 2i+2 的元素。

排序的思路為：

• 將無序的數組構建出一個大頂堆，也就是上面的元素比下面的元素大。
• 將堆頂的元素和堆的最末尾的元素交換，將最大元素下沉到數組的最后面（末端）。
• 重新調整前面的順序，繼續交換堆頂的元素和當前末尾的元素，直到所有元素全部下沉。

倘若一個數組為 [11，21，34，43，56，61，90，98]，動態的過程如下：

十、基數排序

基數排序比較特殊，特殊在它只能用在整數（自然數）排序，而且不是基于比較的，其原理是將整數按照位分成不同的數字，按照每個數各位值逐步排序。何為高位，比如 81，1 就是低位， 8 就是高位。 分為高位優先和低位優先，先比較高位就是高位優先，先比較低位就是低位優先。下面我們講高位優先。

主要的步驟如下：

• 將所有元素統一稱為統一數位長度，前面補 0。
• 從最高位開始，依次排序，從最高位到最低位遍歷完，數組就是有序的。

以數組 [98，90，34，56，21，11，43，61，39] 為例，動態的排序過程如下：

---

十個算法的復雜度以及特點總結一下：

• 冒泡排序：基本最慢，時間復雜度最好為 O(n)，最壞為 O(n2)，平均時間復雜度為 O(n2)，空間復雜度為 O(1)，穩定排序算法。
• 選擇排序：時間復雜度很穩定，最好最壞或者平均都是 O(n2)，空間復雜度為 O(1)，可以做到穩定排序。
• 插入排序：時間復雜度最好為 O(n)，最壞為 O(n2)，平均時間復雜度為 O(n2)，空間復雜度為 O(1)，穩定排序算法。
• 希爾排序：希爾增量下最壞的情況時間復雜度是 O(n2)，最好的時間復雜度是 O(n) （也就是數組已經有序），平均時間復雜度是 O(n3/2)，屬于不穩定排序。
• 快速排序：時間復雜度最差的情況是 O(n2)，平均時間復雜度為 O(nlogn)，空間復雜度，雖然快排本身沒有申請額外的空間，但是遞歸需要使用棧空間，遞歸數的深度是 log2n，空間復雜度也就是 O( log2n)，屬于不穩定排序。
• 歸并排序：排序復雜度為 nlog2n，不存在好壞的情況，但是代價就是需要申請額外的空間，申請空間的大小最大為 n，所以空間復雜度為 O(n)，屬于穩定排序。
• 計數排序：時間復雜度為 O(n+k)，申請了一個統計數組和一個新數組，空間復雜度為 O(n+k)，沒有所謂最好最壞，都是一個復雜度，一般適用于小范圍整數排序，屬于穩定排序。
• 桶排序：最好情況時間復雜度 O(n)，最壞情況時間復雜度為 O(n2)，平均的時間復雜度為 O(n+k)。由于在中間過程中會申請桶的數量 m，所以空間復雜度為 O(n+m)，穩定性決定于桶內部排序。
• 堆排序：時間復雜度為 O(nlogn)，沒有申請額外的空間，空間復雜度為 O(1)，屬于不穩定排序。
• 基數排序：時間復雜度為 O(d(2n))。一般只使用于整數排序，不適合小數或者文字排序。由于需要申請桶的空間，假設有 k 個桶(上面是 10 個桶)，則空間復雜度為 O(n+k)，一般 k 較小，所以近似為 O(n)，屬于穩定排序。

每一種排序，都有其優缺點，我們應該根據場景選擇合適的排序算法。

資料來源

如果你覺得有用的話就給這篇文章一個贊吧！

總結

以上是生活随笔為你收集整理的「干货」编程语言十大经典算法，你知道几个？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。