我們一起來排序——使用Java語言優雅地實作常用排序算法

排序算法——最基礎的算法，網際網路面試必備技能。春來來了，排序的季節來了！本文使用Java語言優雅地實作常用排序算法，希望對大家有幫助，早日拿到Offer！

破陣子·春景 燕子來時新社，梨花落後清明。 池上碧苔三四點，葉底黃鹂一兩聲。日長飛絮輕。 巧笑同桌夥伴，上學徑裡逢迎。 疑怪昨宵春夢好，元是今朝Offer拿。笑從雙臉生。

排序算法——最基礎的算法，網際網路面試必備技能。春來來了，排序的季節來了！

本文使用Java語言優雅地實作常用排序算法，希望對大家有幫助，早日拿到Offer！

最暴力、最無腦、最簡單的排序算法。名字的由來是因為越大的元素會經由交換慢慢“浮”到數組的頂端，就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。

冒泡排序的基本思想是：每次比較相鄰的元素，如果它們的順序和理想順序不一緻，就把它們進行交換。不多叨叨了，直接看代碼。

選擇排序，這樣記憶，選擇最小的元素與未進行排序的首元素進行交換。

選擇排序具體過程：

找到數組中最小的元素，将它與數組的第一個元素交換位置；

在剩下的元素中尋找最小的元素，将它和數組第二個元素交換位置；

往複執行，直到将整個數組排序完成。

選擇排序特點：

運作時間和輸入無關；選擇排序為了找到最小的元素需要每次都掃描一遍整個輸入數組，這也是它的平均時間複雜度、最好情況、最壞情況都是O（n^2）。

資料移動最少；每次交換都會改變兩個數組元素的值，交換次數和要排序的數組大小呈線性關系。

插入排序，這樣記憶，将一個元素插入到已經排好序的有序數組中。

插入排序的基本思想是：每步将一個待排序的元素，插入前面已經排序的數組中适當位置上，直到全部插入完為止。

在程式的實作中，為了給要插入的元素騰出空間，需要将其餘所有元素在插入之前都向右移動一位。

插入排序所需的時間取決于輸入元素的初始順序，對資料量比較大且基本有序的數組進行排序要比對随機順序或者逆序數組排序要快的多。

希爾排序是1959年Shell發明，是第一個突破O（n^2）的排序算法，是簡單插入排序的改進版。與插入排序的不同之處在于，它會優先比較距離較遠的元素。

希爾排序是把記錄按下标的一定增量分組，對每組使用直接插入排序算法排序；随着增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個檔案恰被分成一組，算法便終止。

希爾排序的核心在于間隔序列的設定。既可以提前設定好間隔序列，也可以動态的定義間隔序列。動态定義間隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。

關于希爾排序的時間複雜度，有人在大量的實驗之後得出結論：當n在某個特定的範圍後希爾排序的比較和移動次數減少至n^1.3 ，關于數學論證，這就很困難了。這種科學難題我們就不用太糾結了。

重要！重要！重要！>在現場筆試和面試中遇到好多次了（阿裡巴巴、位元組跳動、騰訊、百度等）。

與冒泡排序相比，快速排序每次交換是跳躍式的，這也是快速排序速度較快的原因。每次排序的時候選擇一個基準點，将小于基準點的全部放到基準點左邊，将大于基準點的都放到基準點右邊。這樣每次交換的時候就不會想冒泡排序一樣隻交換相鄰位置的元素，交換距離變大，交換次數變小，進而提高速度。當然在最壞情況下，仍可能是相鄰兩個數進行了交換。是以快速排序的最差時間複雜度和冒泡排序是一樣的，都是O（n^2）。快速排序的平均時間複雜度為O（nlogn）。而且，快速排序是原地排序（隻需要一個很小的輔助棧），時間和空間複雜度都很優秀。用《算法（第四版）》的話來說就是：

快速排序是最快的通用排序算法。

程式怎麼寫：

定義一個基準數（初始化值設定為左邊第一個元素）和兩個左右指針（分别為i和j）；

當i和j沒有相遇的時候，在循環中進行尋找i和j，讓j先從右往左尋找比基準數小的，i從左往右尋找比基準數大的，當然需要滿足條件<code>i&lt;j</code>；找到了的時候，進行交換。為什麼要右邊的指針先走呢？當從左邊開始時，那麼 i 所停留的那個位置肯定是大于基數base的，為了滿足<code>i&lt;j</code>的條件，j也會停下。那麼如果在此時進行交換，會發現交換以後并不滿足基準數左邊都比基準數小，右邊都比基準數大。

當i和j相遇的時候，說明i右邊已經沒有比基準數base小的元素了，左邊沒有比基準數大的元素了，此時交換i位置上的元素arr[i]和基準數，基準數的位置就定好了。

基準數歸位

繼續快速排序處理i的左半部分和右半部分。

如果了解了，自己能寫出來最好。如果還沒有完全了解，需要進行面試，那我覺得還是背下來吧。對，沒有看錯，就是背下來，現場筆試的時候直接默寫！！！

上文提到，快速排序是最快的通用排序算法。的确，在大多數情況下，快速排序是最佳選擇。但是，有一個明顯的例外：如果穩定性很重要且空間又不是問題，歸并排序可能是最好的。

歸并排序是分治思想（divide-and-conquer）的典型應用。将待排序的數組，可以先（遞歸地）将它分成兩半分别排序，然後将結果歸并起來。

歸并排序的優點是能夠保證将任意長度為n的數組排序所需的時間與nlogn成正比，時間複雜度為O（nlogn）；缺點也很明顯，所需的額外空間與n成正比，空間複雜度O（n）。

堆排序，首要問題是要知道什麼是堆？

通俗來說，堆是一種特殊的完全二叉樹。如果這課二叉樹所有父節點都要比子節點大，就叫大頂堆；如果所有父節點都比子節點小，就叫小頂堆。

《算法（第四版）》是這麼說的：

當一棵二叉樹的每個節點都大于等于它的兩個節點時，它被稱為堆有序。 二叉堆是一組能夠用堆有序的完全二叉樹排序的元素，并在數組中按照層序存儲。

也就是說：對于n個元素的待排序數組arr[0，...，n-1]，當且僅當滿足下列要求（<code>0 &lt;= i &lt;= (n-1)/2</code>）：

<code>array[i] &gt;= array[2*i + 1]</code> 且 <code>array[i] &gt;= array[2*i + 2]</code>； 稱為大根堆；

<code>array[i] &lt;= array[2*i + 1]</code> 且 <code>array[i] &lt;= array[2*i + 2]</code>； 稱為小根堆；

堆排序的基本思想（大頂堆為例）：将待排序數組構造成一個大頂堆，此時，整個數組的最大值就是堆頂元素。将其與末尾元素進行交換，此時末尾就為最大值。然後将剩餘n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值。如此反複執行，就可以得到一個有序數組。

具體過程：

建堆；

将堆頂元素與堆底元素進行交換；

堆頂元素向下調整使其繼續保持大根堆的性質；

重複過程2,3，直到堆中隻剩下堆頂元素未交換，此時也無法交換了，排序完成。

其中建堆的時間複雜度為O（n）；

由于堆的高度為logn，是以将堆頂元素與堆底元素進行交換并進行排序的時間複雜度為O（logn）；

是以整體的時間複雜度為O（nlogn）。

堆排序過程中隻有交換的時候借助了輔助空間，空間複雜度為O（1）。

以上的排序算法都是基于比較的排序算法。通過比較來決定元素之間的相對次序，其時間複雜度不能突破O(nlogn)的界限。

關于穩定性，如果一個排序算法能夠保留數組中重複元素的相對位置，就是穩定的。怎麼記憶呢？不穩定的排序算法可以用”快些選對“諧音來記：快速排序、希爾排序、選擇排序、堆排序。

用一張表格來作為小結：

排序方法

平均情況

最好情況

最壞情況

空間複雜度

穩定性

冒泡排序

O(n^2)

O(n)

O(1)

穩定

選擇排序

不穩定

插入排序

希爾排序

O(nlogn) ~ O(n^2)

O(n1.3)

堆排序

O(nlogn)

歸并排序

快速排序

O(logn)~O(n)

高曉松老師曾說：生活不隻是眼前的苟且，還有詩和遠方。而我希望遠方不遠，有處可尋，祝大家早日拿到Offer。

由于部落客也是在攀登的路上，文中可能存在不當之處，歡迎各位多指教！ 如果文章對您有用，那麼請點個”推薦“，以資鼓勵！