一、前言
在上一篇文章中，我們已經(jīng)學(xué)習(xí)了五種排序算法，還沒(méi)看過(guò)的小伙伴可以去看一下：傳送門(mén)
今天要講的是八大排序中剩下的三種，這三種排序算法用的是非常多的，需要好好掌握。
下面介紹的排序算法均以排升序?yàn)槔?/p>
二、快速排序
快排的思想是分治，就是選定一個(gè)基準(zhǔn)值，使這個(gè)值的左邊都小于等于它，右邊都大于等于它，然后遞歸處理左右子區(qū)間。
因此快排的關(guān)鍵就在于如何選定基準(zhǔn)值和如何實(shí)現(xiàn)劃分左右區(qū)間。
關(guān)于前者，我們可以選左端點(diǎn)，也可以選右端點(diǎn)，也可以選中點(diǎn)，還可以隨機(jī)選。我們不妨先以左端點(diǎn)為基準(zhǔn)值，來(lái)繼續(xù)下面的分析。
關(guān)于后者，其實(shí)有很多種方法可以實(shí)現(xiàn)劃分，這里只講幾種比較經(jīng)典的。
1. hoare 版
hoare是快排的發(fā)明者，我們先來(lái)學(xué)習(xí)他的劃分方法。
給幾分鐘認(rèn)真觀察下面的動(dòng)圖。
以排升序?yàn)槔覀円棺筮叾夹∮诘扔?code>key，右邊都大于等于key，就可以利用左右雙指針來(lái)維護(hù)這段區(qū)間，右指針找小，左指針找大，找到后交換，再繼續(xù)找，直至左右指針相遇為止。最后把key與相遇處的值交換即可。
先來(lái)解釋下為什么選左端點(diǎn)為基準(zhǔn)值的時(shí)候，要右指針先走。
先說(shuō)結(jié)論，這樣做是為了保證最后左右指針相遇處的值比key小，從而保證key與相遇位置的值交換后，左邊都小于key，右邊都大于key。同理如果以右端點(diǎn)為基準(zhǔn)值，就要左指針先走。
再來(lái)解釋下為什么會(huì)這樣。左右指針相遇無(wú)非兩種情況，要么左遇右，要么右遇左。
如果左遇右，因?yàn)橛抑羔樝茸?，所以右指針先停。由于右指針是找小，所以右指針停的位置的值?code>key小，所以相遇處的值就比key小。
如果右遇左，也就是說(shuō)右指針還沒(méi)停，因?yàn)橛抑羔樖窍茸叩?，一種情況是左指針根本沒(méi)動(dòng)過(guò)，還停留在左端點(diǎn)；另一種情況是左指針動(dòng)過(guò)，但是上一輪左右指針指向的值交換后，左指針位置的值就比key小了。所以上述兩種情況都能保證key與左右指針相遇處的值交換后，左邊都小于key，右邊都大于key。
來(lái)看看代碼怎么寫(xiě)。
void QuickSort1(int a[], int l, int r)
{
if (l >= r) return;
int keyi = l;//左端為key，右端先走
int i = l, j = r;//保存一下左右指針的初始位置
while (l < r)
{
while (l < r && a[r] >= a[keyi]) r--;//右邊找小
while (l < r && a[l] <= a[keyi]) l++;//左邊找大
swap(&a[l], &a[r]);
}
swap(&a[keyi], &a[l]);
keyi = l;
QuickSort1(a, i, keyi - 1);
QuickSort1(a, keyi + 1, j);
}
第一趟結(jié)束后，因?yàn)?code>key的左邊都小于等于它，右邊都大于等于它，所以key已經(jīng)在最終排好序的位置上了。故只需遞歸[l, keyi - 1]和[keyi + 1, r]即可。
2. 挖坑法
這種方法比較好理解，直接上動(dòng)圖和代碼。
void QuickSort2(int a[], int l, int r)
{
if (l >= r) return;
int key = a[l];
int hole = l;
int i = l, j = r;
while (l < r)
{
while (l < r && a[r] >= key) r--;
a[hole] = a[r];
hole = r;
while (l < r && a[l] <= key) l++;
a[hole] = a[l];
hole = l;
}
a[hole] = key;
QuickSort2(a, i, hole - 1);
QuickSort2(a, hole + 1, j);
}
3. 前后指針?lè)?/h3>
void QuickSort3(int a[], int l, int r)
{
if (l >= r) return;
int keyi = l;
int prev = l, cur = l + 1;
while (cur <= r)
{
if (a[cur] < a[keyi])
swap(&a[++prev], &a[cur]);
cur++;
}
swap(&a[prev], &a[keyi]);
QuickSort3(a, l, prev - 1);
QuickSort3(a, prev + 1, r);
}
以上三種方法效率并無(wú)差異，只是實(shí)現(xiàn)劃分的思想不同，挑一種自己好理解的掌握就行。個(gè)人比較喜歡 hoare 版的快排。
4. 快排的非遞歸實(shí)現(xiàn)
眾所周知，函數(shù)棧幀是建立在?？臻g上的，而?？臻g的大小是有限的，如果遞歸過(guò)深可能會(huì)導(dǎo)致棧溢出。因此算法的非遞歸實(shí)現(xiàn)具有很重要的意義。
我們可以利用數(shù)據(jù)結(jié)構(gòu)中的棧來(lái)模擬遞歸的過(guò)程。
void QuickSortNonR(int a[], int l, int r)
{
ST st;
STInit(&st);
STPush(&st, r);
STPush(&st, l);
while (!STEmpty(&st))
{
l = STTop(&st);
STPop(&st);
r = STTop(&st);
STPop(&st);
//這里是hoare版的劃分思想
int keyi = l;
int i = l, j = r;
while (i < j)
{
while (i < j && a[j] >= a[keyi]) j--;
while (i < j && a[i] <= a[keyi]) i++;
swap(&a[i], &a[j]);
}
swap(&a[keyi], &a[i]);
keyi = i;
//如果區(qū)間長(zhǎng)度==2
//它的兩個(gè)子區(qū)間長(zhǎng)度就分別為1和0，故不用繼續(xù)遞歸
if (r - keyi > 2)//r - (keyi + 1) + 1
{
STPush(&st, r);
STPush(&st, keyi + 1);
}
if (keyi - l > 2)//(keyi - 1) - l + 1
{
STPush(&st, keyi - 1);
STPush(&st, l);
}
}
STDestroy(&st);
}
在 C 語(yǔ)言中，我們需要自己實(shí)現(xiàn)棧這個(gè)數(shù)據(jù)結(jié)構(gòu)，具體可以看我這篇文章：【數(shù)據(jù)結(jié)構(gòu)】棧和隊(duì)列
另外，快排的非遞歸還可以用隊(duì)列實(shí)現(xiàn)，有興趣的也可以自己嘗試。
提示：棧模擬的是dfs，隊(duì)列模擬的是bfs。
5. 時(shí)空復(fù)雜度分析
快排的平均時(shí)間復(fù)雜度是O(NlogN)，數(shù)組有序的情況下會(huì)退化成O(N^2)。
空間復(fù)雜度是O(logN)。
快排是不穩(wěn)定的排序算法。
三、歸并排序
歸并排序就是先遞歸排序左右區(qū)間，再有序合并左右區(qū)間。
有序合并左右區(qū)間需要一個(gè)輔助數(shù)組，遞歸要開(kāi)辟logN層棧幀，故空間復(fù)雜度為O(N)。
歸并排序的時(shí)間復(fù)雜度是O(NlogN)。
歸并排序是穩(wěn)定的排序算法。
來(lái)看看代碼怎么寫(xiě)。
1. 遞歸實(shí)現(xiàn)
void _MergeSort(int a[], int l, int r, int* tmp)
{
if (l >= r) return;
int mid = (l + r) / 2;
_MergeSort(a, l, mid, tmp);
_MergeSort(a, mid + 1, r, tmp);
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r)
{
if (a[i] <= a[j]) tmp[k++] = a[i++];
else tmp[k++] = a[j++];
}
while (i <= mid) tmp[k++] = a[i++];
while (j <= r) tmp[k++] = a[j++];
for (int i = l; i <= r; i++) a[i] = tmp[i];
}
void MergeSort(int a[], int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
}
2. 非遞歸實(shí)現(xiàn)
void MergeSortNonR(int a[], int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
int gap = 1;
while (gap < n)
{
int j = 0;
for (int i = 0; i < n; i += 2 * gap)
{
// 每組的合并數(shù)據(jù)
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[j++] = a[begin1++];
}
else
{
tmp[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
// 歸并一組，拷貝一組
memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
gap *= 2;
}
free(tmp);
}
歸并排序的缺點(diǎn)在于O(N)的空間復(fù)雜度和拷貝數(shù)組的消耗。
因此歸并排序的思想更多的是用于外部排序。
四、計(jì)數(shù)排序
void CountSort(int a[], int n)
{
int min = 0, max = 0;
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;
int* count = (int*)calloc(range, sizeof(int));
for (int i = 0; i < n; i++)
{
int idx = a[i] - min;
count[idx]++;
}
for (int i = 0, j = 0; i < range; i++)
{
while (count[i]--)
{
a[j++] = i + min;
}
}
free(count);
}
時(shí)間復(fù)雜度 O(N + range)
空間復(fù)雜度 O(range)
缺陷：
1.只適合于數(shù)據(jù)范圍較集中的情況：
如果range過(guò)大，時(shí)間復(fù)雜度和空間復(fù)雜度都會(huì)很大，時(shí)空效率都很一般。
2.只能用于數(shù)據(jù)類(lèi)型為整型的情況：
因?yàn)橛?jì)數(shù)排序是用計(jì)數(shù)數(shù)組的下標(biāo)來(lái)相對(duì)映射原數(shù)組每個(gè)元素的值，而數(shù)組下標(biāo)只能是整型。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-584408.html
小結(jié)：
計(jì)數(shù)排序在排序范圍較集中的整型數(shù)據(jù)時(shí)，效率非常好，大幅優(yōu)于其他排序算法。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-584408.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】圖解八大排序（下）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
