一、常見(jiàn)的排序算法
排序在我們生活中處處可見(jiàn)，所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來(lái)的操作。
常見(jiàn)的排序算法可以分為四大類(lèi)：插入排序，選擇排序，交換排序，歸并排序；其中，插入排序分為直接插入排序和希爾排序；選擇排序分為直接選擇排序和堆排序；交換排序分為冒泡排序和快速排序；歸并排序歸為一大類(lèi)；
下面我們逐一分析每一個(gè)排序的算法思路以及優(yōu)缺點(diǎn)和穩(wěn)定性；
二、常見(jiàn)排序算法的實(shí)現(xiàn)
1. 直接插入排序
直接插入排序是一種簡(jiǎn)單的插入排序法，其基本思想是：把待排序的記錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個(gè)新的有序序列 。
//直接插入排序
void InsertSort(int* a, int n)
{
for (int i = 1; i < n; i++)
{
int tmp = a[i];
int end = i - 1;
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
}
else
{
break;
}
end--;
}
a[end + 1] = tmp;
}
}
當(dāng)插入第i(i>=1)個(gè)元素時(shí)，前面的 a[0],a[1],…,a[i-1] 已經(jīng)排好序，即 0 到 end 的區(qū)間已經(jīng)排好序，此時(shí)用 a[i] 的下標(biāo)與 a[i-1] , a[i-2] ,…的下標(biāo)從 end 開(kāi)始往前進(jìn)行比較，找到符合條件的插入位置即將 a[i] 插入，原來(lái)位置上的元素順序后移；
如圖，下標(biāo)為 0 - end（0 - 0） 的區(qū)間上只有一個(gè)元素，即已經(jīng)排好序，i 為 end 的后一個(gè)下標(biāo)，然后 i 從 end 開(kāi)始往前進(jìn)行比較，遇到比自己大的就繼續(xù)走，直到遇到比自己小的元素，就在這個(gè)位置插入；
原來(lái)這個(gè)位置上的元素往后移動(dòng)；注意是先移動(dòng)再插入，否則會(huì)覆蓋數(shù)據(jù)；
第二輪插入：
如圖所示這三個(gè)數(shù)就排好序了；
排序的動(dòng)圖如下：
直接插入排序的特性總結(jié)：
- 元素集合越接近有序，直接插入排序算法的時(shí)間效率越高
- 時(shí)間復(fù)雜度：O(N^2)
- 空間復(fù)雜度：O(1)，它是一種穩(wěn)定的排序算法
- 穩(wěn)定性：穩(wěn)定
2. 希爾排序
希爾排序法又稱(chēng)縮小增量法，希爾排序法的基本思想是：先選定一個(gè)整數(shù) gap，把待排序文件中所有記錄分成 gap 個(gè)組，所有距離為 gap 的記錄分在同一組內(nèi)（即間隔為 gap 分為一組，總計(jì) gap 組），并對(duì)每一組內(nèi)的記錄進(jìn)行排序。然后取重復(fù)上述分組和排序的工作。當(dāng) gap = 1時(shí)，所有記錄在統(tǒng)一組內(nèi)排好序。
希爾排序其實(shí)是對(duì)直接插入排序的優(yōu)化，當(dāng) gap > 1 時(shí)都是預(yù)排序（對(duì) gap 組數(shù)據(jù)分別進(jìn)行插入排序），目的是讓數(shù)組更接近于有序；當(dāng) gap == 1 時(shí)，即每一個(gè)元素都是獨(dú)立的一組，也就變成了直接插入排序；
gap 的選值是不一定的，我們按照大概數(shù)組長(zhǎng)度的三分之一來(lái)選值；例如{ 6,1,2,7,9,3,4,5,10,8,0 } 這個(gè)數(shù)組，我們按照 gap = gap / 3 + 1 來(lái)選取 gap 的值，數(shù)組被分成 gap == 4 組，每個(gè)組之間的元素間隔 gap == 4 個(gè)元素；如圖所示，不同顏色的線段區(qū)間代表不同的 gap 組：
每個(gè) gap 組排好序的數(shù)組如原數(shù)組的上方數(shù)據(jù)所示：
然后 gap 再按照上面的取值方式繼續(xù)計(jì)算，gap 得到 2，按照 gap == 2 的分組分成以下組別，一共兩組，每個(gè)組之間的元素間隔 gap == 2 個(gè)元素：
每個(gè) gap 組排好序的數(shù)組如原數(shù)組的上方數(shù)據(jù)所示：
從目前的數(shù)組的排列可以看出，數(shù)組已經(jīng)很接近有序了，此時(shí)我們只要繼續(xù)按照 gap 的取值方式取 gap 值，會(huì)得到 gap == 1，即進(jìn)行直接插入排序，這樣我們就排好了一段數(shù)組；gap 按照 gap = gap / 3 + 1 的方式取值的原因是因?yàn)椋詈蟮?+ 1可以保證最后一次 gap 的取值一定是 1 ，即最后一次排序一定會(huì)執(zhí)行直接插入排序；
實(shí)現(xiàn)的代碼如下：
//希爾排序
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
// +1保證最后一次一定是1
gap = gap / 3 + 1;
// 多組并排
// i < n - gap 保證與數(shù)組的長(zhǎng)度有 gap 的距離，不會(huì)越界；并分成了 gap 組；
for (int i = 0; i < n - gap; i++)
{
// 以 gap 為間距直接進(jìn)行插入排序，多個(gè)組同時(shí)進(jìn)行插入排序
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
希爾排序的時(shí)間復(fù)雜度不好計(jì)算，因?yàn)間ap的取值方法很多，導(dǎo)致很難去計(jì)算，總體的時(shí)間復(fù)雜度在 O(NlogN)~O(N^2)，最好的情況時(shí)間復(fù)雜度為 O(N^1.3)；空間復(fù)雜度為 O(1)，因?yàn)闆](méi)有使用額外的空間；希爾排序的穩(wěn)定性是不穩(wěn)定的；
3. 直接選擇排序
選擇排序的思想是，每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完 。
動(dòng)圖如下。動(dòng)圖提供的思路是每次只選一個(gè)最小的元素放到數(shù)組的最左邊，而我們的思路是同時(shí)選出最大元素和最小元素，將最大的元素放到最右邊，最小的元素放到最左邊，這算是一個(gè)小小的優(yōu)化；
例如 { 5，3，4，1，2 } 這個(gè)數(shù)組，begin 和 end 記錄數(shù)組的頭和尾，maxi 和 mini 記錄除了已排序好的元素之外的最大元素和最小元素的下標(biāo)，如下圖，此時(shí) begin 和 end 維護(hù)這一段數(shù)組，目前這段數(shù)組是無(wú)序的，maxi 和 mini 都從 begin 開(kāi)始遍歷，分別尋找最大元素和最小元素的下標(biāo)；然后先對(duì) a[maxi] 和 a[end] 進(jìn)行交換，將最大元素放到最后；然后交換 a[mini] 和 a[begin]，將最小的元素?fù)Q到前面去；最后 begin++， end- -，縮小數(shù)組范圍；
進(jìn)行第二次選擇排序，此時(shí) mini 和 end 重合，如果先交換 a[maxi] 和 a[end]，原來(lái)的 a[mini] 是最小元素，交換后就會(huì)變成原來(lái)的 a[maxi]，即現(xiàn)在的 a[end]，即變成了最大的元素（因?yàn)?end 和 mini 重合），所以此時(shí)要進(jìn)行判斷， mini 和 end 如果重合則說(shuō)明原來(lái)的 mini 現(xiàn)在已經(jīng)被換到 maxi 的位置了，所以要進(jìn)行 mini = maxi 操作；
交換后：
改正后：
最后排序完：
以下是參考代碼：
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//選擇排序
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[end], &a[maxi]);
//end 和 mini 重合
if (mini == end)
mini = maxi;
Swap(&a[begin], &a[mini]);
begin++;
end--;
}
}
直接選擇排序的特性總結(jié)：
- 直接選擇排序思考好理解，但是效率不是很好，實(shí)際中很少使用
- 時(shí)間復(fù)雜度：O(N^2)
- 空間復(fù)雜度：O(1)
- 穩(wěn)定性：不穩(wěn)定
4. 堆排序
堆排序(Heapsort)是指利用堆積樹(shù)（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種。它是通過(guò)堆來(lái)進(jìn)行選擇數(shù)據(jù)。要注意的是排升序要建大堆，排降序建小堆。
例如一個(gè)數(shù)組 { 5，2，1，3，7，6，4 }，這個(gè)數(shù)組的樹(shù)形結(jié)構(gòu)如下圖：
將它建成大堆，其中建堆的思路在這里不細(xì)說(shuō)，詳細(xì)請(qǐng)看往期博客鏈接 二叉樹(shù)—堆，建成的大堆如下圖：
堆排序的思路是，首先要建立一個(gè)堆，現(xiàn)在已經(jīng)建立好大堆，升序要建大堆，因?yàn)榇蠖阎?，大的在前面，每次讓堆頂?shù)臄?shù)據(jù)與堆尾的數(shù)據(jù)的值進(jìn)行交換，交換完長(zhǎng)度減一，相當(dāng)于最大的放到后面就不動(dòng)了，然后再?gòu)亩秧旈_(kāi)始向下調(diào)整，次大的調(diào)到堆頂，然后和倒數(shù)第二的數(shù)據(jù)的值進(jìn)行交換…直到長(zhǎng)度減到0，就完成了排序；
例如上圖的大堆中，7 和 4 交換后 size 減減，我們操作的堆，表面上邏輯結(jié)構(gòu)是一個(gè)堆，實(shí)際上我們操作的是一個(gè)數(shù)組，所以交換后 7 交換到數(shù)組的最后，7 是最大的元素，所以將長(zhǎng)度減一，就說(shuō)明已經(jīng)排序好了一個(gè)元素，排序完一個(gè)元素就繼續(xù)從堆頂開(kāi)始進(jìn)行向下調(diào)整，因?yàn)槌硕秧數(shù)脑?，它已?jīng)是一個(gè)堆，所以可以直接從堆頂開(kāi)始進(jìn)行向下調(diào)整算法繼續(xù)建堆；
參考代碼如下：
//向下調(diào)整算法
void AdjustDown(int* a, int n, int parent)
{
int child = 2 * parent + 1;
while (child < n)
{
if (child + 1 < n && a[child] < a[child + 1])
{
child++;
}
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
//堆排序
void HeapSort(int* a, int n)
{
//建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
// 交換數(shù)據(jù)后調(diào)整堆頂?shù)臄?shù)據(jù)
while (n)
{
Swap(&a[0], &a[n - 1]);
n--;
AdjustDown(a, n, 0);
}
}
堆排序的特性總結(jié)：
- 堆排序使用堆來(lái)選數(shù)，效率就高了很多。
- 時(shí)間復(fù)雜度：O(N * logN)，時(shí)間復(fù)雜度的消耗主要是在交換數(shù)據(jù)后堆頂要重新找到次大/次小的值；因?yàn)樵诮粨Q數(shù)據(jù)后，除了最后一個(gè)元素和堆頂?shù)脑兀渌匾呀?jīng)是堆，所以堆頂要找出次大/次小的元素，時(shí)間復(fù)雜度是O(logN)，而一共有 N 個(gè)元素，所以總體的時(shí)間復(fù)雜度是 O(N*logN)；
- 空間復(fù)雜度：O(1)
- 穩(wěn)定性：不穩(wěn)定
5. 冒泡排序
冒泡排序的思想是兩兩之間進(jìn)行比較，將較大的元素放到后面去，直到遍歷完數(shù)組，最大的元素就被放到最后面了；再進(jìn)行第二趟比較，將次大的元素放到倒數(shù)第二個(gè)位置，假設(shè)有 n 個(gè)元素，那就一共要比較 n 趟，而每一趟里面又要對(duì)這 n 個(gè)元素進(jìn)行兩兩比較，所以冒泡排序的時(shí)間復(fù)雜度是O(N^2)；
冒泡排序的動(dòng)圖如下：
參考代碼如下：
//冒泡排序
void BubbleSort(int* a, int n)
{
// 每一趟
for (int i = 0; i < n; i++)
{
// 每一趟的兩兩比較
// flag 標(biāo)記，如果這一趟沒(méi)有進(jìn)行交換，說(shuō)明數(shù)組已經(jīng)是有序的，提前跳出循環(huán)
int flag = 1;
for (int j = 1; j < n - i; j++)
{
if (a[j - 1] > a[j])
{
Swap(&a[j],&a[j - 1]);
flag = 0;
}
}
if (flag)
break;
}
}
這里有一個(gè)小小的優(yōu)化，是針對(duì)已經(jīng)有序的數(shù)組，用 flag 標(biāo)記為1，如果在這一趟中沒(méi)有進(jìn)行交換，說(shuō)明數(shù)組已經(jīng)有序，不用進(jìn)行交換，也就沒(méi)有比較下去的必要，所以直接提前跳出循環(huán)；
冒泡排序的特性總結(jié)：
- 冒泡排序是一種非常容易理解的排序，適合初學(xué)者理解，有教學(xué)意義；
- 時(shí)間復(fù)雜度：O(N^2)
- 空間復(fù)雜度：O(1)
- 穩(wěn)定性：穩(wěn)定
6. 快速排序
6.1 遞歸實(shí)現(xiàn)快速排序
快速排序的基本思想為：任取待排序元素序列中的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過(guò)程，直到所有元素都排列在相應(yīng)位置上為止。
通俗易懂地講，就是在數(shù)組中選取一個(gè)比較居中的值 key ，將比 key 小的元素放到 key 的左邊，比 key 大的元素放到 key 的右邊；而又在 key 左邊的數(shù)組區(qū)間選取這段區(qū)間新的居中值（key） ，重復(fù)上面的操作，然后又在key 的右邊重復(fù)操作，最終 key 的左右兩邊都有序了，這個(gè)數(shù)組自然就有序了；當(dāng)然 key 的選值是有講究的，下面我?guī)Т蠹抑鹨环治觯?/p>
首先，我們先想辦法選出每次 key 的值，并對(duì)選出的 key 的值進(jìn)行分割，這里一共有三個(gè)思路供大家參考：
思路一、hoare 版本
我們先看一下 hoare 版本的動(dòng)圖思路：
很明顯，思路就是每次定義 key 為最左邊的元素，然后定義兩個(gè)下標(biāo) L 和 R ，L 找比 key 大的元素， R 找比 key 小的元素，找到后交換下標(biāo)為 L 和 R 的元素；那么通過(guò)這個(gè)思路，我們可以得出以下代碼：
// 快排排單趟 --- hoare法
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;
}
那么大家肯定有一個(gè)疑問(wèn)，怎么能保證最后一次交換的正確性呢？
首先我們是定義 key 為最左邊的元素，其實(shí)也可以定義成最右邊的元素，這要看大家的選擇；我們定義 key 為最左邊的元素，那么我們肯定是希望最后一次與 key 交換是比 key 小的元素，因?yàn)楸?key 小的元素要放到左邊；那么怎么保證 L 和 R相遇的位置一定比 key 小呢？
這個(gè)就與 L 和 R 誰(shuí)先走有關(guān)系了，假設(shè)我們先讓 L 先走，例如以上面動(dòng)圖的數(shù)組{6，1，2，7，9，3，4，5，10，8 }，如下圖，先讓 L 先走：
從圖中可以看出，最后 L 和 R 相遇的位置是 9，不是我們想要的比 key 小的值；而第一張動(dòng)圖中是 R 先走，R 先走最后的結(jié)果是滿足我們的要求的；出現(xiàn)這種情況的原因是什么呢？
原因很簡(jiǎn)單，L 本質(zhì)上是要找比 key 大的值，而 R 是要找比 key 小的值，如果是 L 先走，R 后走，等他們找到對(duì)應(yīng)的值交換后，L 又開(kāi)始新的一輪尋找，找比 key 大的值，而經(jīng)過(guò)上一輪的交換，L 當(dāng)前停留的元素是比 key 大的值，如果 L 在相遇 R 之前沒(méi)有遇到比 key 大的值，那么 L 最終停留的位置一定是 R 所在的位置，又因?yàn)樗鼈円呀?jīng)相遇了，所以 R 也動(dòng)不了了，所以最終與 key 交換的值是比 key 大的值，不符合我們的期望；
相反，如果讓 R 先走，L 后走，在經(jīng)過(guò)一輪的交換后，L 停留的位置是比 key 小的值，R 停留的位置是比 key 大的值，新的一輪也是 R 先走，如果在相遇 L 之前沒(méi)有遇到比 key 小的值，那么 R 和 L 的相遇點(diǎn)一定是比 key 小的值；即使 R 在 相遇 L 之前遇到比 key 小的值，隨著 L 的移動(dòng)，L 一定會(huì)相遇 R ，而他們的相遇點(diǎn)也一定是比 key 小的值，所以相遇點(diǎn)和 key 交換符合我們的期望；
以上就是 hoare 版本 的思路，下面我們介紹另外一種思路；
思路二、挖坑法
老規(guī)矩，我們先看動(dòng)圖的思路：
思路很簡(jiǎn)單，就是將最左邊的元素看作是 key，而將 key 這個(gè)位置挖空，然后定義 L 和 R 兩個(gè)下標(biāo)，L 找比 key 大的元素，R 找比 key 小的元素，因?yàn)槲覀兿韧诳盏氖亲钭筮呍?，而我們期望左邊放的都是?key 小的元素，所以我們也是先讓 R 先走，找到比 key 小的元素后放入坑中，自己形成新的坑，然后 L 走，找到比 key 大的元素后放入坑中，自己又形成新的坑，重復(fù)這個(gè)步驟，直到 L 和 R 相遇，相遇位置就是坑，將 key 放回坑中即可；參考代碼如下：
// 快排排單趟 --- 挖坑法
int PartSort2(int* a, int left, int right)
{
int key = a[left];
int hole = left;
while (left < right)
{
// 右邊找比 key 小的
while (left < right && a[right] >= key)
{
right--;
}
a[hole] = a[right];
hole = right;
// 左邊找比 key 大的
while (left < right && a[left] <= key)
{
left++;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
return hole;
}
思路三、前后指針?lè)?/h5>
還有一個(gè)思路叫做前后指針?lè)?，我們先看?dòng)圖思路：
從圖中可以看出，前后指針?lè)ǖ乃悸芬埠芎美斫?，定義兩個(gè)指針 prev 和 cur，同樣也是將最左邊的元素看作 key，cur 找比 key 小的元素，與 prev 的后一個(gè)位置交換，這樣 key + 1到 prev 的元素都是比 key 小的元素，prev + 1到 cur 都是比 key 大的元素；直到 cur 為空，prev 的位置肯定是比key 小的元素，最后 key 與 prev 的位置交換即可完成；
參考代碼如下：
// 快排排單趟 --- 前后指針?lè)? int PartSort3(int* a, int left, int right)
{
int keyi = left, cur = left + 1, prev = left;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[prev], &a[keyi]);
keyi = prev;
return keyi;
}
以上就是我們對(duì) key 的分割的三個(gè)思路，那么我們應(yīng)該如何實(shí)現(xiàn)快速排序呢？
由于分割的操作有點(diǎn)像我們前面學(xué)的二叉樹(shù)中的前序遍歷，key 就像根節(jié)點(diǎn)一樣，所以我們可以用遞歸的思想實(shí)現(xiàn)；
// 快排 --- 遞歸實(shí)現(xiàn)
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int keyi = PartSort3(a, left, right - 1);
QuickSort(a, left, keyi);
QuickSort(a, keyi + 1, right);
}
從代碼可以看出，我們以前后指針?lè)槔?，先取?key 的下標(biāo) keyi，再對(duì)其左區(qū)間和右區(qū)間進(jìn)行選 key 的分割，即對(duì)其進(jìn)行遞歸，最后當(dāng) left >= right 時(shí)停止遞歸。
這樣我們的快速排序就實(shí)現(xiàn)了，但是對(duì)于這個(gè)快速排序還有一些缺陷：試想，我們的 key 每次都是按照最左邊的值選取的，如果每次最左邊的值都是這個(gè)數(shù)組中比較小的元素的時(shí)候，就會(huì)進(jìn)行不必要的遞歸，效率也就慢了下來(lái)，所以針對(duì)這個(gè)問(wèn)題，我們有了三數(shù)取中選key這個(gè)思路，這個(gè)思路的參考代碼如下：
//快排優(yōu)化：三數(shù)取中
int GetMidIndex(int* a, int left, int right)
{
int mid = (left + right) / 2;
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
if (a[left] < a[right])
{
return right;
}
else
{
return left;
}
}
// a[left] > a[mid]
else
{
if (a[mid] > a[right])
{
return mid;
}
if (a[left] > a[right])
{
return right;
}
else
{
return left;
}
}
}
我們對(duì)下標(biāo) left 和 right 取中下標(biāo) mid，再兩兩比較這三個(gè)元素，返回處于中間大小的元素的下標(biāo)，這樣就大大增加了取 key 的隨機(jī)性；
那么我們應(yīng)該如何使用這個(gè)函數(shù)呢？
很簡(jiǎn)單，假設(shè)我們以前后指針?lè)槔?，只要在前后指針?lè)ê瘮?shù)內(nèi)的開(kāi)頭加入這個(gè)函數(shù)即可；將下標(biāo) left 和 right 傳入 GetMidIndex 函數(shù)，取到中間數(shù)的元素的下標(biāo) midi，再將下標(biāo)為 left 和 midi 的元素交換即可；
// 快排排單趟 --- 前后指針?lè)? int PartSort3(int* a, int left, int right)
{
int midi = GetMidIndex(a, left, right);
Swap(&a[left], &a[midi]);
int keyi = left, cur = left + 1, prev = left;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[prev], &a[keyi]);
keyi = prev;
return keyi;
}
以上這種遞歸實(shí)現(xiàn)的快速排序就相對(duì)比較完善了，但是對(duì)于一些特殊情況還沒(méi)有得到相應(yīng)的解決，如處理含有大量相同元素的時(shí)候，三數(shù)取中也很有可能會(huì)取到相同的元素，也會(huì)重復(fù)進(jìn)行不必要的遞歸，大大降低了效率，這種問(wèn)題的解決方案叫做三路劃分，大家有興趣的可以自行去了解。
快速排序的特性總結(jié)：
- 快速排序整體的綜合性能和使用場(chǎng)景都是比較好的，所以才敢叫快速排序
- 時(shí)間復(fù)雜度：O(N*logN)
- 空間復(fù)雜度：O(logN) （遞歸消耗了棧幀的空間）
- 穩(wěn)定性：不穩(wěn)定
6.2 非遞歸實(shí)現(xiàn)快速排序
非遞歸實(shí)現(xiàn)快速排序的基本思路是：用棧模擬實(shí)現(xiàn)遞歸的操作，嚴(yán)格來(lái)說(shuō)并不是模擬遞歸的實(shí)現(xiàn)，只是用棧實(shí)現(xiàn)比較像遞歸的操作；
例如數(shù)組 {6，1，2，7，9，3，4，5，10，8 }，假設(shè)我們每次以最左邊的為 key，如下圖操作，下圖只執(zhí)行到第二次取 keyi 的值：
如上圖，到第二次取 keyi 的值的時(shí)候，其實(shí)也重復(fù)了上圖剛開(kāi)始的操作，繼續(xù)將其左右區(qū)間入棧，按照棧的特性，后進(jìn)的先出，棧會(huì)先處理后進(jìn)的元素下標(biāo)，我們上面模擬的是后進(jìn) keyi 的左區(qū)間，所以棧會(huì)先處理 keyi 的左區(qū)間，最后再處理 keyi 的右區(qū)間；
其次用棧模擬實(shí)現(xiàn)我們需要先有一個(gè)棧，根據(jù)前期回顧我們直接用以前實(shí)現(xiàn)過(guò)的棧，詳細(xì)請(qǐng)看鏈接 棧和隊(duì)列。
參考代碼如下：
// 快排 --- 非遞歸
void QuickSortNonR(int* a, int begin, int end)
{
ST st;
STInit(&st);
// 一開(kāi)始先將兩邊的元素入棧
STPushTop(&st, end - 1);
STPushTop(&st, begin);
// 棧不為空就繼續(xù)
while (!STIsEmpty(&st))
{
// 取一次，出一次棧
int left = STTop(&st);
STPopTop(&st);
// 取一次，出一次棧
int right = STTop(&st);
STPopTop(&st);
// 取出 keyi 的值
int keyi = PartSort3(a, left, right);
// 在符合的區(qū)間內(nèi)就繼續(xù)將其左右區(qū)間入棧
if (keyi + 1 < right)
{
STPushTop(&st, right);
STPushTop(&st, keyi + 1);
}
if (left < keyi - 1)
{
STPushTop(&st, keyi - 1);
STPushTop(&st, left);
}
}
STDestroy(&st);
}
7. 歸并排序
7.1 歸并排序的遞歸實(shí)現(xiàn)
基本思想：歸并排序是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱(chēng)為二路歸并。
下面觀察動(dòng)圖的思路：
例如數(shù)組{ 10，6，7，1，3，9，2，4 }，觀察更直觀的動(dòng)圖：
根據(jù)上面的思路，我們首先想到，它的思路有點(diǎn)像二叉樹(shù)中的后序遍歷，先將它的子序列排成有序的，最后再將兩個(gè)相對(duì)有序的子序列進(jìn)行歸并，所以我們這里也可以用遞歸的思路實(shí)現(xiàn)類(lèi)似后序遍歷的操作；
我們首先需要一個(gè)子函數(shù)對(duì)子序列進(jìn)行劃分并排序的函數(shù)：
// 歸并的區(qū)間劃分
void PartOfMergeSort(int* a, int begin, int end, int* tmp)
{
if (begin == end)
return;
// 小區(qū)間優(yōu)化
if (end - begin + 1 < 10)
{
InsertSort(a + begin, end - begin + 1);
return;
}
int mid = (begin + end) / 2;
// 劃分的區(qū)間為：
// [begin,mid] [mid + 1,end]
PartOfMergeSort(a, begin, mid, tmp);
PartOfMergeSort(a, mid + 1, end, tmp);
// 對(duì)每個(gè)區(qū)間進(jìn)行歸并排序
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int pos = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
tmp[pos++] = a[begin1++];
else
tmp[pos++] = a[begin2++];
}
while (begin1 <= end1)
tmp[pos++] = a[begin1++];
while (begin2 <= end2)
tmp[pos++] = a[begin2++];
// 將這段已經(jīng)排序好的空間拷貝回原數(shù)組
memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
上面的函數(shù)中，每次進(jìn)入函數(shù)，都會(huì)取中間的下標(biāo)，對(duì)區(qū)域進(jìn)行劃分，并遞歸它的左右子區(qū)間，到最后停止遞歸的條件是 begin == end，然后返回上一層遞歸對(duì)上一層的子序列進(jìn)行歸并排序，每排序完一段子序列就拷貝回原數(shù)組，然后繼續(xù)返回上一層排序上一層的子序列，直到回到第一層，回到第一層，左右子序列已經(jīng)排序好了，進(jìn)行最后一次歸并排序即可；
其次，我們可以看到，在上面的函數(shù)中我們加了一個(gè)小優(yōu)化，就是當(dāng)區(qū)間的元素小于 10 個(gè)時(shí)，我們選擇直接插入排序，原因是因?yàn)楫?dāng)區(qū)間元素小于 10 個(gè)時(shí)，繼續(xù)遞歸會(huì)消耗更多的空間和效率，這種不必要的遞歸用直接插入排序替換更優(yōu)；
// 歸并 --- 遞歸
void MergeSort(int* a, int n)
{
// 需要一段空間進(jìn)行臨時(shí)拷貝
int* tmp = (int*)malloc(sizeof(int) * n);
PartOfMergeSort(a, 0, n - 1, tmp);
free(tmp);
}
7.2 歸并排序的非遞歸實(shí)現(xiàn)
歸并排序的非遞歸實(shí)現(xiàn)，基本思路是控制 gap 的值，把 2*gap 看作一個(gè)子序列，在這一輪的 gap 的子序列排完序后，gap *= 2，再歸并下一個(gè)子序列，直到 gap 的值大于數(shù)組長(zhǎng)度就結(jié)束；
例如數(shù)組{ 10，6，7，1，3，9，4，2 }，
當(dāng) gap == 1：
當(dāng) gap == 2：
當(dāng) gap == 4：
如上圖，當(dāng) gap == 4 時(shí)，數(shù)組已經(jīng)排序好了，這時(shí)候?qū)?shù)組拷貝回原數(shù)組即可；參考代碼如下：
// 歸并 --- 非遞歸
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
assert(tmp);
int gap = 1;
while (gap < n)
{
int pos = 0;
for (int i = 0; i < n; i += 2 * gap)
{
// 給定兩個(gè)歸并區(qū)間的范圍
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
// 有一個(gè)區(qū)間結(jié)束就結(jié)束
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[pos++] = a[begin1++];
}
else
{
tmp[pos++] = a[begin2++];
}
}
// 判斷兩個(gè)區(qū)間是否都結(jié)束了
while (begin1 <= end1)
{
tmp[pos++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[pos++] = a[begin2++];
}
}
// 更新 gap
gap *= 2;
}
}
這時(shí)候我們不得不面臨一個(gè)問(wèn)題，當(dāng)我們?cè)黾?1 到 2 數(shù)據(jù)的時(shí)候，結(jié)果還會(huì)一樣嗎？我們畫(huà)一下圖就可以看出來(lái)了，當(dāng)數(shù)組為{ 10，6，7，1，3，9，4，2 ，0}時(shí)，即上面的數(shù)組增加了一個(gè) 0 ，作圖如下：
從圖中可以看出，當(dāng) gap == 1 時(shí)，問(wèn)題就已經(jīng)出現(xiàn)了，end1、begin2、end2 都越界了；
有人認(rèn)為是奇數(shù)個(gè)元素就不行，而當(dāng)數(shù)組為{ 10，6，7，1，3，9，4，2 ，0，5}，即在上面的數(shù)組基礎(chǔ)上又增加了一個(gè)元素，此時(shí)是 10 個(gè)元素，作圖如下：
當(dāng)元素為偶數(shù)個(gè)的時(shí)候，依然越界了，此時(shí)我們不得不面臨一個(gè)問(wèn)題，就是在給區(qū)間劃分范圍的時(shí)候邊界的區(qū)間可能會(huì)面臨越界的問(wèn)題，此時(shí)我們需要修正邊界的范圍，這里有兩種修正方案：
方案一：因?yàn)?begin1 == i，而 i 是不可能越界的，所以 begin1 不可能會(huì)越界，而 end1、begin2、end2 都有可能越界，此時(shí)我們可以做出以下修正：
// 修正邊界值(方法一：適用歸并一組拷貝一組)
if (end1 >= n || begin2 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
加在函數(shù)中如下：
// 歸并 --- 非遞歸
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
assert(tmp);
int gap = 1;
while (gap < n)
{
int pos = 0;
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
// 修正邊界值(方法一：適用歸并一組拷貝一組)
if (end1 >= n || begin2 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[pos++] = a[begin1++];
}
else
{
tmp[pos++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[pos++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[pos++] = a[begin2++];
}
// 歸并一組，拷貝一組
memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
gap *= 2;
}
}
注意方案一需要?dú)w并一組，拷貝一組，它的解決方案是當(dāng) begin2 或 end1 越界時(shí)直接跳出循環(huán)，這段區(qū)間就在原數(shù)組中不用動(dòng)了；
方案二：直接加在函數(shù)中如下：
// 歸并 --- 非遞歸
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
assert(tmp);
int gap = 1;
while (gap < n)
{
int pos = 0;
for (int i = 0; i < n; i += 2 * gap)
{
// 給定兩個(gè)歸并區(qū)間的范圍
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
// 修正邊界值(方法二：適用歸并完當(dāng)前 gap 再拷貝)
if (end1 >= n)
{
end1 = n - 1;
// 將第二個(gè)區(qū)間變成不存在的區(qū)間
begin2 = n;
end2 = n - 1;
}
else if (begin2 >= n)
{
// 變成不存在的區(qū)間
begin2 = n;
end2 = n - 1;
}
else if (end2 >= n)
{
end2 = n - 1;
}
// 有一個(gè)區(qū)間結(jié)束就結(jié)束
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[pos++] = a[begin1++];
}
else
{
tmp[pos++] = a[begin2++];
}
}
// 判斷兩個(gè)區(qū)間是否都結(jié)束了
while (begin1 <= end1)
{
tmp[pos++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[pos++] = a[begin2++];
}
}
// 歸并完當(dāng)前 gap 全部拷貝
memcpy(a, tmp, sizeof(int) * n);
gap *= 2;
}
}
方案二的思路是將所有越界的邊界值都進(jìn)行修改，只需要修改成 begin2 > end2 就可以了；這個(gè)修正方案可以直接不用歸并一組，拷貝一組，而是可以將當(dāng)前的 gap 分組歸并完后，一次性拷貝回原數(shù)組；
以上就是歸并排序的思路分析，歸并排序的特性總結(jié)：
- 歸并的缺點(diǎn)在于需要O(N)的空間復(fù)雜度，歸并排序的思考更多的是解決在磁盤(pán)中的外排序問(wèn)題。
- 時(shí)間復(fù)雜度：O(N*logN)
- 空間復(fù)雜度：O(N)
- 穩(wěn)定性：穩(wěn)定
*8. 計(jì)數(shù)排序
計(jì)數(shù)排序是一種非比較排序，是利用另外一個(gè)數(shù)組 hash 記錄需要排序的數(shù)組中的元素出現(xiàn)的次數(shù)，然后遍歷一次 hash 數(shù)組，按順序?qū)⒊霈F(xiàn)的元素依次放到數(shù)組中，放一次就自減一次，直到出現(xiàn)過(guò)的元素出現(xiàn)次數(shù)減到 0 ，這樣就相當(dāng)于排序了；
這種排序算法只需要了解即可，因?yàn)樗木窒扌源螅袃纱笕毕荩?br>缺陷1：依賴數(shù)據(jù)范圍，適用于范圍集中的數(shù)組；
缺陷2：只能用于整形；
所以在這里我不作過(guò)多的分析，有興趣的伙伴可以自行去了解；
參考代碼如下：
// 計(jì)數(shù)排序
void CountSort(int* a, int n)
{
// 找出最大的元素和最小的元素
int max = a[0], min = a[0];
for (int i = 0; i < n; i++)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
// 計(jì)算這個(gè)數(shù)組的最大值和最小值的范圍
// 計(jì)算相對(duì)范圍
int range = max - min + 1;
// 開(kāi)辟空間，長(zhǎng)度就是相對(duì)的范圍
int* hash = (int*)malloc(sizeof(int) * range);
assert(hash);
// 將空間初始化為 0
memset(hash, 0, sizeof(int) * range);
// 統(tǒng)計(jì)某個(gè)元素在相對(duì)位置出現(xiàn)的次數(shù)
for (int i = 0; i < n; i++)
{
hash[a[i] - min]++;
}
// 遍歷相對(duì)范圍，如果相對(duì)位置不為 0，說(shuō)明出現(xiàn)過(guò)，就將這個(gè)元素的相對(duì)值放入元素中覆蓋即可，然后出現(xiàn)的次數(shù)自減
int pos = 0;
for (int i = 0; i < range; i++)
{
while (hash[i] != 0)
{
a[pos++] = i + min;
hash[i]--;
}
}
}
三、各種排序的復(fù)雜度和穩(wěn)定性
首先我們先要理解一個(gè)概念，什么是穩(wěn)定性？
穩(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)定的。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-562769.html
所以經(jīng)過(guò)分析，我們得出各種排序算法的時(shí)間復(fù)雜度和空間復(fù)雜度以及穩(wěn)定性如下表：
以上就是我對(duì)常見(jiàn)的各種排序的思路的分享，如有不正確或可以修改的地方，感謝指出！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-562769.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)---排序】庖丁解牛式剖析常見(jiàn)的排序算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
