插入排序
插入排序分為直接插入排序和希爾排序，其中希爾排序是很值得學(xué)習(xí)的算法
希爾排序的基礎(chǔ)是直接插入排序，先學(xué)習(xí)直接插入排序
直接插入排序
直接插入排序類似于打撲克牌前的整牌的過程，假設(shè)我們現(xiàn)在有2 4 5 3四張牌，那么應(yīng)該怎么整牌？
方法很簡單，把3插到2和4中間，這樣就完成了整牌的過程，而插入排序的算法就是這樣的過程
插入排序的基本原理圖如下所示
我們?cè)谶@里定義end為已經(jīng)排查結(jié)束的，排好序的一段數(shù)據(jù)的最后一個(gè)元素，tmp作為存儲(chǔ)要移動(dòng)的元素，那么具體實(shí)現(xiàn)方法如下：
這里找到了tmp確實(shí)比end要小，于是下一步是要讓tmp移動(dòng)到end前面這段有序的數(shù)據(jù)中的合適的位置
算法實(shí)現(xiàn)的思想是：tmp如果比end的值小，那么就讓end的值向后移動(dòng)，end再指向前一個(gè)，再比較覆蓋移動(dòng)…直到tmp的值不比end小或者end直接走出數(shù)組，如果走出數(shù)組就讓tmp成為新的首元素
這樣就完成了一次插入，那么接著進(jìn)行一次排序：
從中可以看出，插入排序整體的思想并不算復(fù)雜，代碼實(shí)現(xiàn)相對(duì)也更簡單，直接插入排序的價(jià)值在于給希爾排序做準(zhǔn)備
插入排序的實(shí)現(xiàn)如下：
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i; // 找到有序數(shù)組的最后一個(gè)元素
int tmp = a[i + 1]; // 要參與插入排序的元素
while (end >= 0)
{
if (a[end] > tmp)
{
// 進(jìn)行覆蓋
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
直接插入排序的時(shí)間復(fù)雜度也不難分析，是O(N^2)，和冒泡排序在同一個(gè)水平，并不算高效
直接插入排序更多是給希爾排序做鋪墊，希爾排序是很重要的排序，處理數(shù)據(jù)的效率可以和快速排序看齊
希爾排序
上面學(xué)完了插入排序，那么就必須總結(jié)一下插入排序的弊端
- 插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高，即可以達(dá)到線性排序的效率。
- 但插入排序一般來說是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位。
于是，希爾排序就是基于上面這兩個(gè)問題進(jìn)行解決的：
首先，插入排序?qū)τ谝呀?jīng)排序差不多的序列有很強(qiáng)的效率，但與此同時(shí)它一次只能調(diào)整一個(gè)元素的位置，因此希爾就發(fā)明了希爾排序，它具體的操作幾乎和插入排序相同，只是在插入排序的基礎(chǔ)上，前面多了預(yù)排序的步驟，預(yù)排序是相當(dāng)重要的，可以把一段數(shù)據(jù)的大小排序基本相同
那預(yù)排序的實(shí)現(xiàn)是如何實(shí)現(xiàn)的？
首先把數(shù)據(jù)進(jìn)行分組，假設(shè)分成3組，下面的圖片演示了這個(gè)過程
分好組后，對(duì)每一組元素單獨(dú)進(jìn)行插入排序
此時(shí)，序列里的數(shù)據(jù)就已經(jīng)很接近有序了，再對(duì)這里的數(shù)據(jù)進(jìn)行插入排序，可以完美適應(yīng)插入排序的優(yōu)點(diǎn)
這里只是寫了希爾排序的基本思想是如何工作的，具體的代碼實(shí)現(xiàn)較為復(fù)雜
那么下一個(gè)問題就有了，為什么gap是3？如果數(shù)據(jù)量特別大還是3嗎？gap的選擇應(yīng)該如何選擇？
這里對(duì)gap要進(jìn)行理解，gap到底是用來做什么的，它的大小會(huì)對(duì)最終結(jié)果造成什么影響
gap是對(duì)數(shù)據(jù)進(jìn)行預(yù)處理階段選擇的大小，通過gap可以把數(shù)據(jù)變得相對(duì)有序一點(diǎn)，而gap越大，說明分的組越多，每一組的數(shù)據(jù)就越少，gap越小，分的就越細(xì)，就越接近真正的有序，當(dāng)gap為1的時(shí)候，此時(shí)序列只有一組，那么就排成了真正的有序
代碼實(shí)現(xiàn)如下：
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end = end - gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
這里重點(diǎn)理解兩點(diǎn)
gap = gap / 3 + 1; // 這句的目的是什么？
gap==1 // 是什么
gap=gap/3+1會(huì)讓gap的最終結(jié)果一定為1
而gap為1的時(shí)候，此時(shí)就是插入排序，而序列也接近有序，插入排序的優(yōu)點(diǎn)可以很好的被利用
希爾排序的時(shí)間復(fù)雜度相當(dāng)難算，需要建立復(fù)雜的數(shù)學(xué)模型，這里直接說結(jié)論，希爾排序的時(shí)間復(fù)雜度大體上是接近于 O(N^1.3) 整體看效率是不低的，值得深入鉆研學(xué)習(xí)
選擇排序
選擇排序
基礎(chǔ)版的選擇排序?qū)崿F(xiàn)是很簡單的，算法思路如下
這里需要注意一點(diǎn)是，maxi可能會(huì)和begin重疊，導(dǎo)致交換begin和min的時(shí)候產(chǎn)生bug，因此只需要在前面補(bǔ)充一下條件即可
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int maxi = begin, mini = begin;
for (int i = begin; i <= end; i++)
{
if (a[i] > a[maxi])
{
maxi = i;
}
if (a[i] < a[mini])
{
mini = i;
}
}
Swap(&a[begin], &a[mini]);
// 如果maxi和begin重疊，修正一下即可
if (begin == maxi)
{
maxi = mini;
}
Swap(&a[end], &a[maxi]);
++begin;
--end;
}
}
堆排序
堆排序前面文章有過詳細(xì)講解，這里就不多贅述了
數(shù)據(jù)結(jié)構(gòu)—手撕圖解堆
直接上代碼實(shí)現(xiàn)
void Swap(int* p, int* c)
{
int tmp = *p;
*p = *c;
*c = tmp;
}
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[parent] < a[child])
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
// 建堆
for (int i = (n - 2) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
// 堆排序
int end = n - 1;
while (end)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}
}
交換排序
冒泡排序
入門出學(xué)的第一個(gè)排序，效率很低
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int flag = 0;
for (int j = 0; j < n - i - 1; j++)
{
if (a[j] > a[j + 1])
{
flag = 1;
int tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
}
}
if (flag == 0)
{
break;
}
}
}
下面重點(diǎn)是對(duì)快速排序進(jìn)行學(xué)習(xí)，快速排序正常來說是泛用性最廣的排序算法
快速排序
快速排序是所有排序算法中速度最快的一個(gè)排序算法（在數(shù)據(jù)量很龐大的前提下），因此，很多庫中自帶的sort都是用快速排序做底層實(shí)現(xiàn)的，例如qsort和STL中的sort，因此，學(xué)習(xí)好它是很有必要的
首先說明它的基本思想
基本思路是，選定一個(gè)元素為key，經(jīng)過一系列算法讓原本數(shù)組中比key小的數(shù)據(jù)在key的左邊，比key大的數(shù)據(jù)在key的右邊，然后遞歸進(jìn)入key的左邊，在遞歸函數(shù)中重復(fù)這個(gè)操作，最后就能完成排序，那么第一個(gè)關(guān)鍵點(diǎn)就是如何實(shí)現(xiàn)讓以key為分界點(diǎn)，左右分別是比它大和比它小的？
關(guān)于這個(gè)算法有很多版本，我們一一介紹
hoare版
快速排序的創(chuàng)始人就是hoare，作為快速排序的祖師爺，hoare在研究快速排序自然寫出了對(duì)應(yīng)的算法，那么我們當(dāng)然要先學(xué)習(xí)最經(jīng)典的算法
下面展示hoare算法的示意圖
看完演繹圖和上面的流程圖，大概可以理解hoare算法的基本思路，但其實(shí)還有一些問題，比如最后交換的元素(上圖中為3) 一定比key小嗎？比key大難道不會(huì)讓大的元素到key的左邊嗎？
解釋上述問題的原因
其實(shí)問題的原因就在于left和right誰先走的問題，在上面算法中是讓right先走，這是為什么？
我們假設(shè)中間的元素不是3，而是8 (大于key的都可以) 那么，當(dāng)right繼續(xù)向前走的時(shí)候就會(huì)跳過8，繼續(xù)向前找，最后最壞的結(jié)果會(huì)找到left，而left對(duì)應(yīng)的是和前面交換后的比key小的元素，因此這里只要是right先走，最終和right和left相遇的位置一定比key小！
這個(gè)算法其實(shí)并不好寫，需要控制的變量和問題很多，實(shí)現(xiàn)過程如下
int PartSort1(int* a, int left, int right)
{
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
{
right--;
}
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
return left;
}
注意點(diǎn)
- keyi的選取是left而不是0，因?yàn)楹竺孢f歸的時(shí)候最左邊的元素下標(biāo)不一定是0
- while循環(huán)向前/向后尋找時(shí)要隨時(shí)判斷l(xiāng)eft有沒有小于right，防止越界
- 返回的是左值，這個(gè)左值就是下一次的左邊界或右邊界、
快速排序的實(shí)現(xiàn)
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int keyi = PartSort1(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
后續(xù)的三種寫法只需要替換掉PartSort1即可
挖坑法
代碼實(shí)現(xiàn)如下：
int PartSort2(int* a, int left, int right)
{
int key = a[left];
int hole = left;
while (left < right)
{
while (left<right && a[right]>= key)
{
right--;
}
a[hole] = a[right];
hole = right;
while (left < right && a[left] <= key)
{
left++;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
return hole;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int keyi = PartSort2(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
這個(gè)實(shí)現(xiàn)很簡單，沒有需要額外注意，相較第一個(gè)算法來說更容易理解一些
前后指針法
實(shí)現(xiàn)原理如下圖所示
代碼實(shí)現(xiàn)邏輯如下
int PartSort3(int* a, int left, int right)
{
int cur = left+1;
int prev = left;
int keyi = left;
while (cur <= right)
{
if (a[cur] < a[keyi])
{
++prev;
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[prev], &a[keyi]);
return prev;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int keyi = PartSort3(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
實(shí)際上是prev找cur，如果cur指針對(duì)應(yīng)的值小于key，那么就++prev再交換，否則cur就繼續(xù)前進(jìn)，這樣就能使得cur和prev之間的數(shù)據(jù)全部為比key大的數(shù)據(jù)
快速排序的遞歸展開圖
了解了快速排序的工作原理，獨(dú)立畫出它的遞歸展開圖有助于了解它的工作原理
快速排序的優(yōu)化
快速排序確實(shí)是在很多方面都很優(yōu)秀的排序，但是僅僅用上述的代碼并不能完全解決問題，假設(shè)現(xiàn)在給的序列是一個(gè)按升序排列的序列，那么此時(shí)我們選取的key是最小的數(shù)據(jù)，時(shí)間復(fù)雜度是O(N^2)，但如果每次選取的數(shù)據(jù)恰好是中位數(shù)，那么就是整個(gè)數(shù)據(jù)最高效的方式，時(shí)間復(fù)雜度是O(NlogN)，因此如何優(yōu)化？
常見的優(yōu)化有三數(shù)取中法和遞歸到小的子區(qū)間選取插入排序法
三數(shù)取中法
顧名思義，就是取開頭，末尾和中間的三個(gè)數(shù)，選這三個(gè)數(shù)中最中間的一個(gè)，讓這個(gè)數(shù)作為key
int GetMid(int* a, int left, int right)
{
int midi = (left + right) / 2;
if (a[left] < a[midi])
{
if (a[midi] < a[right])
{
return midi;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
else // a[left] > a[midi]
{
if (a[midi] > a[right])
{
return midi;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
int PartSort1(int* a, int left, int right)
{
int midi = GetMid(a, left, right);
Swap(&a[midi], &a[left]);
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
{
right--;
}
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
return left;
}
int PartSort2(int* a, int left, int right)
{
int midi = GetMid(a, left, right);
Swap(&a[midi], &a[left]);
int key = a[left];
int hole = left;
while (left < right)
{
while (left < right && a[right] >= key)
{
right--;
}
a[hole] = a[right];
hole = right;
while (left < right && a[left] <= key)
{
left++;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
return hole;
}
int PartSort3(int* a, int left, int right)
{
int midi = GetMid(a, left, right);
Swap(&a[midi], &a[left]);
int cur = left+1;
int prev = left;
int keyi = left;
while (cur <= right)
{
if (a[cur] < a[keyi])
{
++prev;
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[prev], &a[keyi]);
return prev;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int keyi = PartSort1(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
快速排序的非遞歸實(shí)現(xiàn)
快速排序是利用遞歸實(shí)現(xiàn)的，而凡是遞歸就有可能爆棧的情況出現(xiàn)，因此這里要準(zhǔn)備快速排序的非遞歸實(shí)現(xiàn)方法
非遞歸實(shí)現(xiàn)是借助棧實(shí)現(xiàn)的，棧是在堆上malloc實(shí)現(xiàn)的，棧區(qū)一般在幾十Mb左右，而堆區(qū)有幾G左右的空間，在堆上完成操作是沒有問題的
當(dāng)left<keyi-1才會(huì)入棧，當(dāng)keyi+1<right才會(huì)入棧
隨著不斷入棧出棧，區(qū)間劃分越來越小，left最終會(huì)等于keyi-1，這樣就不會(huì)入棧，右邊同理，不入棧只出棧，最終棧會(huì)為空，當(dāng)棧為空時(shí)，排序完成
歸并排序
歸并排序的排序原理如下：
從中可以看出，歸并排序的原理就是把一整個(gè)大的，無序的數(shù)組分解成小數(shù)組，直到分到數(shù)組中只有一個(gè)數(shù)，再把數(shù)組組裝成有序的數(shù)組，再把組裝成有序的兩個(gè)數(shù)組合并成有序數(shù)組，再讓這個(gè)有序數(shù)組和另外一個(gè)合并…依次遞歸，這樣就和二叉樹一樣遞歸成了一個(gè)合適的數(shù)組文章來源：http://www.zghlxwxcb.cn/news/detail-611913.html
代碼實(shí)現(xiàn)如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-611913.html
void _MergeSort(int* a, int begin, int end, int* tmp)
{
if (begin == end)
return;
int mid = (begin + end) / 2;
_MergeSort(a, begin, mid, tmp);
_MergeSort(a, mid + 1, end, tmp);
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
}
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)：手撕圖解七大排序(含動(dòng)圖演示)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![數(shù)據(jù)結(jié)構(gòu)——七大排序[源碼+動(dòng)圖+性能測試]](https://imgs.yssmx.com/Uploads/2024/02/706744-1.png)
