排序概念
排序：所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來(lái)的操作。
穩(wěn)定性：假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過(guò)排序，這些記錄的相對(duì)次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱(chēng)這種排序算法是穩(wěn)定的；否則稱(chēng)為不穩(wěn)定的。
內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序。
外部排序：數(shù)據(jù)元素太多不能同時(shí)放在內(nèi)存中，根據(jù)排序過(guò)程的要求不能在內(nèi)外存之間移動(dòng)數(shù)據(jù)的排序。
注：這部分主要是內(nèi)部排序。排序講解都以升序?yàn)槔?/p>
常見(jiàn)的排序算法
常見(jiàn)排序算法的實(shí)現(xiàn)
直接插入排序
（點(diǎn)擊此處跳轉(zhuǎn)，更加詳細(xì)的講解過(guò)程，干貨滿(mǎn)滿(mǎn)?。?br> 動(dòng)圖展示：
插入排序，又叫直接插入排序。實(shí)際中，我們玩撲克牌的時(shí)候，就用了插入排序的思想。
基本思想：
?在待排序的元素中，假設(shè)前n-1個(gè)元素已有序，現(xiàn)將第n個(gè)元素插入到前面已經(jīng)排好的序列中，使得前n個(gè)元素有序。按照此法對(duì)所有元素進(jìn)行插入，直到整個(gè)序列有序。
但我們并不能確定待排元素中究竟哪一部分是有序的，所以我們一開(kāi)始只能認(rèn)為第一個(gè)元素是有序的，依次將其后面的元素插入到這個(gè)有序序列中來(lái)，直到整個(gè)序列有序?yàn)橹埂?br> ?
代碼示例：
//插入排序
void InsertSort(int* a, int n)
{
int i = 0;
for (i = 0; i < n - 1; i++)
{
int end = i;//記錄有序序列的最后一個(gè)元素的下標(biāo)
int tmp = a[end + 1];//待插入的元素
while (end >= 0)
{
if (tmp < a[end])//還需繼續(xù)比較
{
a[end + 1] = a[end];
end--;
}
else//找到應(yīng)插入的位置
{
break;
}
}
a[end + 1] = tmp;
//代碼執(zhí)行到此位置有兩種情況:
//1.待插入元素找到應(yīng)插入位置（break跳出循環(huán)到此）。
//2.待插入元素比當(dāng)前有序序列中的所有元素都小（while循環(huán)結(jié)束后到此）。
}
}
直接插入排序的特性總結(jié)：
1>元素集合越接近有序，直接插入排序算法的時(shí)間效率越高
2>時(shí)間復(fù)雜度：O(N^2)
3>空間復(fù)雜度：O(1)，它是一種穩(wěn)定的排序算法
4>穩(wěn)定性：穩(wěn)定
希爾排序
（點(diǎn)擊此處跳轉(zhuǎn)，更加詳細(xì)的講解過(guò)程，干貨滿(mǎn)滿(mǎn)?。?br> 動(dòng)圖展示：
希爾排序法又稱(chēng)縮小增量法。
基本思想：
先選定一個(gè)整數(shù)gap，把待排序文件中所有記錄分成gap個(gè)組，所有距離為gap的記錄分在同一組內(nèi)，并對(duì)每一組內(nèi)的元素進(jìn)行排序。
然后將gap逐漸減小重復(fù)上述分組和排序的工作。
當(dāng)?shù)竭_(dá)gap=1時(shí)，所有元素在統(tǒng)一組內(nèi)排好序。
靜態(tài)圖展示：
該題中，前兩趟就是希爾排序的預(yù)排序，最后一趟就是希爾排序的直接插入排序。
代碼示例：
//希爾排序
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 2;//gap折半
int i = 0;
//進(jìn)行一趟排序
for (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;
}
}
}
希爾排序的特性總結(jié)：
1>希爾排序是對(duì)直接插入排序的優(yōu)化。
2>當(dāng)gap > 1時(shí)都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap ==
1時(shí)，數(shù)組已經(jīng)接近有序的了，這樣就會(huì)很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。
3>希爾排序的時(shí)間復(fù)雜度不好計(jì)算，因?yàn)間ap的取值方法很多，導(dǎo)致很難去計(jì)算，這里不深究。
4>時(shí)間復(fù)雜度O(N^1.5)
5>空間復(fù)雜度O(1)
6>穩(wěn)定性：不穩(wěn)定。
選擇排序
（點(diǎn)擊此處跳轉(zhuǎn)，更加詳細(xì)的講解過(guò)程，干貨滿(mǎn)滿(mǎn)）
動(dòng)圖展示：
基本思想：
第一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，存放在序列的起始(末尾)位置，
然后選出次小(或次大)的一個(gè)元素，存放在最大(最小)元素的下一個(gè)位置，
重復(fù)這樣的步驟直到全部待排序的數(shù)據(jù)元素排完 。
代碼示例1：
//選擇排序(一次選一個(gè)數(shù))
void SelectSort(int* a, int n)
{
int i = 0;
for (i = 0; i < n; i++)//i代表參與該趟選擇排序的第一個(gè)元素的下標(biāo)
{
int start = i;
int min = start;//記錄最小元素的下標(biāo)
while (start < n)
{
if (a[start] < a[min])
min = start;//最小值的下標(biāo)更新
start++;
}
Swap(&a[i], &a[min]);//最小值與參與該趟選擇排序的第一個(gè)元素交換位置
}
}
代碼示例2：
實(shí)際上，我們可以一趟選出兩個(gè)值，一個(gè)最大值一個(gè)最小值，然后將其放在序列開(kāi)頭和末尾，這樣可以使選擇排序的效率快一倍。
//選擇排序(一次選兩個(gè)數(shù))
void SelectSort(int* a, int n)
{
int left = 0;//記錄參與該趟選擇排序的第一個(gè)元素的下標(biāo)
int right = n - 1;//記錄參與該趟選擇排序的最后一個(gè)元素的下標(biāo)
while (left < right)
{
int minIndex = left;//記錄最小元素的下標(biāo)
int maxIndex = left;//記錄最大元素的下標(biāo)
int i = 0;
//找出最大值及最小值的下標(biāo)
for (i = left; i <= right; i++)
{
if (a[i] < a[minIndex])
minIndex = i;
if (a[i]>a[maxIndex])
maxIndex = i;
}
//將最大值和最小值放在序列開(kāi)頭和末尾
Swap(&a[minIndex], &a[left]);
if (left == maxIndex)
{
maxIndex = minIndex;//防止最大值位于序列開(kāi)頭，被最小值交換
}
Swap(&a[maxIndex], &a[right]);
left++;
right--;
}
}
注意：
在進(jìn)行最小值和最大值同時(shí)交換時(shí)也會(huì)出現(xiàn)一個(gè)問(wèn)題，
如果最大值在起始位置的時(shí)候，交換了最小值之后，最大值就被交換到了min的位置，
如果繼續(xù)交換max，就會(huì)將最小值交換到末尾位置。
所以，在每次交換了最小值之后應(yīng)該判斷一下最大值是否在起始位置，如果在需要將max賦值為min。
直接選擇排序的特性總結(jié)：
1>直接選擇排序思考非常好理解，但是效率不是很好(不論數(shù)組是否有序都會(huì)執(zhí)行原步驟)。實(shí)際中很少使用
2>時(shí)間復(fù)雜度：O(N^2)
3>空間復(fù)雜度：O(1)
4>穩(wěn)定性：不穩(wěn)定
堆排序
（點(diǎn)擊此處跳轉(zhuǎn)，更加詳細(xì)的講解過(guò)程，干貨滿(mǎn)滿(mǎn)）
動(dòng)圖展示：
堆排序即利用堆的思想來(lái)進(jìn)行排序，總共分為兩個(gè)步驟：
-
建堆
升序：建大堆
降序：建小堆 -
利用堆刪除思想來(lái)進(jìn)行排序
建堆和堆刪除中都用到了向下調(diào)整，因此掌握了向下調(diào)整，就可以完成堆排序。這里以升序?yàn)槔?/p>
1.首先應(yīng)該建一個(gè)大堆，不能直接使用堆來(lái)實(shí)現(xiàn)?？梢詫⑿枰判虻臄?shù)組看作是一個(gè)堆，但需要將數(shù)組結(jié)構(gòu)變成堆。
2.我們可以從堆從下往上的第二行最右邊開(kāi)始依次向下調(diào)整直到調(diào)整到堆頂，這樣就可以將數(shù)組調(diào)整成一個(gè)堆，且如果建立的是大堆，堆頂元素為最大值。
3.然后按照堆刪的思想將堆頂和堆底的數(shù)據(jù)交換，但不同的是這里不刪除最后一個(gè)元素
4.這樣最大元素就在最后一個(gè)位置，然后從堆頂向下調(diào)整到倒數(shù)第二個(gè)元素，這樣次大的元素就在堆頂，重復(fù)上述步驟直到只剩堆頂時(shí)停止。
代碼示例：
//堆排序
void HeapSort(int* a, int n)
{
//排升序，建大堆
//從第一個(gè)非葉子結(jié)點(diǎn)開(kāi)始向下調(diào)整，一直到根
int i = 0;
for (i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
int end = n - 1;//記錄堆的最后一個(gè)數(shù)據(jù)的下標(biāo)
while (end)
{
Swap(&a[0], &a[end]);//將堆頂?shù)臄?shù)據(jù)和堆的最后一個(gè)數(shù)據(jù)交換
AdjustDown(a, end, 0);//對(duì)根進(jìn)行一次向下調(diào)整
end--;//堆的最后一個(gè)數(shù)據(jù)的下標(biāo)減一
}
}
直接選擇排序的特性總結(jié)：
1>堆排序使用堆來(lái)選數(shù)，效率就高了很多。
2>時(shí)間復(fù)雜度：O(N*logN)
3>空間復(fù)雜度：O(1)
4>穩(wěn)定性：不穩(wěn)定
冒泡排序
（點(diǎn)擊此處跳轉(zhuǎn)，更加詳細(xì)的講解過(guò)程，干貨滿(mǎn)滿(mǎn)）
動(dòng)圖展示：
冒泡排序應(yīng)該是我們最熟悉的排序了，在C語(yǔ)言階段我們就學(xué)習(xí)了冒泡排序。
他的思想也非常簡(jiǎn)單：
兩兩元素相比，前一個(gè)比后一個(gè)大就交換，直到將最大的元素交換到末尾位置。這是第一趟
一共進(jìn)行n-1趟這樣的交換將可以把所有的元素排好。
( n-1趟是因?yàn)橹皇蓚€(gè)元素時(shí)只需要一趟就可以完成)
代碼示例：
//冒泡排序
void BubbleSort(int* a, int n)
{
int end = 0;
for (end = n - 1; end >= 0; end--)
{
int exchange = 0;//記錄該趟冒泡排序是否進(jìn)行過(guò)交換
int i = 0;
for (i = 0; i < end; i++)
{
if (a[i]>a[i + 1])
{
Swap(&a[i], &a[i + 1]);
exchange = 1;
}
}
if (exchange == 0)//該趟冒泡排序沒(méi)有進(jìn)行過(guò)交換，已有序
break;
}
}
冒泡排序的特性總結(jié)：
1>冒泡排序是一種非常容易理解的排序
2>時(shí)間復(fù)雜度：O(N^2)
3>空間復(fù)雜度：O(1)
4>穩(wěn)定性：穩(wěn)定
快速排序
（點(diǎn)擊此處跳轉(zhuǎn)，更加詳細(xì)的講解過(guò)程，干貨滿(mǎn)滿(mǎn)）
這里是排序算法的重點(diǎn)了，非常重要！
快速排序是Hoare于1962年提出的一種二叉樹(shù)結(jié)構(gòu)的交換排序方法，
其基本思想為：
任取待排序元素序列中的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過(guò)程，直到所有元素都排列在相應(yīng)位置上為止。
遞歸實(shí)現(xiàn)
Hoare版本
動(dòng)圖展示：
具體思路是：
1.選定一個(gè)基準(zhǔn)值，最好選定最左邊或者最右邊，選中間會(huì)給自己找麻煩。
2.確定兩個(gè)指針left 和right 分別從左邊和右邊向中間遍歷數(shù)組。
3.如果選最右邊為基準(zhǔn)值，那么left指針先走，如果遇到大于基準(zhǔn)值的數(shù)就停下來(lái)。
4.然后右邊的指針再走，遇到小于基準(zhǔn)值的數(shù)就停下來(lái)。
5.交換left和right指針對(duì)應(yīng)位置的值。
6.重復(fù)以上步驟，直到left = right ，最后將基準(zhǔn)值與left(right)位置的值交換。
這樣基準(zhǔn)值左邊的所有數(shù)都比他小，而他右邊的數(shù)都比他大，從而他所在的位置就是排序后的正確位置。
之后再遞歸排以基準(zhǔn)值為界限的左右兩個(gè)區(qū)間中的數(shù)，當(dāng)區(qū)間中沒(méi)有元素時(shí)，排序完成。
代碼展示：
//快速排序（Hoare版本）
void QuickSort1(int* a, int begin, int end)
{
if (begin >= end)//當(dāng)只有一個(gè)數(shù)據(jù)或是序列不存在時(shí)，不需要進(jìn)行操作
return;
int left = begin;//L
int right = end;//R
int keyi = left;//key的下標(biāo)
while (left < right)
{
//right先走，找小
while (left < right&&a[right] >= a[keyi])
{
right--;
}
//left后走，找大
while (left < right&&a[left] <= a[keyi])
{
left++;
}
if (left < right)//交換left和right的值
{
Swap(&a[left], &a[right]);
}
}
int meeti = left;//L和R的相遇點(diǎn)
Swap(&a[keyi], &a[meeti]);//交換key和相遇點(diǎn)的值
QuickSort1(a, begin, meeti - 1);//key的左序列進(jìn)行此操作
QuickSort1(a, meeti + 1, end);//key的右序列進(jìn)行此操作
}
挖坑法
動(dòng)圖展示：
具體思路是：
1.先將選定的基準(zhǔn)值(最左邊)直接取出，然后留下一個(gè)坑，
2.當(dāng)右指針遇到小于基準(zhǔn)值的數(shù)時(shí)，直接將該值放入坑中，而右指針指向的位置形成新的坑位，
3.然后左指針遇到大于基準(zhǔn)值的數(shù)時(shí)，將該值放入坑中，左指針指向的位置形成坑位，
4.重復(fù)該步驟，直到左右指針相等。最后將基準(zhǔn)值放入坑位之中。
代碼展示：
//快速排序（挖坑法）
void QuickSort2(int* a, int begin, int end)
{
if (begin >= end)//當(dāng)只有一個(gè)數(shù)據(jù)或是序列不存在時(shí)，不需要進(jìn)行操作
return;
int left = begin;//L
int right = end;//R
int key = a[left];//在最左邊形成一個(gè)坑位
while (left < right)
{
//right向左，找小
while (left < right&&a[right] >= key)
{
right--;
}
//填坑
a[left] = a[right];
//left向右，找大
while (left < right&&a[left] <= key)
{
left++;
}
//填坑
a[right] = a[left];
}
int meeti = left;//L和R的相遇點(diǎn)
a[meeti] = key;//將key拋入坑位
QuickSort2(a, begin, meeti - 1);//key的左序列進(jìn)行此操作
QuickSort2(a, meeti + 1, end);//key的右序列進(jìn)行此操作
}
前后指針?lè)?/h6>
動(dòng)圖展示：
具體思路是：
1.選定基準(zhǔn)值，定義prev和cur指針(cur = prev + 1)
2.cur先走，遇到小于基準(zhǔn)值的數(shù)停下，然后將prev向后移動(dòng)一個(gè)位置
3.將prev對(duì)應(yīng)值與cur對(duì)應(yīng)值交換
4.重復(fù)上面的步驟，直到cur走出數(shù)組范圍
5.最后將基準(zhǔn)值與prev對(duì)應(yīng)位置交換
6.遞歸排序以基準(zhǔn)值為界限的左右區(qū)間
代碼展示：
//快速排序（前后指針?lè)ǎ?/span>
void QuickSort3(int* a, int begin, int end)
{
if (begin >= end)//當(dāng)只有一個(gè)數(shù)據(jù)或是序列不存在時(shí)，不需要進(jìn)行操作
return;
//三數(shù)取中
int midIndex = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[midIndex]);
int prev = begin;
int cur = begin + 1;
int keyi = begin;
while (cur <= end)//當(dāng)cur未越界時(shí)繼續(xù)
{
if (a[cur] < a[keyi] && ++prev != cur)//cur指向的內(nèi)容小于key
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
int meeti = prev;//cur越界時(shí)，prev的位置
Swap(&a[keyi], &a[meeti]);//交換key和prev指針指向的內(nèi)容
QuickSort3(a, begin, meeti - 1);//key的左序列進(jìn)行此操作
QuickSort3(a, meeti + 1, end);//key的右序列進(jìn)行此操作
}
非遞歸實(shí)現(xiàn)
當(dāng)我們需要將一個(gè)用遞歸實(shí)現(xiàn)的算法改為非遞歸時(shí)，一般需要借用一個(gè)數(shù)據(jù)結(jié)構(gòu)，那就是棧。將Hoare版本、挖坑法以及前后指針?lè)ǖ目焖倥判蚋臑榉沁f歸版本，其實(shí)主體思想一致，只是調(diào)用的單趟排序的算法不同而已。
?于是我們可以先將Hoare版本、挖坑法和前后指針?lè)ǖ膯翁伺判騿为?dú)封裝起來(lái)。然后寫(xiě)一個(gè)非遞歸的快速排序，在函數(shù)內(nèi)部調(diào)用單趟排序的函數(shù)即可。
快速排序的非遞歸算法基本思路：
?1、先將待排序列的第一個(gè)元素的下標(biāo)和最后一個(gè)元素的下標(biāo)入棧。
?2、當(dāng)棧不為空時(shí)，讀取棧中的信息（一次讀取兩個(gè)：一個(gè)是L，另一個(gè)是R），然后調(diào)用某一版本的單趟排序，排完后獲得了key的下標(biāo)，然后判斷key的左序列和右序列是否還需要排序，若還需要排序，就將相應(yīng)序列的L和R入棧；若不需排序了（序列只有一個(gè)元素或是不存在），就不需要將該序列的信息入棧。
?3、反復(fù)執(zhí)行步驟2，直到棧為空為止。
代碼示例：
//快速排序（非遞歸實(shí)現(xiàn)）
void QuickSortNonR(int* a, int begin, int end)
{
Stack st;//創(chuàng)建棧
StackInit(&st);//初始化棧
StackPush(&st, begin);//待排序列的L
StackPush(&st, end);//待排序列的R
while (!StackEmpty(&st))
{
int right = StackTop(&st);//讀取R
StackPop(&st);//出棧
int left = StackTop(&st);//讀取L
StackPop(&st);//出棧
//該處調(diào)用的是Hoare版本的單趟排序
int keyi = PartSort1(a, left, right);
if (left < keyi - 1)//該序列的左序列還需要排序
{
StackPush(&st, left);//左序列的L入棧
StackPush(&st, keyi - 1);//左序列的R入棧
}
if (keyi + 1 < right)// 該序列的右序列還需要排序
{
StackPush(&st, keyi + 1);//右序列的L入棧
StackPush(&st, right);//右序列的R入棧
}
}
StackDestroy(&st);//銷(xiāo)毀棧
}
Hoare版本
代碼示例：
//Hoare版本（單趟排序）
int PartSort1(int* a, int left, int right)
{
int keyi = left;//key的下標(biāo)
while (left < right)
{
//right走，找小
while (left < right&&a[right] >= a[keyi])
{
right--;
}
//left先走，找大
while (left < right&&a[left] <= a[keyi])
{
left++;
}
if (left < right)
{
Swap(&a[left], &a[right]);//交換left和right的值
}
}
int meeti = left;//L和R的相遇點(diǎn)
Swap(&a[keyi], &a[meeti]);//交換key和相遇點(diǎn)的值
return meeti;//返回相遇點(diǎn)，即key的當(dāng)前位置
}
挖坑法
代碼示例：
//挖坑法（單趟排序）
int PartSort2(int* a, int left, int right)
{
int key = a[left];//在最左邊形成一個(gè)坑位
while (left < right)
{
//right向左，找小
while (left < right&&a[right] >= key)
{
right--;
}
//填坑
a[left] = a[right];
//left向右，找大
while (left < right&&a[left] <= key)
{
left++;
}
//填坑
a[right] = a[left];
}
int meeti = left;//L和R的相遇點(diǎn)
a[meeti] = key;//將key拋入坑位
return meeti;//返回key的當(dāng)前位置
}
前后指針?lè)?/h6>
代碼示例：
//前后指針?lè)ǎ▎翁伺判颍?/span>
int PartSort3(int* a, int left, int right)
{
int prev = left;
int cur = left + 1;
int keyi = left;
while (cur <= right)//當(dāng)cur未越界時(shí)繼續(xù)
{
if (a[cur] < a[keyi] && ++prev != cur)//cur指向的內(nèi)容小于key
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
int meeti = prev;//cur越界時(shí)，prev的位置
Swap(&a[keyi], &a[meeti]);//交換key和prev指針指向的內(nèi)容
return meeti;//返回key的當(dāng)前位置
}
快速排序倆個(gè)優(yōu)化
但是上面的程序還有一些缺陷：
在基準(zhǔn)值的選擇上，如果選擇的基準(zhǔn)值為恰好為最小值，會(huì)進(jìn)行不必要的遞歸。
在排序大量有序數(shù)據(jù)或者接近有序數(shù)據(jù)時(shí)，效率會(huì)比較低，甚至可能會(huì)出現(xiàn)程序崩潰的情況。
這是因?yàn)樵谂判蛴行驍?shù)據(jù)時(shí)，快速排序的遞歸調(diào)用次數(shù)過(guò)多，會(huì)導(dǎo)致棧溢出的情況。
為了解決這些問(wèn)題，這里有兩種優(yōu)化方法：
1> 三數(shù)取中法選基準(zhǔn)值
2> 遞歸到小的子區(qū)間時(shí)，可以考慮使用插入排序
三數(shù)取中法取基準(zhǔn)值：即在在起始位置，中間位置，末尾位置中選出中間值，作為基準(zhǔn)值。
代碼示例：
//三數(shù)取中
int GetMidIndex(int* a, int left, int right)
{
int mid = left + (right - left) / 2;
if (a[mid] > a[left])
{
if (a[mid] < a[right])
return mid;
else if (a[left]>a[right])
return left;
else
return right;
}
else
{
if (a[mid] > a[right])
return mid;
else if (a[left] > a[right])
return right;
else
return left;
}
}
小區(qū)間優(yōu)化：類(lèi)似于二叉樹(shù)，每個(gè)子樹(shù)都會(huì)進(jìn)行一次遞歸調(diào)用，越到下面遞歸調(diào)用會(huì)越多。為了減少遞歸調(diào)用，當(dāng)?shù)竭f歸到下層時(shí)，我們可以使用其他的排序來(lái)替代。這里我們使用插入排序。
代碼示例：
//優(yōu)化后的快速排序
void QuickSort0(int* a, int begin, int end)
{
if (begin >= end)//當(dāng)只有一個(gè)數(shù)據(jù)或是序列不存在時(shí)，不需要進(jìn)行操作
return;
if (end - begin + 1 > 20)//可自行調(diào)整
{
//可調(diào)用快速排序的單趟排序三種中的任意一種
//int keyi = PartSort1(a, begin, end);
//int keyi = PartSort2(a, begin, end);
int keyi = PartSort3(a, begin, end);
QuickSort(a, begin, keyi - 1);//key的左序列進(jìn)行此操作
QuickSort(a, keyi + 1, end);//key的右序列進(jìn)行此操作
}
else
{
//HeapSort(a, end - begin + 1);
ShellSort(a, end - begin + 1);//當(dāng)序列長(zhǎng)度小于等于20時(shí)，使用希爾排序
}
}
快速排序的特性總結(jié)：
1>快速排序整體的綜合性能和使用場(chǎng)景都是比較好的，所以才敢叫快速排序
2>時(shí)間復(fù)雜度：O(N*logN)
3>空間復(fù)雜度：O(logN)
4>穩(wěn)定性：不穩(wěn)定
歸并排序
（點(diǎn)擊此處跳轉(zhuǎn)，更加詳細(xì)的講解過(guò)程，干貨滿(mǎn)滿(mǎn)）
動(dòng)圖展示：
基本思想：
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide andConquer）的一個(gè)非常典型的應(yīng)用。
將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。
若將兩個(gè)有序表合并成一個(gè)有序表，稱(chēng)為二路歸并。
圖片展示：
按照其算法思想：
首先應(yīng)在數(shù)組中找出有序的序列，但數(shù)組是否有序編譯器可不知道。
所以可以將數(shù)組劃分，一分二，二分四…直到每個(gè)序列中只有一個(gè)數(shù)字。
一個(gè)數(shù)字總可以認(rèn)為他是有序的吧。
最后將同時(shí)劃分的序列合并。
遞歸實(shí)現(xiàn)
歸并排序，從其思想上看就很適合使用遞歸來(lái)實(shí)現(xiàn)，并且用遞歸實(shí)現(xiàn)也比較簡(jiǎn)單。其間我們需要申請(qǐng)一個(gè)與待排序列大小相同的數(shù)組用于合并過(guò)程兩個(gè)有序的子序列，合并完畢后再將數(shù)據(jù)拷貝回原數(shù)組。
代碼示例：
//歸并排序（子函數(shù)）
void _MergeSort(int* a, int left, int right, int* tmp)
{
if (left >= right)//歸并結(jié)束條件：當(dāng)只有一個(gè)數(shù)據(jù)或是序列不存在時(shí)，不需要再分解
{
return;
}
int mid = left + (right - left) / 2;//中間下標(biāo)
_MergeSort(a, left, mid, tmp);//對(duì)左序列進(jìn)行歸并
_MergeSort(a, mid + 1, right, tmp);//對(duì)右序列進(jìn)行歸并
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
//將兩段子區(qū)間進(jìn)行歸并，歸并結(jié)果放在tmp中
int i = left;
while (begin1 <= end1&&begin2 <= end2)
{
//將較小的數(shù)據(jù)優(yōu)先放入tmp
if (a[begin1] < a[begin2])
tmp[i++] = a[begin1++];
else
tmp[i++] = a[begin2++];
}
//當(dāng)遍歷完其中一個(gè)區(qū)間，將另一個(gè)區(qū)間剩余的數(shù)據(jù)直接放到tmp的后面
while (begin1 <= end1)
tmp[i++] = a[begin1++];
while (begin2 <= end2)
tmp[i++] = a[begin2++];
//歸并完后，拷貝回原數(shù)組
int j = 0;
for (j = left; j <= right; j++)
a[j] = tmp[j];
}
//歸并排序（主體函數(shù)）
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int)*n);//申請(qǐng)一個(gè)與原數(shù)組大小相同的空間
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
_MergeSort(a, 0, n - 1, tmp);//歸并排序
free(tmp);//釋放空間
}
非遞歸實(shí)現(xiàn)
非遞歸實(shí)現(xiàn)的思想與遞歸實(shí)現(xiàn)的思想是類(lèi)似的。
不同的是，這里的序列劃分過(guò)程和遞歸是相反的，不是一次一分為二，而是先1個(gè)元素一組，再2個(gè)元素一組，4個(gè)元素一組…直到將所有的元素歸并完。
代碼示例：
//歸并排序（子函數(shù)）
void _MergeSortNonR(int* a, int* tmp, int begin1, int end1, int begin2, int end2)
{
int j = begin1;
//將兩段子區(qū)間進(jìn)行歸并，歸并結(jié)果放在tmp中
int i = begin1;
while (begin1 <= end1&&begin2 <= end2)
{
//將較小的數(shù)據(jù)優(yōu)先放入tmp
if (a[begin1] < a[begin2])
tmp[i++] = a[begin1++];
else
tmp[i++] = a[begin2++];
}
//當(dāng)遍歷完其中一個(gè)區(qū)間，將另一個(gè)區(qū)間剩余的數(shù)據(jù)直接放到tmp的后面
while (begin1 <= end1)
tmp[i++] = a[begin1++];
while (begin2 <= end2)
tmp[i++] = a[begin2++];
//歸并完后，拷貝回原數(shù)組
for (; j <= end2; j++)
a[j] = tmp[j];
}
//歸并排序（主體函數(shù)）
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int)*n);//申請(qǐng)一個(gè)與待排序列大小相同的空間，用于輔助合并序列
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
int gap = 1;//需合并的子序列中元素的個(gè)數(shù)
while (gap < n)
{
int i = 0;
for (i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
if (begin2 >= n)//最后一組的第二個(gè)小區(qū)間不存在或是第一個(gè)小區(qū)間不夠gap個(gè)，此時(shí)不需要對(duì)該小組進(jìn)行合并
break;
if (end2 >= n)//最后一組的第二個(gè)小區(qū)間不夠gap個(gè)，則第二個(gè)小區(qū)間的后界變?yōu)閿?shù)組的后界
end2 = n - 1;
_MergeSortNonR(a, tmp, begin1, end1, begin2, end2);//合并兩個(gè)有序序列
}
gap = 2 * gap;//下一趟需合并的子序列中元素的個(gè)數(shù)翻倍
}
free(tmp);//釋放空間
}
外排序
上面介紹的排序算法均是在內(nèi)存中進(jìn)行的，對(duì)于數(shù)據(jù)量龐大的序列，上面介紹的排序算法都束手無(wú)策，而歸并排序卻能勝任這種海量數(shù)據(jù)的排序。
假設(shè)現(xiàn)在有10億個(gè)整數(shù)（4GB）存放在文件A中，需要我們進(jìn)行排序，而內(nèi)存一次只能提供512MB空間，歸并排序解決該問(wèn)題的基本思路如下：
?1、每次從文件A中讀取八分之一，即512MB到內(nèi)存中進(jìn)行排序（內(nèi)排序），并將排序結(jié)果寫(xiě)入到一個(gè)文件中，然后再讀取八分之一，重復(fù)這個(gè)過(guò)程。那么最終會(huì)生成8個(gè)各自有序的小文件（A1~A8）。
?2、對(duì)生成的8個(gè)小文件進(jìn)行1 1合并，最終8個(gè)文件被合成為4個(gè)，然后再1 1合并，就變成2個(gè)文件了，最后再進(jìn)行一次1 1合并，就變成1個(gè)有序文件了。
注意：這里將兩個(gè)文件進(jìn)行1 1合并，并不是先將兩個(gè)文件讀入內(nèi)存然后進(jìn)行合并，因?yàn)閮?nèi)存裝不下。這里的11合并是利用文件輸入輸出函數(shù)，從兩個(gè)文件中各自讀取一個(gè)數(shù)據(jù)，然后進(jìn)行比較，將較小的數(shù)據(jù)寫(xiě)入到一個(gè)新文件中去，然后再讀取，再比較，再寫(xiě)入，最終將兩個(gè)文件中的數(shù)據(jù)全部寫(xiě)入到另一個(gè)文件中去，那么此時(shí)這個(gè)文件又是一個(gè)有序的文件了。
歸并排序的特性總結(jié)：
1>歸并的缺點(diǎn)在于需要O(N)的空間復(fù)雜度，歸并排序的思考更多的是解決在磁盤(pán)中的外排序問(wèn)題。
2>時(shí)間復(fù)雜度：O(N*logN)
3>空間復(fù)雜度：O(N)
4>穩(wěn)定性：穩(wěn)定
計(jì)數(shù)排序
（點(diǎn)擊此處跳轉(zhuǎn)，更加詳細(xì)的講解過(guò)程，干貨滿(mǎn)滿(mǎn)）
動(dòng)圖展示：
思想：
計(jì)數(shù)排序又稱(chēng)為鴿巢原理，是對(duì)哈希直接定址法的變形應(yīng)用。 操作步驟
- 統(tǒng)計(jì)相同元素出現(xiàn)次數(shù)
- 根據(jù)統(tǒng)計(jì)的結(jié)果將序列回收到原來(lái)的序列中
代碼示例：
//計(jì)數(shù)排序
void CountSort(int* a, int n)
{
int min = a[0];//記錄數(shù)組中的最小值
int max = a[0];//記錄數(shù)組中的最大值
for (int i = 0; i < n; i++)
{
if (a[i] < min)
min = a[i];
if (a[i] > max)
max = a[i];
}
int range = max - min + 1;//min和max之間的自然數(shù)個(gè)數(shù)（包括min和max本身）
int* count = (int*)calloc(range, sizeof(int));//開(kāi)辟可儲(chǔ)存range個(gè)整型的內(nèi)存空間，并將內(nèi)存空間置0
if (count == NULL)
{
printf("malloc fail\n");
exit(-1);
}
//統(tǒng)計(jì)相同元素出現(xiàn)次數(shù)（相對(duì)映射）
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
}
int i = 0;
//根據(jù)統(tǒng)計(jì)結(jié)果將序列回收到原來(lái)的序列中
for (int j = 0; j < range; j++)
{
while (count[j]--)
{
a[i++] = j + min;
}
}
free(count);//釋放空間
}
注意：計(jì)數(shù)排序在排負(fù)數(shù)時(shí)，可將負(fù)數(shù)的類(lèi)型轉(zhuǎn)化成 unsigned int。
數(shù)組中元素有正有負(fù)的情況時(shí)不適用計(jì)數(shù)排序。
計(jì)數(shù)排序的特性總結(jié)：
1>計(jì)數(shù)排序在數(shù)據(jù)范圍集中時(shí)，效率很高，但是適用范圍及場(chǎng)景有限。 2>時(shí)間復(fù)雜度：O(MAX(N,范圍))
3>空間復(fù)雜度：O(范圍)
4>穩(wěn)定性：穩(wěn)定
常見(jiàn)排序算法的性能分析
最后我們對(duì)各種排序算法進(jìn)行一個(gè)簡(jiǎn)單的測(cè)試：隨機(jī)測(cè)試10000個(gè)數(shù)據(jù)
我們借此來(lái)觀察一下各個(gè)排序算法所用時(shí)長(zhǎng)的差異
void TestOP()
{
srand(time(0));
const int N = 100000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);
int* a5 = (int*)malloc(sizeof(int) * N);
int* a6 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
a1[i] = rand(); //獲得隨機(jī)數(shù)
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
}
//直接插入排序
int begin1 = clock();
InsertSort(a1, N);
int end1 = clock();
//希爾排序
int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();
//選擇排序
int begin3 = clock();
SelectSort(a3, N);
int end3 = clock();
//堆排序
int begin4 = clock();
HeapSort(a4, N);
int end4 = clock();
//快速排序
int begin5 = clock();
QuickSort(a5, 0, N - 1);
int end5 = clock();
//歸并排序
int begin6 = clock();
MergeSort(a6, N);
int end6 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelectSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
printf("QuickSort:%d\n", end5 - begin5);
printf("MergeSort:%d\n", end6 - begin6);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
}
由此可見(jiàn)，不同的排序算法之間差異性較大，大家應(yīng)該根據(jù)不同的應(yīng)用場(chǎng)景來(lái)選擇合適的排序算法。
最后，給出所有排序算法的時(shí)間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性的對(duì)比表格，希望大家能夠有所收獲。
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-493410.html
如此明了清晰的詳解過(guò)程，希望各位看官能夠一鍵三連哦??文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-493410.html
到了這里，關(guān)于八大排序：直接插入排序、希爾排序、選擇排序、堆排序、冒泡排序、快速排序、歸并排序、計(jì)數(shù)排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
