👀樊梓慕：個人主頁

?🎥個人專欄：《C語言》《數(shù)據(jù)結(jié)構(gòu)》《藍橋杯試題》《LeetCode刷題筆記》《實訓(xùn)項目》

🌝每一個不曾起舞的日子，都是對生命的辜負

---

目錄

前言

1.直接插入排序

2.希爾排序

3.直接選擇排序

4.堆排序

---

前言

本篇文章博主將介紹排序算法中的插入排序：直接插入排序、希爾排序和選擇排序：選擇排序、堆排序，并進行代碼實現(xiàn)，感興趣的同學(xué)給博主點點關(guān)注哦🌝

---

歡迎大家📂收藏📂以便未來做題時可以快速找到思路，巧妙的方法可以事半功倍。

=========================================================================

GITEE相關(guān)代碼：🌟fanfei_c的倉庫🌟

=========================================================================

---

1.直接插入排序

直接插入排序的思想就是從左到右進行遍歷，在遍歷過程中將當前的元素插入到前面（已經(jīng)有序）合適的位置，直到遍歷完成。

直接插入排序的特性：

• 元素集合越接近有序，直接插入排序算法時間效率越高；
• 時間復(fù)雜度：O(N^2)；
• 空間復(fù)雜度：O(1)；
• 穩(wěn)定性：穩(wěn)定。

排序的穩(wěn)定性：指的是保證排序前2個相等的數(shù)其在序列的前后位置順序和排序后它們兩個的前后位置順序相同。

代碼實現(xiàn)：

// 插入排序
void InsertSort(int* a, int n)
{for (int i = 0; i < n-1; i++){int end = i;int tmp = a[end + 1];//保存待插入的值while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];//向后覆蓋}else//因為此時前面已經(jīng)是有序序列，如果tmp>當前值，證明比前面都大，所以break跳出即可{break;}end--;}a[end+1]= tmp;}
}

---

2.希爾排序

希爾排序與直接插入排序同屬插入排序方法，也就是說希爾排序也是靠向前插入的思路進行的。

不同的是，希爾排序先進行預(yù)排序，將待排序序列調(diào)整的接近有序后，再進行一次直接插入排序。

希爾排序利用了插入排序的特性：待排序序列越接近有序，插入排序時間效率越高。

那么如何進行預(yù)排序呢？

希爾排序?qū)⒋判蛐蛄蟹纸M，假設(shè)定義一個變量?gap ，那么間隔gap的數(shù)據(jù)我們分為一組，如圖：

預(yù)排序階段：我們以分組情況為基礎(chǔ)，每組內(nèi)部進行直接插入排序，每完成一輪，gap=gap/3-1。

注意：預(yù)排序階段的邊界設(shè)計很多可以參照直接插入排序，就是將1改為了gap而已，不理解時可以代入直接插入排序進行理解。?

直接插入排序階段：直到gap的值為1的時候，我們發(fā)現(xiàn)此時就是直接插入排序了，經(jīng)過這輪排序就能得到最終的有序序列。

---

圖片取自wikipedia-Shell_sort

---

希爾排序的特性總結(jié)：

• 希爾排序是對直接插入排序的優(yōu)化。
• 當gap > 1時都是預(yù)排序，目的是讓數(shù)組更接近于有序。當gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就會很快。這樣整體而言，可以達到優(yōu)化的效果。我們實現(xiàn)后可以進行性能測試的對比。
• 希爾排序的時間復(fù)雜度不好計算，因為gap的取值方法很多，導(dǎo)致很難去計算，因此在好些樹中給出的希爾排序的時間復(fù)雜度都不固定。大致為O(N^1.25)到O(1.6*N^1.25)。
• 穩(wěn)定性：不穩(wěn)定

代碼實現(xiàn)：

// 希爾排序
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;//gap遞減普遍取這種，也有取gap=gap/2的for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

---

3.直接選擇排序

選擇排序的思想是每遍歷一遍選出最小的值，放到最開始的位置。

我們對該思想優(yōu)化，每次遍歷選出最大值和最小值，分別放到兩邊。

直接選擇排序的特性：

• 直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用
• 時間復(fù)雜度：O(N^2)
• 空間復(fù)雜度：O(1)
• 穩(wěn)定性：不穩(wěn)定

代碼實現(xiàn)：

// 選擇排序
void SelectSort(int* a, int n)
{int left = 0;int right = n - 1;while (right > left){int maxi = left;int mini = left;for (int i = left+1; i <=right ; i++){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}swap(&a[left], &a[mini]);if (maxi == left)//假設(shè)max被換走了，恢復(fù)一下{maxi = mini;}swap(&a[right], &a[maxi]);right--;left++;}
}

---

4.堆排序

堆排序首先要介紹的是向下調(diào)整算法。

向下調(diào)整算法的前提是左右子樹是堆。

以小堆為例：

1.給定向下調(diào)整的起點（雙親節(jié)點下標）和節(jié)點總數(shù)，根據(jù)起點下標計算孩子節(jié)點下標。

注意：向下調(diào)整時，若有兩個孩子節(jié)點，則需要確保調(diào)整的是較大的孩子節(jié)點。

2.比較孩子節(jié)點與雙親節(jié)點數(shù)值大小，若孩子節(jié)點小于雙親節(jié)點，則交換兩者，并將雙親節(jié)點的下標更新為之前的孩子節(jié)點下標，根據(jù)最新的雙親節(jié)點下標重新計算孩子節(jié)點下標，重復(fù)這一過程直到孩子節(jié)點超出節(jié)點總數(shù)。

---

對于堆排序來說：

以升序為例：

首先構(gòu)建大堆（推薦使用向下調(diào)整），此時堆頂元素一定為最大值，然后將堆頂元素與最后一個節(jié)點交換，此時最大值就放到了整個數(shù)組的最后面，然后除了最后一個值以外，其他的數(shù)據(jù)再向下調(diào)整，調(diào)整完成后堆頂元素為次大值，再與數(shù)組倒數(shù)第二個位置的值交換，這樣依此往復(fù)就得到了升序數(shù)組。

注意：升序建大堆，降序建小堆。

---

🌐更多關(guān)于堆的內(nèi)容可以參考博客：堆排序與TopK問題---樊梓慕🌐

---

堆排序的特性總結(jié)：?

• 堆排序擅于處理龐大數(shù)據(jù)。
• 時間復(fù)雜度：O(N*logN)
• 空間復(fù)雜度：O(1)
• 穩(wěn)定性：不穩(wěn)定

代碼實現(xiàn)：

// 堆排序
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){// 找出小的那個孩子if (child + 1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);// 繼續(xù)往下調(diào)整parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapSort(int* a, int n)
{// 向下調(diào)整建堆// O(N)for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}// O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

---

=========================================================================

如果你對該系列文章有興趣的話，歡迎持續(xù)關(guān)注博主動態(tài)，博主會持續(xù)輸出優(yōu)質(zhì)內(nèi)容

🍎博主很需要大家的支持，你的支持是我創(chuàng)作的不竭動力🍎

🌟~ 點贊收藏＋關(guān)注 ~🌟

=========================================================================