??樊梓慕：個人主頁
???個人專欄：《C語言》《數(shù)據(jù)結構》《藍橋杯試題》《LeetCode刷題筆記》《實訓項目》
??每一個不曾起舞的日子，都是對生命的辜負
目錄
前言
1.直接插入排序
2.希爾排序
3.直接選擇排序
4.堆排序
前言
本篇文章博主將介紹排序算法中的插入排序：直接插入排序、希爾排序和選擇排序：選擇排序、堆排序，并進行代碼實現(xiàn)，感興趣的同學給博主點點關注哦??
歡迎大家??收藏??以便未來做題時可以快速找到思路，巧妙的方法可以事半功倍。
=========================================================================文章來源地址http://www.zghlxwxcb.cn/news/detail-715468.html
GITEE相關代碼：??fanfei_c的倉庫??
=========================================================================
1.直接插入排序
直接插入排序的思想就是從左到右進行遍歷，在遍歷過程中將當前的元素插入到前面（已經(jīng)有序）合適的位置，直到遍歷完成。
直接插入排序的特性：
- 元素集合越接近有序，直接插入排序算法時間效率越高；
- 時間復雜度：O(N^2)；
- 空間復雜度：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.希爾排序
希爾排序與直接插入排序同屬插入排序方法，也就是說希爾排序也是靠向前插入的思路進行的。
不同的是，希爾排序先進行預排序，將待排序序列調(diào)整的接近有序后，再進行一次直接插入排序。
希爾排序利用了插入排序的特性：待排序序列越接近有序，插入排序時間效率越高。
那么如何進行預排序呢？
希爾排序?qū)⒋判蛐蛄蟹纸M，假設定義一個變量?gap ，那么間隔gap的數(shù)據(jù)我們分為一組，如圖：
預排序階段：我們以分組情況為基礎，每組內(nèi)部進行直接插入排序，每完成一輪，gap=gap/3-1。
注意：預排序階段的邊界設計很多可以參照直接插入排序，就是將1改為了gap而已，不理解時可以代入直接插入排序進行理解。?
直接插入排序階段：直到gap的值為1的時候，我們發(fā)現(xiàn)此時就是直接插入排序了，經(jīng)過這輪排序就能得到最終的有序序列。
圖片取自wikipedia-Shell_sort
希爾排序的特性總結：
- 希爾排序是對直接插入排序的優(yōu)化。
- 當gap > 1時都是預排序，目的是讓數(shù)組更接近于有序。當gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就會很快。這樣整體而言，可以達到優(yōu)化的效果。我們實現(xiàn)后可以進行性能測試的對比。
- 希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算，因此在好些樹中給出的希爾排序的時間復雜度都不固定。大致為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)化，每次遍歷選出最大值和最小值，分別放到兩邊。
直接選擇排序的特性：
- 直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用
- 時間復雜度：O(N^2)
- 空間復雜度：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)//假設max被換走了，恢復一下
{
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é)點下標，重復這一過程直到孩子節(jié)點超出節(jié)點總數(shù)。
對于堆排序來說：
以升序為例：
首先構建大堆（推薦使用向下調(diào)整），此時堆頂元素一定為最大值，然后將堆頂元素與最后一個節(jié)點交換，此時最大值就放到了整個數(shù)組的最后面，然后除了最后一個值以外，其他的數(shù)據(jù)再向下調(diào)整，調(diào)整完成后堆頂元素為次大值，再與數(shù)組倒數(shù)第二個位置的值交換，這樣依此往復就得到了升序數(shù)組。
注意：升序建大堆，降序建小堆。
??更多關于堆的內(nèi)容可以參考博客：堆排序與TopK問題---樊梓慕??
堆排序的特性總結：?
- 堆排序擅于處理龐大數(shù)據(jù)。
- 時間復雜度：O(N*logN)
- 空間復雜度：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ù)關注博主動態(tài)，博主會持續(xù)輸出優(yōu)質(zhì)內(nèi)容
??博主很需要大家的支持，你的支持是我創(chuàng)作的不竭動力??
??~ 點贊收藏＋關注 ~??文章來源：http://www.zghlxwxcb.cn/news/detail-715468.html
=========================================================================
到了這里，關于【數(shù)據(jù)結構】排序算法（一）—＞插入排序、希爾排序、選擇排序、堆排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
