C語(yǔ)言?八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼
前言
排序是數(shù)據(jù)結(jié)構(gòu)中很重要的一章，先介紹幾個(gè)基本概念。
- 排序穩(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ù)的排序。
一、插入排序
時(shí)間復(fù)雜度
最壞：-----------O(N^2)
最好：-----------O(N)
平均：-----------O(N^2)
空間復(fù)雜度
O(1)
穩(wěn)定性：穩(wěn)定
-『 插入排序 』：顧名思義就是把每一個(gè)數(shù)插入到有序數(shù)組中對(duì)應(yīng)的位置。
就相當(dāng)于你玩撲克牌的過(guò)程，抓來(lái)一張牌，就放在對(duì)應(yīng)有序位置
直接插入排序：
當(dāng)插入第i(i>=1)個(gè)元素時(shí)，前面的array[0],array[1],…,array[i-1]已經(jīng)排好序，此時(shí)用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進(jìn)行比較，找到插入位置即將array[i]插入，原來(lái)位置上的元素順序后移
代碼實(shí)現(xiàn)（升序）
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int x = a[end+1];//x為待排序的值
int end = i;//從end開(kāi)始往前和x依次比較
while (end >= 0)
{
if (a[end] > x)//只要當(dāng)前的值大于x繼續(xù)往前找
{
a[end+1] = a[end];
end--;
}
else
{
break;//跳出循環(huán)說(shuō)明a[end] <= x
}
}
a[end + 1] = x;//跳出循環(huán)說(shuō)明a[end] <= x，需要把x插入到end前邊
}
}
那么我們可以看到，越是接近有序的數(shù)組，插入排序的效率越高（有序時(shí)對(duì)于任何一個(gè)數(shù)只需要和前邊的數(shù)比較一次）。
二、希爾排序
時(shí)間復(fù)雜度
O(n^（1.3—2）)
空間復(fù)雜度
O(1)
穩(wěn)定性：穩(wěn)定
『 希爾排序 』(Shell's Sort)是插入排序的一種又稱(chēng)“縮小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。該方法因 D.L.Shell 于 1959 年提出而得名。
該方法實(shí)質(zhì)上是一種『 分組插入 』方法,因?yàn)椴迦肱判驅(qū)τ诮咏行虻臄?shù)組排序效率非常高，那么希爾提出：
算法先將要排序的一組數(shù)按某個(gè)增量d分成若干組，每組中記錄的下標(biāo)相差d.對(duì)每組中全部元素進(jìn)行排序，然后再用一個(gè)較小的增量對(duì)它進(jìn)行分組，在每組中再進(jìn)行排序。當(dāng)增量減到1時(shí)，整個(gè)要排序的數(shù)被分成一組，排序完成。
一般的初次取序列的一半為增量，以后每次減半，直到增量為1。
并且插入排序可以看成分組是1的希爾排序。動(dòng)圖如下：
因?yàn)椴迦肱判蚩梢钥醋鰃ap==1的希爾排序，因此只需要改變插入排序中for循環(huán)的增量控制排序即可。
代碼實(shí)現(xiàn)
void ShellSort(int* a, int n)
{
//按gap分組進(jìn)行預(yù)排序
int gap = n;
while (gap>1)
{
//gap = gap / 2;
gap = gap / 3 + 1;//這里分組選每次折半或者/3都可以
for (int j = 0; j < gap; j++)//gap個(gè)組
for (int i = j; i < n - gap; i+=gap)//每個(gè)組從j開(kāi)始每個(gè)增量gap
{
int end = i;
int x = a[end + gap];
while (end >= 0)
{
if (a[end] > x)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = x;
}
}
}
關(guān)于希爾排序時(shí)間復(fù)雜度證明比較復(fù)雜，取決于gap怎么取，如果按照Knuth提出的/3，來(lái)取是O(n^（1.25）- 1.6*O(n^1.25).
希爾排序的特性總結(jié)：
- 希爾排序是對(duì)直接插入排序的優(yōu)化。
- 當(dāng)gap > 1時(shí)都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時(shí)，數(shù)組已經(jīng)接近有序的了，這樣就會(huì)很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。我們實(shí)現(xiàn)后可以進(jìn)行性能測(cè)試的對(duì)比。
- 希爾排序的時(shí)間復(fù)雜度不好計(jì)算，因?yàn)間ap的取值方法很多，導(dǎo)致很難去計(jì)算，因此在好些樹(shù)中給出的希爾排序的時(shí)間復(fù)雜度都不固定
三、選擇排序
時(shí)間復(fù)雜度
最壞：-----------O(N^2)
最好：-----------O(N^2)
平均：-----------O(N^2)
空間復(fù)雜度
O(1)
穩(wěn)定性：不穩(wěn)定
『 基本思想 』：
每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，存放在序列的起始（末尾）位置，直到全部待排序的數(shù)據(jù)元素排完 。如圖：
代碼實(shí)現(xiàn)
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
int mini = begin;//記錄最小值下標(biāo)
while (begin<end)
{
for (int i = begin; i < end; i++)
{
if (a[i] < a[mini])
{
mini = i;//更新最小值下標(biāo)
}
}
Swap(&a[mini],&a[begin]);//把最小值放到左邊
++begin;//左邊對(duì)應(yīng)起始位置++
}
}
直接選擇排序思考非常好理解，但是效率不是很好。實(shí)際中很少使用。
四、堆排序
時(shí)間復(fù)雜度
最壞：-----------O(N * logN)
最壞：-----------O(N * logN)
平均：-----------O(N*logN)
空間復(fù)雜度
O(1)
堆排序(Heapsort)是指利用堆積樹(shù)（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種。它是通過(guò)堆來(lái)進(jìn)行選擇數(shù)據(jù)。需要注意的是排升序要建大堆，排降序建小堆。
具體可見(jiàn)另一篇文章堆排序和TopK問(wèn)題
動(dòng)圖：
代碼實(shí)現(xiàn)
void Swap(int* px,int* py)
{
int t = (*px);
(*px) = (*py);
(*py)= t ;
}
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]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
for (int i = n - 1; i > 0; i--)
{
Swap(&a[0], &a[i]);
AdjustDown(a, i, 0);
}
}
五、冒泡排序
時(shí)間復(fù)雜度
最壞：-----------O(N^2)
最好：-----------O(N)
平均：-----------O(N^2)
空間復(fù)雜度
O(1)
『 冒泡排序 』是大家最熟悉的也是最容易理解的排序,如下圖：
『 冒泡排序基本思想 』就是每一次將相鄰的數(shù)據(jù)進(jìn)行『 兩兩比較 』，選出最大的依次比較送到右邊，那么最右邊就是最大值，而左邊留下的自然就是小的（排升序）
-『 冒泡排序 』需要兩層循環(huán)
『 內(nèi)層循環(huán) 』表示一次冒泡，也就是兩兩比較先選出最大的放到最右邊，同時(shí)注意每一次冒泡選出最大元素，那么兩兩比較次數(shù)-1（下一次不用比較選好的最右邊）
『 外層循環(huán) 』控制的是冒泡的次數(shù)（假設(shè)數(shù)組N 個(gè)元素）也就是N-1次冒泡選出N-1個(gè)最大的元素
代碼實(shí)現(xiàn)
初版代碼如下：
//初版：
void Swap(int* px, int* py)
{
int t = (*px);
*px = (*py);
(*py) = t;
}
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n-1; i++)//外層循環(huán)
{
for (int j = 0; j < n-1-i; j++)
{
if(a[j]>a[j+1])
Swap(&a[j],& a[j + 1]);//交換
flag = 1;
}
}
}
時(shí)間復(fù)雜度分析：每一次比較次數(shù)是N-1,N-2,N-3***1.因此是N(N-1)/2
但是這種寫(xiě)法還是有缺陷，時(shí)間復(fù)雜度永遠(yuǎn)是O(N^2） ， 對(duì)于一個(gè)已經(jīng)排好序的數(shù)組來(lái)說(shuō)，還是需要N^2的復(fù)雜度，但對(duì)于有序的數(shù)組，每一次冒泡都不會(huì)進(jìn)行交換因?yàn)橛行?，因此如果只要任何一次冒泡中沒(méi)有數(shù)據(jù)交換就證明數(shù)組有序了。時(shí)間復(fù)雜度最好也可以達(dá)到0(N)。
代碼優(yōu)化如下：
//優(yōu)化：
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n-1; i++)
{
int flag = 0;
for (int j = 0; j < n-1-i; j++)
{
if(a[j]>a[j+1])
Swap(&a[j],& a[j + 1]);
flag = 1;
}
if (flag == 0)
break;
}
}
六、快排排序
時(shí)間復(fù)雜度
最壞：-----------O(N^2)
最好：-----------O(logN)
平均：-----------O(logN)
空間復(fù)雜度
O(logN)
『 快速排序 』是Hoare于1962年提出的一種二叉樹(shù)結(jié)構(gòu)的交換排序方法，其『 基本思想 』為：任取待排序元素序列中的某元素作為『 基準(zhǔn)值 』，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過(guò)程，直到所有元素都排列在相應(yīng)位置上為止。如圖：
代碼實(shí)現(xiàn)
遞歸寫(xiě)法：
// 假設(shè)按照升序?qū)數(shù)組中[left, right)區(qū)間中的元素進(jìn)行排序
void QuickSort(int* a, int left, int right) {
if(right >= left )
return;//遞歸截止條件
// 按照基準(zhǔn)值對(duì)a數(shù)組的 [left, right]區(qū)間中的元素進(jìn)行劃分
int keyi= partion(a, left, right);
// 劃分成功后以keyi為邊界形成了左右兩部分 [left, keyi-1] 和 [keyi+1, right]
// 遞歸排[left, keyi-1]
QuickSort(a, left, keyi-1);
// 遞歸排[keyi+1, right]
QuickSort(a, keyi+1, right);
}
遞歸框架寫(xiě)完了接下來(lái)就差partion函數(shù)的實(shí)現(xiàn)也就是快排的靈魂，去每一次找基準(zhǔn)值。那么一共有三種寫(xiě)法如下：
hoare版本
1.首先就是要找基準(zhǔn)值，這里你可以選最左邊或最右邊的值（圖中是6）
2.兩個(gè)指針指向頭（這里選左為基準(zhǔn)值，頭指針指向第二個(gè)）和尾，基準(zhǔn)值選左，則右指針先走，反之左指針先走。
3.左指針找到比基準(zhǔn)值大的停下，右指針找比基準(zhǔn)值小的停下，交換左右指針指向值
4.重復(fù)2.3動(dòng)作，直到左右指針相遇，交換左指針值和基準(zhǔn)值
左值為基準(zhǔn)，右指針先走找比6小的：
左值為基準(zhǔn)，右指針先走找比6小的：
交換：
最終效果：相遇交換左指針和基準(zhǔn)值，保證了6的左邊都比6小，右邊比6大。
并且除此之外，由于我們看到這種算法類(lèi)似于二叉樹(shù)的思想排好中間再排左右子樹(shù)，因此我要保證選取的隨機(jī)值盡量位與中位數(shù)。所以我們采取三數(shù)取中的方法。（選取最左值最右最中間的數(shù)的中位數(shù)）效率是可以提升5%到10%的。
//三數(shù)取中
int GetMidIndex(int* a, int left, int right)
{
//int mid = (left + right) / 2;
//int mid = left + (right - left) / 2;
int mid = left + ((right - left)>>1);
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
else//a[left] > a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
int Partion(int* a, int left,int right)
{
int mini = GetMidIndex(a, left, right);
Swap(&a[mini], &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[left], &a[keyi]);
return left;
}
挖坑法
挖坑法就是對(duì)hoare版本的一種變形，過(guò)程如下：
初始如下：先保存基準(zhǔn)值，基準(zhǔn)值形成一個(gè)坑位！
左為基準(zhǔn)，右指針先走，找到小的送到坑位，那么此刻右指針形成了新的坑位
左指針出動(dòng)，找到大的繼續(xù)送到坑位，左指針形成了新的坑位
指針相遇，把6寫(xiě)入。也保證左邊比6小，右邊比6大。代碼如下：
//挖坑法
int Partion2(int* a, int left, int right)
{
int mini = GetMidIndex(a, left, right);
Swap(&a[mini], &a[left]);
int key = a[left];
int pivot = left;
while (left < right)
{
//右邊先找小
while (left< right && a[right] >= key)
{
--right;
}
a[pivot] = a[right];
pivot = right;
while (left < right && a[left] <= key)
{
++left;
}
a[pivot] = a[left];
pivot = left;
}
a[pivot] = key;
return pivot;
}
前后指針版本
顧名思義，使用兩個(gè)指針，這里選取左為基準(zhǔn)值為例，兩個(gè)指針從左開(kāi)始出發(fā)一個(gè)cur,一個(gè)prev。
要求：
cur指針先走，一旦找到比基準(zhǔn)值小的就停下，++prev,并交換。
cur指針一直到頭為止，最后交換prev指向值和基準(zhǔn)值
1和2都比6小cur走一步停一步，prev++并交換，指向相等。
cur越過(guò)7和9去找小的3，此時(shí)停下，prev++指向7交換。（我們注意到prev和cur不等時(shí)prev永遠(yuǎn)是去找大的，cur是找小的，因此交換就做到把cur指向的小的往前扔，大的往后仍，）
整個(gè)過(guò)程如上，代碼：
//前后指針?lè)?
int Partion3(int* a, int left, int right)
{
int mini = GetMidIndex(a, left, right);
Swap(&a[mini], &a[left]);
int prev = left, cur = left+1;
int keyi = left;
while (cur<=right)
{
if (a[cur] < a[keyi] && ++prev !=cur)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[prev], &a[keyi]);
return prev;
}
小結(jié)
遞歸版本三種方法如上，但是遞歸畢竟有缺陷，就是需要不斷開(kāi)辟棧幀，當(dāng)數(shù)據(jù)量超過(guò)10W以上時(shí)就會(huì)有棧溢出的風(fēng)險(xiǎn)。
并且遞歸類(lèi)似二叉樹(shù)的結(jié)構(gòu)越往下遞歸調(diào)用越多，棧幀翻倍開(kāi)辟，因此我們還可以去優(yōu)化一下，就是當(dāng)遞歸到左右區(qū)間比較小時(shí)，我們?nèi)タ刂剖Ｏ碌呐判蛴脛e的排序來(lái)代替它。
//優(yōu)化：
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
if (right - left + 1 < 10)
{
//小區(qū)間優(yōu)化
InsertSort(a + left , right - left + 1);
}
else
{
int keyi = Partion3(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
}
非遞歸：
非遞歸版本就是改變了快排的框架，用一個(gè)棧和循環(huán)來(lái)代替遞歸實(shí)現(xiàn)。依次將左右下標(biāo)入棧出棧（出棧之前排序）來(lái)模擬遞歸。
void QuickSortNonR(int* a, int left, int right)
{
Stack st;//定義一個(gè)棧
StackInit(&st);//初始化
StackPush(&st, left);//左下標(biāo)入棧
StackPush(&st, right);//右下標(biāo)入棧
while (StackEmpty(&st)!=0)
{
int end = StackTop(&st);//獲取棧頂元素即后入棧的右下標(biāo)
StackPop(&st);//出棧
int begin = StackTop(&st);//獲取棧頂元素即先入棧的左下標(biāo)
StackPop(&st);//出棧
int keyi = Partion3(a, begin, end);
if (keyi + 1 < end)//相當(dāng)于遞歸左半部分
{
StackPush(&st, keyi + 1);
StackPush(&st, right);
}
if (keyi - 1 > begin)//相當(dāng)于遞歸右半部分
{
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}
}
七、歸并排序
時(shí)間復(fù)雜度
最壞：-----------O(NlogN)
最好：-----------O(NlogN)
平均：-----------O(NlogN)
空間復(fù)雜度
O(N)
穩(wěn)定性：穩(wěn)定
基本思想：
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide andConquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱(chēng)為二路歸并。 動(dòng)圖演示：
歸并的思想就是把先假設(shè)數(shù)組分成兩個(gè)有序，對(duì)其進(jìn)行篩選排序，如上圖：
但是問(wèn)題來(lái)了我們?cè)趺幢ＷC數(shù)組是有序的？因此就要求我們從小區(qū)間開(kāi)始對(duì)數(shù)組歸并排序，對(duì)于上圖中的數(shù)據(jù)，先對(duì)開(kāi)始3和3歸并，小的先進(jìn)入到tmp數(shù)組，因此前兩個(gè)就是有序，再對(duì)，5和6歸并，5,6有序后，在歸并3，3，5，6……以此類(lèi)推
代碼實(shí)現(xiàn)
遞歸寫(xiě)法
框架：
void MergeSort(int* a,int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);//開(kāi)辟N個(gè)大小數(shù)組
if (tmp == NULL)
{
exit(-1);
}
_MergeSort(a, 0, n - 1, tmp);//進(jìn)行歸并操作
free(tmp);
tmp = NULL;
}
歸并排序：
運(yùn)用遞歸先不斷縮小偏序區(qū)間，在遞歸層層退出時(shí)一遍退出，一邊對(duì)不斷回大的區(qū)間歸并排序：
void _MergeSort(int* a, int left, int right,int* tmp)
{
if (left >= right)
{
return;//遞歸截止條件left >= right區(qū)間中數(shù)的個(gè)數(shù)<=0個(gè)
}
int mid = left + (right - left) / 2;//取中
_MergeSort(a, left, mid, tmp);//對(duì)左區(qū)間遞歸
_MergeSort(a, mid+1, right, tmp);//對(duì)右區(qū)間遞歸
int begin1 = left, end1 = mid;//左區(qū)間
int begin2 = mid+1, end2 = right;//右區(qū)間
int i = left;
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++];
}
for (size_t i = left; i <= right; i++)
{
a[i] = tmp[i];//把排好序[left,right]的tmp賦值給原數(shù)組
}
}
非遞歸
非遞歸的不同就是需要手動(dòng)控制區(qū)間大小，也就是不斷2倍擴(kuò)大區(qū)間歸并。
但是還需要注意就是當(dāng)下標(biāo)是奇數(shù)，無(wú)法分成整數(shù)個(gè)組的時(shí)候，需要考慮剩余的數(shù)，以及是否越界的問(wèn)題
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
exit(-1);
}
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
//[i][i+gap-1] [i+gap][i+2*gap-1]
int begin1 = i, end1 = i + gap-1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
int index = i;
if (end1 >= n || begin2 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
while (begin1<=end1 && begin2<=end2)
{
if (a[begin1] <= a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
//控制越界問(wèn)題三種情況
if (end1 >= n)
{
end1 = n - 1;
}
if (end1 >= n)
{
end1 = n - 1;
}
if (end1 >= n)
{
end1 = n - 1;
}
for (int j = i; j <= end2; j++)
{
a[j] = tmp[j];
}
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}
八、計(jì)數(shù)排序
時(shí)間復(fù)雜度
最壞：-----------O(MAX(N,范圍))
最好：-----------O(MAX(N,范圍))
平均：-----------O(MAX(N,范圍))
空間復(fù)雜度
O(范圍)
穩(wěn)定性：不穩(wěn)定
思想：計(jì)數(shù)排序又稱(chēng)為鴿巢原理，是對(duì)哈希直接定址法的變形應(yīng)用。 操作步驟：
- 統(tǒng)計(jì)相同元素出現(xiàn)次數(shù)
- 根據(jù)統(tǒng)計(jì)的結(jié)果將序列回收到原來(lái)的序列中
動(dòng)圖如下：
類(lèi)似桶排序的思想，如上圖，先開(kāi)辟數(shù)組統(tǒng)計(jì)數(shù)組中某一個(gè)數(shù)出現(xiàn)的次數(shù)，比如2出現(xiàn)1次，3出現(xiàn)兩次，那么我們直接按順序讀入開(kāi)辟的數(shù)組，在原數(shù)組寫(xiě)1一個(gè)2，兩個(gè)3以此類(lèi)推……
代碼實(shí)現(xiàn)
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];
}
}
int range = max - min + 1;
int* count = (int*)malloc(sizeof(int) * range);
memset(count, 0, sizeof(int)*range);
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
}
int j = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
a[j++] = i + min;
}
}
}
計(jì)數(shù)排序的特性總結(jié)：
計(jì)數(shù)排序在數(shù)據(jù)范圍集中時(shí)，效率很高，但是適用范圍及場(chǎng)景有限。
九、各種排序總結(jié)比較
1. 復(fù)雜度總結(jié)
2. 性質(zhì)分類(lèi)
?以上就是C語(yǔ)言 八大排序算法的過(guò)程圖解及實(shí)現(xiàn)代碼的詳細(xì)內(nèi)容，更多關(guān)于C語(yǔ)言八大排序算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
C語(yǔ)言查找數(shù)組里數(shù)字重復(fù)次數(shù)的方法
這篇文章主要介紹了C語(yǔ)言查找數(shù)組里數(shù)字重復(fù)次數(shù)的方法,涉及C語(yǔ)言針對(duì)數(shù)組的遍歷與判斷技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-07-07
解析設(shè)計(jì)模式中的Prototype原型模式及在C++中的使用
這篇文章主要介紹了設(shè)計(jì)模式中的Prototype原型模式及在C++中的使用,需要的朋友可以參考下2016-03-03
C語(yǔ)言線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)實(shí)例詳解
這篇文章主要介紹了C語(yǔ)言線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-06-06
OpenCV利用霍夫變換實(shí)現(xiàn)交通車(chē)道線(xiàn)檢測(cè)
經(jīng)典霍夫變換用來(lái)檢測(cè)圖像中的直線(xiàn)，后來(lái)霍夫變換經(jīng)過(guò)擴(kuò)展可以進(jìn)行任意形狀物體的識(shí)別，例如圓和橢圓。本文就來(lái)利用霍夫變換實(shí)現(xiàn)交通車(chē)道線(xiàn)檢測(cè)，需要的可以參考一下2022-09-09
C++ 虛函數(shù)的詳解及簡(jiǎn)單實(shí)例
這篇文章主要介紹了C++ 虛函數(shù)的詳解及簡(jiǎn)單實(shí)例的相關(guān)資料,需要的朋友可以參考下2017-06-06![C 語(yǔ)言基礎(chǔ)教程(我的C之旅開(kāi)始了)[九]](http://img.jbzj.com/images/xgimg/bcimg5.png)
C 語(yǔ)言基礎(chǔ)教程(我的C之旅開(kāi)始了)[九]
C 語(yǔ)言基礎(chǔ)教程(我的C之旅開(kāi)始了)[九]...2007-02-02
深入分析C語(yǔ)言中結(jié)構(gòu)體指針的定義與引用詳解
本篇文章是對(duì)C語(yǔ)言中結(jié)構(gòu)體指針的定義與引用進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
位運(yùn)算直接對(duì)內(nèi)存數(shù)據(jù)進(jìn)行操作,不需要轉(zhuǎn)換成十進(jìn)制,因此處理速度非?？?本文主要介紹了C++ 位運(yùn)算的具體實(shí)現(xiàn),具有一定的參考價(jià)值,感興趣的可以了解一下2024-02-02
Linux下實(shí)現(xiàn)C++操作Mysql數(shù)據(jù)庫(kù)
由于工作需要抽出一周的時(shí)間來(lái)研究C/C++訪問(wèn)各種數(shù)據(jù)庫(kù)的方法，并打算封裝一套數(shù)據(jù)庫(kù)操作類(lèi)，現(xiàn)在奉上最簡(jiǎn)單的一部分：在Linux下訪問(wèn)MySQL數(shù)據(jù)庫(kù)。2017-05-05
C++ Primer中&、*符號(hào)的多重定義與int *p和int* p的區(qū)別講解
今天小編就為大家分享一篇關(guān)于C++Primer中&、*符號(hào)的多重定義與int *p和int* p的區(qū)別講解，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2019-04-04