Java數據結構_一篇文章了解常用排序

本文所有排序舉例均默認為升序排列。

1. 常見的排序算法

2. 常見排序算法的實現

2.1 插入排序

2.1.1 基本思想：

2.1.2 直接插入排序

2.1.3 希爾排序（縮小增量排序）

2.2 選擇排序

2.2.1 基本思想：

2.2.2 直接選擇排序

2.2.3 堆排序

2.3 交換排序

2.3.1 冒泡排序

2.3.2 快速排序

1. Hoare版

回答問題：

2. 挖坑法

3.? 前后指針法：

2.2.3 快速排序的優化

1. 三數取中法選key

2.遞歸到比較小的子區間的時候，可以考慮使用插入排序

2.2.4 快速排序的非遞歸實現：

2.4 歸并排序

?2.4.1 基本思想

2.4.2 歸并排序的非遞歸實現

2.4.3 海量數據的排序問題

3. 排序算法復雜度及其穩定性分析總結

4. 其他非基于比較排序（了解）

1. 計數排序

2. 基數排序

3. 桶排序

1. 常見的排序算法

2. 常見排序算法的實現

2.1 插入排序

2.1.1 基本思想：

直接插入排序的基本思想：

把待排序的元素，按照其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，知道所有的元素插入完為止，從而得到一個有序的序列，實際生活中，就像在整理撲克牌時，就利用了插入排序的思想。

2.1.2 直接插入排序

當插入第 i (i >= 1)個元素的時候，i 前面的元素已經排好序，此時用array[i]與前面的元素進行比較，找到適合的位置插入即可，原來位置上的元素則順序向后移。

如圖：

如果要將下圖的數組按照直接插入排序

可定義兩個索引變量 i = 1 ， j = i - 1，在定義一個臨時變量tmp

將下標為 i 的元素先存入tmp中

然后再將下標為 j 的元素與tmp進行對比，如果array[j] > tmp，則要把下標為 j 的位置讓出來，即 array[j + 1] = array[j]，同時 j--，繼續對比

直到 j < 0結束對比，此時 j + 1下標的位置就是最小的元素的下標，再將tmp的值賦給array[j + 1]，即

array[j + 1] = tmp

然后 i 繼續向后走，j 繼續賦值為 i - 1

比較array[j] > tmp，則給tmp讓出位置（注意，讓出位置的作用的不能在排序過程中損失任何一個元素），array[j + 1] = array[j] ，j--

繼續比較array[j] 仍然大于 tmp 繼續讓位置 array[j + 1] = array[j]，j--

當 j < 0的時候，將tmp賦給索引為 j + 1的位置

如此循環，即可實現直接插入排序方法

于是有代碼如下：

下面是對直接插入排序方法的分析：

可以在測試類中測試：

在測試類中，先寫三個創建數組的方法

然后再main函數中分別調用orderArray，notOrderArray，notOrderArrayRandom和testInsertSort方法，來測試一下排序耗時，從而區別在不同情況下該方法的時間復雜度

也可以用普通用例來測試，是否符合預期：

2.1.3 希爾排序（縮小增量排序）

希爾排序又稱縮小增量法。其基本思想是：先選定一個整數，把待排序數組中所有元素分成多個組（距離為那個整數的元素分在同一組內），并對每一組的元素進行排序，然后，再取一個整數，重復上述分組和排序的工作。當取的值達到1的時候，所有的記錄在同一組內排好序。

如下圖，有一組數據，其初始狀態如下：

取整數gap為5，然后將互相距離為5的元素分為一組，然后進行排序

再取整數gap為2，然后再將互相距離為2的元素分為一組，即4 2 5 8 5一組，1 3 9 6 7一組，然后組內進行排序：

然后再取整數gap為1，此時距離為1，即所有的元素都在一組，然后再進行分組，組內排序

問題來了，整數gap的值是如何取的呢？此處為什么是5 2 1呢？This is a question，很多專家對此評判不一：

我們此處代碼實現，就按照gap = n / 2的大小來寫代碼如下：

希爾排序的本質是直接插入排序的一種優化方法，再shell方法中本質上還是直接排序方法，不過是i 和 j 的運動由之前的一個一個變化為了跳躍gap。

普通測試如下：符合預期

時間復雜度測試：

2.2 選擇排序

2.2.1 基本思想：

每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到排序的數據元素排完。

2.2.2 直接選擇排序

初始狀態：整個數組分為有序區和無序區，初始時有序區為空，無序區包含數組的所有元素。
第 1 輪選擇：在無序區中找到最小的元素，將它與無序區的第一個元素交換位置，此時有序區包含 1 個元素，無序區包含?n - 1?個元素。
第 2 輪選擇：在剩余的無序區中找到最小的元素，將它與無序區的第一個元素交換位置，此時有序區包含 2 個元素，無序區包含?n - 2?個元素。
重復上述步驟，直到無序區為空，此時整個數組就有序了。

如下圖，如何將其以直接選擇排序的方式進行排序

定義下標i ， j ， minIndex?

然后將 j 逐步向后加加，比較array[j] 與 array[minIndex]的大小，如果array[j] < array[minIndex]，則交換對應的值一直 j 遍歷完整個數組后

進行交換

i++，繼續尋找下一個最小的元素。最終使得數組稱為升序。

于是有代碼如下：

測試符合預期：

復雜度：

選擇排序方法中，還有一種優化后的方法：

讓 i 向后遍歷數組，如果array[i] < array[minIndex] 則把 i 賦給minIndex，如果array[i] > array[maxIndex]，則把 i 賦給maxIndex，這樣 i 遍歷一次之后，就能知道最大和最小的值了，然后然后將對應最大和最小的值分別放在索引為right 和 left 的位置，然后left++，right--

于是有代碼如下：

但是在Test測試類中，發現結果不符合預期：

是因為還存在一種邏輯錯誤，當最大元素的初始位置，恰好是left時候，在將最小元素交換到left位置之后，最大元素就被換到了minIndex位置，后序代碼再將索引為right和索引為maxIndex（還是原來的left位置）進行交換，就會導致結果錯誤。

如下圖，minIndex = 3，maxIndex = 0

先將left和minIndex元素交換

再將right與maxIndex的元素交換時，maxIndex索引指向的元素已經不是最大值了，出現邏輯錯誤。

應該進行改正：在minIndex和left進行交換后，加一個if判斷條件：if(maxIndex == left) maxIndex = minIndex

完整代碼如下：

測試符合預期：

2.2.3 堆排序

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。注意的是：排升序要建大根堆，排降序要建小根堆。

在堆中已經學習，此處僅做代碼復習：

測試符合預期：

時間測試：

2.3 交換排序

基本思想：根據序列中兩個記錄鍵值的比較結果來兌換兩個記錄在序列中的位置。

2.3.1 冒泡排序

簡單，僅作代碼展示

2.3.2 快速排序

Hoare于1962年提出的一種二叉樹結構的交換排序方法，基本思想：任取待排序元素中的某元素作為基準值，按照該基準值將排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右序列重復該過程，知道所有元素都排列在相應位置上為止。

大致框架：

1. Hoare版

舉例說明：

如下面這個數組

???

定義一個left，一個right

Key對應的元素是6，然后先從后面right開始，找比6小的元素，再從前面left開始，找比6大的元素

找到之后，交換其值

再繼續找

找到之后，再交換值

直到left和right相遇之后

將相遇的這個索引的數值和6進行交換

換完之后，會發現，6左邊的元素都是比6小的值，6右邊的元素都是比6大的值

此時稱6為privot（基準）

然后再以上面的方法，分而治之，即再在6的左邊，和6的右邊進行上述操作

例如：在左邊，Key為3

再先從right開始，找比3小的元素，找到2，再從左邊left出發找比3大的元素，發現會相遇

在拿相遇時候的值和3進行交換

此時3又是新的基準

再對3的左邊進行操作，有新的left和right

先從right找比2小的--1，再從left找比2大的，與right相遇

相遇的值與2進行交換

此時2有序了，左側只有一個元素，1也有序了。

再對3的右樹進行操作：操作過后，4，5交換位置，這樣6的左樹就全部有序了

大致操作過程，也是很像二叉樹的遞歸過程

第一次找到privot6

然后對6的左樹遞歸

再對3的左樹遞歸

再逐層向下遞歸

然后再遞歸3的右樹，再遞歸6的右樹等等，所以重點在于，如何確定基準privot的位置。

可以先將大致框架搭建起來，為了保持和前面排序方法參數的一致性，所以再quickSort方法中添加了quic方法。再quick中不斷調用partition方法。

假設已經partition方法已經完成，在quick方法中，如何不斷遞歸呢？

因為在后面過程中，不斷進行變化的是left和right，這里start和end的位置并沒有發生變化。

還要思考的是：遞歸結束的條件是什么呢？

可以回憶在遞歸二叉樹的時候結束的條件：

當沒有左右子樹，或者只有左右子樹一棵樹的條件： start >= end。

如何在partition方法中找到partition呢？

再想一下，剛剛模擬的過程，首先明白，當left和right相遇的時候，要把第一個元素key來存起來，然后就是先從right位置找比6小的元素（為什么要先從right開始走呢？這里提出一個問題，后面解決），當從right位置找到比6小的元素之后，再從left位置找到比6大的元素，然后進行交換，然后left++，right--，直到left和right相遇，于是有代碼如下：（在array[right] >= key中為什么要加上等于呢？這里是第二個問題）

但是，注意上面的代碼會出現越界的問題，在219和224中的while循環中，可能會出現越界錯誤，比如219中，如果right從后面開始，逐漸--的過程中，后面的元素的值都是比key大的元素，則right會一直--，會出現越界情況，224中如果left從前面開始，逐漸++的過程中，元素的值都是比key小的元素，則left會一直++，也會出現越界的情況，所以此時要再加一個條件。

上面代碼一直執行217中的while循環，直到left和right相遇之后，就要交換相遇位置和最開始key值的位置了，但是有一個問題是，最開始的key位置是通過left定位的，left已經++到了后面，無法再找到6的下標索引，所以應該在最開始再定義一個遍歷來存一下key的下標索引。

即定義一個 i 存儲最開始的key位置的下標索引，然后當相遇跳出循環后，再交換left/right 與 i ，最后返回 left/right。

完整代碼為：

測試符合預期：

分析時間復雜度和空間復雜度：

如果數組的順序是 1 2 3? 4 5? 6.......等等，那此時的時間復雜度是最壞情況，因為此時right右邊都是比key大的元素，一直到最左邊與left相遇，這樣就會稱為只有一側的單分支樹，此時時間復雜度為O(N ^ 2)

最好情況，就是在partition方法中，每次分割都能分割稱完全二叉樹 / 滿二叉樹，此時的時間復雜度為O(N * logN)

同樣的空間復雜度也分最好情況：O(logN) 滿二叉樹 / 完全二叉樹

最壞情況：O(N) 單分支的樹

總結：

再創建100000數據來測試時間：

卻發現出現異常了，自行研究發現是棧溢出異常，則發現，當創建順序和逆序的數組時候，空間復雜度為O(N)，10000個數據導致棧溢出。后面會有優化的方法！

回答問題：

一：為什么要right先開始從后往前找比key小的元素，也就是說：為什么不可以先從left開始，找比key大的元素？可以嘗試一下，如果先從left開始找，結果是什么

left繼續向后走，找比6大的元素，是9，此刻正好與right相遇，則交換此時left下標索引的值與key下標索引的值

會發現，如果先left后right的話，會導致，left和right相遇的數字是比6大的數字，導致交換后，6左邊的元素，并不是都比6大的元素。

二：下面框住的地方為什么是等于號

這里可以舉出兩種反例，來證明取等號的重要性：

一：如果數組為[3,3,1,3,4]，right開始找，如果不取等號，即array[right] > key，right--，則right會在倒數第二個元素，即下標索引為3的位置停止。之后，left開始找，如果left也不取等號，即array[left] < key，left++，則left會在第一個元素，即下標索引位置為0的位置停止。然后執行swap代碼，但是發現，left和right指向的元素都大小都是3，交換之后沒有意義，且，代碼會陷入死循環，一直交換這兩個相同的3。

二：如果數組為[5,5,5,5,5]，則代碼更是會陷入死循環，無法跳出while(left < right) 的循環，無法返回left。

2. 挖坑法

還是這個例子：

挖坑法，顧名思義，是會挖出一個一個空的，會首先將key的值單獨存起來（相當于挖了一個坑），然后從right開始找比key小的元素，找到后，把該索引的值填入給key的下標索引中

如圖：先將6存起來

然后right找到比6小的元素5

把5覆蓋到6的位置，同時之前5的位置相當于又留了一個坑

left向前走，找到比6大的元素的下標索引

把7填到剛剛5留下的坑的位置，同時7也留下了新的坑

right繼續向前找到比6小的元素

把4填到剛剛7留下的坑，同時4也留下了新的坑

left繼續向后找到比6大的元素，9把剛剛4留下的坑填入，留下新的坑

right繼續向前找到比6小的元素，3把剛剛9留下的坑填入，留下新的坑

left向后走，和right相遇，相遇位置是空的坑，將最開始記錄下的6填入

完成一次排序，返回基準值，然后進行遞歸，挖坑法的大致流程和Hoare法相同，但在細節和每一次的排序結果中有所不同。

于是代碼實現為：

3.? 前后指針法：

這個直接用代碼來理解思想即可：

起始時，prev指針指向序列的開頭，cur指針指向prev指針的后一個位置

示例與代碼結合，示例滿足286行循環，進入循環，287行中array[cur] <= array[left]，示例中array[cur] 等于1，array[left] 等于6，滿足條件，再看array[++prev] != array[cur] array[++prev]等于1，array[cur] 等于1，兩個值相等，不滿足if條件，不進入循環，cur直接++

cur++后，cur仍小于等于right，繼續進入循環，仍不滿足if的第二個條件，直接cur++

繼續進入循環，此時情況不滿足if的第一個條件，直接cur++，注意此時因為不滿足第一個if條件，就不會進入if的第二個條件，所以prev不會執行前置++

繼續進入循環，此時情況不滿足if的第一個條件，直接cur++，prev仍然不會執行前置++此時進入循環，if的兩個條件都滿足，且在第二個條件的時候，prev是的位置也進行了變化

進入if循環，交換cur和prev的值

然后cur++

繼續向后推進，if的兩個條件都滿足，在滿足第二個條件的時候，prev的位置繼續進行變化?

進入if條件，進行swap交換

cur++

進入循環，滿足if的兩個條件，prev先前置++

再swap交換

cur++

再進入循環，不滿足if的第一個條件，prev不前置++，不交換，cur++

此時cur 等于 right 還可以進入循環，不滿足if的第一個條件，prev不前置++，不交換

此時cur > right 無法進入循環，再交換left和prev的值

prev的位置作為基準進行返回，這就是一次前后指針的過程

前后指針方法的特點是：使用單指針進行掃描：cur指針從左到右掃描數組，同時利用prev指針標記小于基準元素區域的邊界，通過條件判斷和交換操作完成分區。

2.2.3 快速排序的優化

在剛剛的方法中，無論是Hoare法，挖坑法，或者前后指針法，都會出現最壞情況，使得在排序的時候出現“單分支樹”的情況，導致棧溢出的異常，如何進行優化呢？

棧溢出，就是因為樹的高度太多了，想辦法優化，就是降低需要的空間，就是要降低樹的高度

即盡量使得單分支樹變為滿 / 完全二叉樹

1. 三數取中法選key

如下圖數據：

如果直接進行快速排序，則會形成單分支樹。

可以對下標索引進行操作，找到位于 left 和 right 的中間位置索引mid

對比left mid right 三個下標索引對應的元素值 5? ?7? ?9，比較這三個值的大小，判斷哪一個的大小位于這三個值的中間位置，即7是5 7 9 三個元素的中間，然后7的位置和left進行交換

這樣7就稱為了新的key值，在每次遞歸前，先進行上面操作，這樣進行快速排序的時候，不會出現單分支樹的情況了。

代碼實現：

這是在三個下標對應的元素取出元素值為中間值的下標的方法

然后在quick方法中應用：

如果將數據量減少未1 0000 個，未優化時候，的耗時是如下

優化后的耗時為

?優化之后，耗時是減少了，但如果數據量是10_0000，仍然會像未優化一樣，出現棧溢出的異常，這其實是因為IDEA集成開發環境導致的，IDEA的默認運行棧的大小是比較小的，所以優化后也會溢出，可以手動設置一下。

教程：（不同IDEA版本的教程有所不同，我使用的是2024.1版本，比較新，CSDN可以找到略舊版本的設置）

然后再多出來的框中設置即可 -Xss + 想要修改的大小再調整棧大小為3m之后，在將三數取中法屏蔽后，仍然會出現棧溢出的異常：

但如果使用了三數取中法之后，就發現可以正常運行10_0000個數據量了

的確證明我們的三數取中法是可以對快速排序法的時間和空間復雜度進行優化的。

2.遞歸到比較小的子區間的時候，可以考慮使用插入排序

什么叫遞歸到比較小的子區間呢？

對于一棵滿? / 完全二叉樹來說，最后兩層的結點的總數，一般是較多的，占了整棵樹的 2 / 3

但是在遞歸創建的時候，最后兩層所占用的空間也是最多的。在快速排序中，是利用樹的遞歸思想不斷在進行排序，越遞歸到后面，即遞歸到比較小的子區間的時候，其實是到最后已經大致有序了，我們又直到，直接插入排序方法在對大致有序的數組進行排序時候，其效率較高。?

所以，我們可以在進行快速排序的過程中，當遞歸到比較小的子區間的時候，使用插入排序。

代碼如下：end - start + 1 <= 15 代表當前子數組中包含的元素總數，當子數組中包含的元素總數小于15的時候，就可以使用直接插入排序方法，減少遞歸的次數

區間進行快速排序代碼：

2.2.4 快速排序的非遞歸實現：

理解思想即可：

在新的基準操作的時候，入棧的時候先入left再入right，操作的時候，仍然先操作右邊，再操作左邊

代碼實現：

解釋：

調用?partition?方法對整個數組進行分區，得到基準元素的最終位置?piovt。
如果基準元素左邊的子數組元素個數大于 1（即?piovt - 1 > left），將該子數組的左右邊界（left?和?piovt - 1）依次壓入棧中。
如果基準元素右邊的子數組元素個數大于 1（即?piovt + 1 < right），將該子數組的左右邊界（piovt + 1?和?right）依次壓入棧中。

2.4 歸并排序

?2.4.1 基本思想

歸并排序是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法的一個典型應用。將

已有的子序列合并，得到完全有序的序列：即先使每個子序列有序，再使子序列之間有序。

若將兩個有序表合并成一個有序表，稱為二路歸并。步驟如下：

分步詳解：

有如下數組：

對其先進行分解（先分解左邊再分解右邊最后合并）

第一次分解以中間的m的索引作為新的數組的r進行分解

再向下進行分解

繼續分解，直到r == l的時候分解完畢?

分解完畢后，再進行合并

分解很簡單，就一直向下遞歸即可

如何將兩個序列段進行合并呢？

以如下圖的兩個有序段（6，10 和 1， 7）舉例，對兩個序列段分別定義s 和 e，來表示第一個和第二個序列端的開始和合并

因為要合并到一個新的數組，所以應該計算兩個序列段的元素個數，即 3 - 0 + 1 = 4，申請一個長度為4的數組來存放合并后的序列。然后每次讓s1和s2進行比較，誰小，誰放入數組中，對應的s++，e是一個結束的位置，如果有一個數組的s逐漸向后遞歸，直到其有一個數組沒有元素了，則說明另一個數組的值都大于另一個數組的最大的值，直接將剩下的數組全部按順序放入即可。

代碼如下：

首先為了同一參數為int [] 則提供一個接口mergeSort，然后再mergeSortFunc方法中進行遞歸的操作，再有一個merge方法進行合并的操作

合并方法的代碼如下：

上面的歸并排序是嚴格的二分法，時間復雜度為O(N * logN)，空間復雜度為O(N)

穩定性分析：按照上述的合并代碼

當array[s2] == array[s1]的時候，就會將s2索引的值插入，會破壞穩定性，但如果不取等號的話，就不會提前將s2的索引值插入，就是穩定的了。所以歸并排序是穩定的排序。

測試符合預期：

2.4.2 歸并排序的非遞歸實現

歸并排序的核心思想是分治法，將一個大問題分解為多個小問題，分別解決小問題后再將結果合并。非遞歸的歸并排序通過迭代的方式，從最小的子數組開始逐步合并，直到整個數組有序。具體步驟是先將數組看作多個長度為 1 的子數組，兩兩合并成長度為 2 的子數組，再將長度為 2 的子數組合并成長度為 4 的子數組，以此類推，直到合并成一個完整的有序數組。

代碼實現如下圖：

為什么可能會出現mid和right越界的情況呢？

當 i 走到1下標索引的位置，此時mid 如果繼續等于 left + gap - 1就會越界，此時mid應該修正位置為array.length - 1

right呢？當最后剩的元素不夠一組的長度的時候，此時right = mid + gap會越界，也需要修正位置為array.length - 1

2.4.3 海量數據的排序問題

外部排序：排序過程需要在磁盤等等外部存儲的排序

前提：內容比較小，例如只有1G，但需要排序的數據遠遠大于內存，比如有100G

因為內存中因為無法把所有數據全部放下，所以需要外部排序，歸并排序是最常用的外部排序

先把文件分成200份，每一份512M
分別對512M進行排序，此時內存以及可以放的下，任意排序方式都可以
進行2路歸并，同時對200分有序文件做歸并過程，最終得到有序的結果

大致過程如下圖：

3. 排序算法復雜度及其穩定性分析總結

4. 其他非基于比較排序（了解）

1. 計數排序

思想：計數排序又稱為鴿巢原理，操作步驟：

統計相同元素出現的次數
根據統計的結果將序列回收到原來的序列中

舉例如下圖：

技術排序要先申請一個計數數組

然后對序列段進行遍歷，把對應出現的數據出現的次數再計數數組當中進行記錄

然后 i 向后走，重復上面的操作

最終計數數組的狀態為：

然后遍歷計數數組，如果在計數數組中值為0 說明未出現數據重新寫回數據

即索引為1的值為2，說明有需要排序的序列段中有兩個1，最終結果為：1 1 2 2 3 3 4 4 4 6 7 7 8 9

那如何實現呢？在實現前，需要解決問題：第一步中，申請一個計數數組，那數組的長度該如何確定呢？如果10個數據的大小集中在 90 - 100 之間，總不可能為10個數據申請一個大小為100的數組，可以用序列段中的最大值max - 最小值min + 1 來確定數組的長度，注意：申請的計數數組值是用來統計數據出現的個數。

于是有代碼如下：