本文內容介紹大綱

排序介紹

??排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作，

??平時的背景關系中，如果提到排序，通常指的是排升序（非降序），

??通常意義上的排序，都是指的原地排序(in place sort)

穩定性

??兩個相等的資料，如果經過排序后，排序演算法能保證其相對位置不發生變化，則我們稱該演算法是具備穩定性的排序演算法，

一、直接插入排序

演算法演示：

1.原理

整個區間被分為

1.有序區間

2.無序區間

??每次選擇無序區間的第一個元素，在有序區間內選擇合適的位置插入

2.基本思想

??直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 ，

實際中我們玩撲克牌時，就用了插入排序的思想

我們來說一下 直接插入排序的具體步驟：

1.定義一個 變數 i ，i 從這個陣列中的第二個元素開始遍歷

2.定義 一個變數 j ， j = i - 1 .如果 arr[ i ] 比 arr [ j] 小的話，每次都把 arr [ j+1 ] = arr [ j ]，相當于把 i 之前 比 arr [ i ] 大的數字全都向后移動一位，直到遇到 arr [ j ] < arr [ i ],此時 arr [j+1] = arr [ i ].

3.如果j向前遍歷，直到 j<0 時 也沒有滿足 arr[ i ] < arr [ j], j 向前的遍歷結束 ， arr [ j+1 ] = arr [ i ].

4.最后完成遍歷，排序完成.

3.代碼展示

穩定性判斷：

??根據上面的思路我們進行遍歷，發現4 4 的位置并沒有進行交換 ，所以 直接插入排序是穩定的.

還有一種判斷穩定性的方法：

??在排序時，如果元素 沒有發生跳躍式 變換，只是相鄰元素交換的話，這個排序就是穩定的.

??還有通過這個代碼我們發現，這個排序也可以變成不穩定的，

??在這樣的情況下，相同的元素 在比較時就會發生交換，排序變成不穩定的了.

我們可以得到一個結論：

一個穩定的排序，可以實作為不穩定的排序

但是一個本身就不穩定的排序，就不可能實作為穩定的排序

4.性能分析

時間復雜度

最好情況下：

??我們給定一個有序的陣列進行直接插入排序，這就是最好情況，此時 時間復雜度為 O (N )

最壞情況下：

??我們給定一個完全無序的陣列進行直接插入排序，這就是最壞情況，此時時間復雜度為 O（N^2）.

我們同樣得到一個結論：

當一組資料，資料量不大且 趨近于有序，此時用插入排序時間更快 .
越有序越快！！

空間復雜度

這個排序演算法 沒用用到其他的輔助空間，所以 空間復雜度 為 O (1).

穩定性

這個排序由于沒有發生跳躍式 變換，所以是 穩定的

二、希爾排序

演算法演示：

希爾排序法又稱縮小增量法，

希爾排序是基于插入排序的以下兩點性質而提出改進方法的：

1.插入排序在對幾乎已經排好序的資料操作時，效率高，即可以達到線性排序的效率，

2.但插入排序一般來說是低效的，因為插入排序每次只能將資料移動一位，

1.基本思想

1.?先選定一個小于N的整數gap作為第一增量，然后將所有距離為gap的元素分在同一組，并對每一組的元素進行直接插入排序，然后再取一個比第一增量小的整數作為第二增量，重復上述操作…

2.當增量的大小減到1時，就相當于整個序列被分到一組，進行一次直接插入排序，排序完成，

為什么要讓gap由大到小呢？

?gap越大，資料移動得越快；gap越小，資料移動得越慢，開始讓gap較大，可以讓資料更快得移動到自己對應的位置附近，減少移動次數.

*注意點

1.希爾排序是對直接插入排序的優化，

2.?當gap > 1時都是預排序，目的是讓陣列更接近于有序，當gap == 1時，陣列已經接近有序的了，這樣就會很快，這樣整體而言，可以達到優化的效果，我們實作后可以進行性能測驗的對比，

我們來將整個排序的 思路走一遍：

下面是 我們要進行排序的陣列

??將陣列中的元素進行分組，每組中的元素 gap 間隔為3， 我用不同顏色進行分組.
gap ==3 ，分組完之后，我們將每一組中的資料進行排序

??將陣列中的元素進行分組，每組中的元素 gap 間隔為2， 我用不同顏色進行分組.

gap == 2 ，分組完之后，我們將每一組中的資料進行排序

??將陣列中的元素進行分組，每組中的元素 gap 間隔為1， 此時對整體進行排序.

整體排完序后，希爾排序完成.

每一組排序我們都用的是 直接插入排序.

2.代碼展示

3.增量 gap 的選取

選自 《資料結構》清華大學出版

gap 的值 沒有除 1 以外 的公因子，并且最后一個增量值 必須為 1 .

我們只能盡量 追求gap 沒有公因子， 最后 要 +1.

我們可以這樣取 gap ，使 gap 最后為 1.

   gap = arr.length;
   while(gap>1){
       gap = gap/3+1;  //  加 1  保證最后一個序列為1 ，除幾都行
   }

4.性能分析

時間復雜度

最壞、最好情況下

??由于 gap 每次取值都不同，所以算起來十分復雜，但是我們仍然能夠得到一些資料…

所以我們就這樣認為

最好情況下時間復雜度 O（n^ 1.3）

最壞情況下時間復雜度 O（n^ 1.5）

空間復雜度

沒有借助其他的輔助空間，所以空間復雜度 為 O（1）

穩定性

在這個排序中 發生了跳躍式的交換，所以這個排序不是穩定的.

三、選擇排序

演算法演示：

1.基本思想

?陣列從頭開始遍歷 ， i= 0開始，i 后面的每一個元素 arr [ j ] 都與 arr[i] 進行比較，如果 arr [ i ]> arr [ j ] ,那么就進行交換.

我們根據思路來 走一下排序的程序.

我們要對 這個資料進行排序

開始進行排序

2.代碼展示

3.性能分析

時間復雜度

最壞情況下： O（n^2）

最好情況下： O（n^2）

空間復雜度

沒有借助輔助空間，所以空間復雜度為 O ( 1 )

穩定性

因為在排序的程序中發生了跳躍式交換，所以這種排序不是穩定的.

四、堆排序

演算法演示：

1.基本思想

從小到大排序 —— 升序 建立大堆

從大到小排序 —— 降序 建立小堆

思路： 以升序 為 例

0.先將陣列 調整為一個 大堆 ，建立一個大堆

1.?交換 陣列 首尾 的元素，這樣最大的堆頂元素 被放在陣列的最后一個，此時 最后一個元素 已經定好序了.

2.?此時從第一個到 倒數第二個再次調整，調整完后將堆頂元素 與倒數第二個元素交換，按照這樣的邏輯規律，回圈直到 有序.

我們以實際 例子說明…

下面以陣列 [5, 7, 9 , 3, 1, 8，6,2] 為例進行從小到大排序的演示：

0.調整為大堆

1.首尾交換

2.向下調整

重復此操作直到全部有序

最后我們排完序了

如何將一個陣列轉換成一個堆呢？

2.建堆操作

??下面我們給出一個陣列，這個陣列邏輯上可以看做一顆完全二叉樹，但是還不是一個堆，現在我們通過演算法，把它構建成一個堆，

??根節點左右子樹不是堆，我們怎么調整呢？這里我們從倒數的第一個非葉子節點的子樹開始調整，一直調整到根節點的樹，就可以調整成堆，

將一個二叉樹 調整為一個 大根堆

這棵二叉樹調整為 大根堆 必須將 每顆子樹都調整為大根堆.

3.向下調整

思想 步驟：

parent —> 根節點下標

child —> 孩子節點下標

1.從最后一棵子樹進行調整.

2.?每顆子樹從根節點向下調整，如果左右孩子節點的最大值比這個根節點大，那么值互換，然后 parent 指向 child ,child = 2* parent + 1， 繼續向下調整，直到 下標child 超出二叉樹 范圍.

3.重復第二步的操作，遍歷每一顆子樹，直到所有子樹全部遍歷完成.

代碼實作：

這就是 向下調整的完整程序.

我們來看整體堆排序的代碼展示：

4.代碼展示

5.性能分析

時間復雜度

最好最壞情況下，都是 O（n* logn）

空間復雜度

沒有借助外部空間，空間復雜度為O（1）

穩定性

發生了跳躍式的交換，所以是不穩定的.

五、冒泡排序

演算法演示：

1.基本思想

兩兩相鄰元素進行比較，數值大的元素排到后面，

比較相鄰的元素，如果第一個比第二個大，就交換他們兩個，

對每一對相鄰元素作同樣的作業，從開始第一對到結尾的最后一對，

針對所有的元素重復以上的步驟，除了最后一個，
?
我們也可以找到規律：

這個陣列一共有 10個數字

第 1 個數字比較了 9次， 第 2 個數字比較了 8 次…

第 i 個數字 比較 10 - i 次

??持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較，

我們來 走一遍 冒泡排序的思路：

??之后對每一個數字都從頭開始比較相鄰元素…直到全部排序完成.

2.代碼展示

3.性能分析

時間復雜度

最好、最壞情況下都是 O（n^2）,在優化下，最好情況是O（n）.

空間復雜度

沒有借助輔助空間，所以空間復雜度為O（1）

穩定性

都是相鄰元素之間進行排序，所以這個排序是穩定的.

六、快速排序

1.原理

1.從待排序區間選擇一個數，作為基準值(pivot)；通常為最左邊的數字.

2.Partition: 遍歷整個待排序區間，將比基準值小的（可以包含相等的）放到基準值的左邊，將比基準值大的（可以包含相等的）放到基準值的右邊；

3.?采用分治思想，對左右兩個小區間按照同樣的方式處理，直到小區間的長度 == 1，代表已經有序，或者小區間的長度 == 0，代表沒有資料，

1. Hoare 法

??左邊第一個數字下標定義為 start 右邊第一個數字下標定義為 end，key 為第一個數字

?end 先向前走，找到 比 key 小的位置，end 找到小于 key 的位置，保持不動，

start 在向后走，找到比 key 大的位置

找到之后，交換 start 和 end 的位置，key 的位置一直保持不動

重復此程序…

直到 start 和 end 相遇， 將該位置的值 與 key 交換.

2.挖坑法

左邊第一個數字下標定義為 start 右邊第一個數字下標定義為 end

先將第一個資料放到 臨時變數 tmp 中，形成一個坑位

?end 開始向前走，找到比 tmp 小的位置，找到后 ，將該值放入坑位中，該位置形成新的坑位

?start 開始向后移動，找到比 tmp 大的位置，找到后，將該值放入坑位中，再形成新的坑位

重復上面的兩個程序…

最后 start 和 end 相互遇見，將 tmp 的值 放入最后一個 相遇的坑位.

我們來走一遍 挖坑法 的具體思路：

2.代碼展示

1.遞回思路

2.基準值的選擇

1. 選擇邊上（左或者右）
2. 隨機選擇
3. 幾數取中（例如三數取中）：array[left], array[mid], array[right] 大小是中間的為基準值

快速排序的優化

1.選擇基準值很重要，通常使用幾數取中法

??我們如果選取的 在基準的數值正好是 這組資料的中位數，每次都是平均 分，那么此時 時間復雜度最小，但是實際情況中通常沒有那么巧合，所以我們為了追求盡可能小的 時間復雜度，取 這組資料 頭 、尾 、 中間三個數字中的中間值作為 基準.

我們在實作 paitition 函式時，要滿足這個條件：

arr [ mid] <= arr [ start ] <= arr [ end ]

2.partition 程序中把和基準值相等的數也選擇出來

3.待排序區間小于一個閾值時（例如 48），使用直接插入排序

??隨著遞回的進行,資料的區間在縮小,區間的資料也在慢慢趨近于有序…

3.非遞回思路

1.呼叫 partition 之后，找到了 pivot

2.把當前 pivot 的左邊區間 和右邊區間 的下標放入堆疊中

3.判斷堆疊是否為 空，不為空，彈出堆疊頂2個元素，注意： 放的順序 決定了 取出的順序中第一個元素是給的 high 還是 low.

4.再進行 partion

什么時候 入堆疊?

當這個區間 最起碼有 2個元素的時候

代碼展示：

3.性能分析

時間復雜度

最好的情況下，選完基準之后都均分，此時時間復雜度為O（n*logn）
最壞的情況下， 陣列為一個有序的陣列，我們要逆序，此時時間復雜度為 O（n^2）.

空間復雜度

最好情況下是每次都二分，所以空間復雜度為O（logn）,最壞情況下為 O（n）,所以 空間復雜度為 O（logn）~ O（n）.

穩定性

排序時發生了跳躍式交換，所以是不穩定的

七、歸并排序

歸并演算法演示

1.原理總覽

?歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序演算法,該演算法是采用分治法（Divide and Conquer）的一個非常典型的應用，將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序，若將兩個有序表合并成一個有序表，稱為二路歸并，

根據思路我們來將 歸并排序走一遍：

1.整組元素對半拆分，拆分之后再次進行拆分，直到拆分成單個的元素.

2.按其拆分的方式，對其對應的兩個元素進行排序并合并成一組.

3.對合并過的組，每兩組再次進行合并

在這個思路中 最重要的 就只有兩步：

1.分解，我們可以折半分解，直到 每個元素都分開

2.合并 ，將各個元素有序合并.

2.合并兩個有序陣列

我們可以根據 start、mid、end 得到兩個陣列的區間

[ start , mid ] ---- [ mid+1 , end ]

構建一個 輔助的陣列空間.

我們在排序時，有以下幾種情況

?兩個陣列都未遍歷完， s1<= e1 && s2<=e2 , 兩個同時遍歷，誰小往輔助陣列放元素.放完之后 ，輔助元素的下標 ++ ，放到陣列元素也 ++.

有一個陣列遍歷完了，直接在 已經排好序的陣列之后接上 未遍歷完的.

合并陣列的代碼展示：

3.代碼展示

歸并排序的完整代碼展示：

4.性能分析

時間復雜度

因為要進行二分拆解，所以最好、最壞情況下都是 O（n* logn）

空間復雜度

由于在合并有序陣列是借助了 輔助空間，所以 空間復雜度為 O（n）.

穩定性

每次排序都是相鄰的元素之間比較，所以是穩定的.

八、內部排序

??我們學習了這幾種基于比較的排序演算法，下面我們來進行總結一下.

??我們學的排序都是內部排序，什么是內部排序呢？ 就是把資料放在記憶體中 進行排序 .

內排序：資料量相對少一些，可以放到記憶體中進行排序，

外排序：資料量較大，記憶體中放不下，資料只能放到磁盤檔案中，需要排序，

上面介紹的排序演算法均是在記憶體中進行的，對于資料量龐大的序列，上面介紹的排序演算法都束手無策，而歸并排序卻能勝任這種海量資料的排序，

九、海量資料的排序問題

外部排序：排序程序需要在磁盤等外部存盤進行的排序

前提：記憶體只有 1G，需要排序的資料有 100G

?? 因為記憶體中因為無法把所有資料全部放下，所以需要外部排序，而歸并排序是最常用的外部排序

1.先把檔案切分成 200 份，每個 512 M

2.分別對 512 M 排序，因為記憶體已經可以放的下，所以任意排序方式都可以

3.進行 200 路歸并，同時對 200 份有序檔案做歸并程序，最終結果就有序了

??好了今天的知識就分享到這里，希望大家多多練習，熟練掌握，感謝大家的欣賞與關注！！

謝謝欣賞！！

未完待續…