??作者：小樹苗渴望變成參天大樹
?? 作者宣言：認(rèn)真寫好每一篇博客
??作者gitee:link
如 果 你 喜 歡 作 者 的 文 章 ，就 給 作 者 點(diǎn) 點(diǎn) 關(guān) 注 吧！
前言
答應(yīng)大家的計(jì)數(shù)排序今天它來了，這也是一個(gè)非常巧妙的方法，不通過比較元素的大小就可以排序出來，通過用另一個(gè)人數(shù)組的下標(biāo)來表示原數(shù)組里面的元素的值，然后通過此數(shù)出現(xiàn)的個(gè)數(shù)進(jìn)行排序
一、計(jì)數(shù)排序
我們來看圖解：
目前我們要解決的問題就是計(jì)數(shù)數(shù)組的大小怎么確定，既然計(jì)數(shù)數(shù)組的下標(biāo)是原數(shù)組里面的值，那開的數(shù)組的大小最小為原數(shù)組中最大元素大小加一，例如上面實(shí)例，最大值為5，我們就要開6個(gè)大小的空間。
我們來看計(jì)數(shù)排序的代碼：
void CountSort2(int* a, int n)
{
int max = 0;
for (int i = 0; i < n; i++)//找出最大值和最小值
{
if (a[i] >= a[max])
{
max = i;
}
}
int count = a[max] + 1;
int* tmp = (int*)malloc(sizeof(int) * count);//開辟范圍差數(shù)組
memset(tmp, 0, sizeof(int) * count);//將開辟的計(jì)數(shù)數(shù)組賦值為0
for (int i = 0; i < n; i++)//計(jì)數(shù)，
{
tmp[a[i]]++;
}
int j = 0;
for (int i = 0; i < count; i++)//排序
{
while (tmp[i]--)
{
a[j++] = i;
}
}
}
我們來看運(yùn)行結(jié)果：
但是這個(gè)代碼有一個(gè)不好的地方，但數(shù)據(jù)出現(xiàn)最大數(shù)和最小數(shù)都很大很大的時(shí)候，例如：90，93，100，1001
那這個(gè)時(shí)候我們開辟的計(jì)數(shù)數(shù)組就太大的，浪費(fèi)了，所以我們就要想一個(gè)辦法，我們可以開辟一個(gè)范圍大小，下標(biāo)就表示原數(shù)組的元素減最小數(shù)的大小
我們?cè)賮砜锤倪M(jìn)的計(jì)數(shù)排序：
void CountSort1(int* a, int n)
{
int min = 0;
int max = 0;
for (int i = 0; i < n; i++)//找出最大值和最小值
{
if (a[i] <= a[min])
{
min = i;
}
if (a[i] >= a[max])
{
max = i;
}
}
int count = a[max] - a[min] + 1;
int* tmp = (int*)malloc(sizeof(int) * count);//開辟范圍差數(shù)組
memset(tmp, 0, sizeof(int) * count);
for (int i = 0; i < n; i++)//計(jì)數(shù)，
{
tmp[a[i] - min]++;
}
int j = 0;
for (int i = 0; i < count; i++)//排序
{
while (tmp[i]--)
{
a[j++] = i + min;
}
}
}
看運(yùn)行結(jié)果：
但是還是有不好的地方，當(dāng)最大數(shù)和最小數(shù)差距很大，并且中間數(shù)據(jù)很少的時(shí)候，例如1，3，5，1000
這個(gè)時(shí)候計(jì)數(shù)排序就不是很友好，這個(gè)沒有辦法解決，這也是計(jì)數(shù)排序的缺點(diǎn)，所以計(jì)數(shù)排序適合數(shù)比較集中的排序。
計(jì)數(shù)排序的特性總結(jié)：
- 計(jì)數(shù)排序在數(shù)據(jù)范圍集中時(shí)，效率很高，但是適用范圍及場(chǎng)景有限。
- 時(shí)間復(fù)雜度：O(MAX(N,范圍))
- 空間復(fù)雜度：O(范圍)
- 穩(wěn)定性：穩(wěn)定
二、排序算法復(fù)雜度及穩(wěn)定性分析
穩(wěn)定性：假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對(duì)次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。
大家可以看看我之前排序的博客，來看看是否穩(wěn)定。這里我就不在一一分析了。大家記住結(jié)論就行了。文章來源：http://www.zghlxwxcb.cn/news/detail-415880.html
三、總結(jié)
到這篇博客結(jié)束后，我們關(guān)于排序的講解就到此結(jié)束，數(shù)據(jù)結(jié)構(gòu)初階的內(nèi)容就現(xiàn)分享到這里了，博主接下來徽更新關(guān)于c++初階和linux相關(guān)的知識(shí)，倒是希望大家可以來支持一下博主，我們下一個(gè)專欄見
文章來源地址http://www.zghlxwxcb.cn/news/detail-415880.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】-計(jì)數(shù)排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
