計(jì)數(shù)排序：
今天學(xué)習(xí)了計(jì)數(shù)排序，貌似計(jì)數(shù)排序的復(fù)雜度為o(n)。很強(qiáng)大。他的基本思路為：
1.
我們希望能線性的時(shí)間復(fù)雜度排序，如果一個(gè)一個(gè)比較，顯然是不實(shí)際的，書上也在決策樹模型中論證了，比較排序的情況為nlogn的復(fù)雜度。
2.
既然不能一個(gè)一個(gè)比較，我們想到一個(gè)辦法，就是如果我在排序的時(shí)候就知道他的位置，那不就是掃描一遍，把他放入他應(yīng)該的位置不就可以了嘛。
3.
要知道他的位置，我們只需要知道有多少不大于他不就可以了嗎？
4.
以此為出發(fā)點(diǎn)，我們?cè)趺创_定不大于他的個(gè)數(shù)呢？我們先來個(gè)約定，如果數(shù)組中的元素都比較集中，都在[0, max]范圍內(nèi)。我們開一個(gè)max的空間b數(shù)組，把b數(shù)組下標(biāo)對(duì)應(yīng)的元素和要排序的A數(shù)組下標(biāo)對(duì)應(yīng)起來。這樣不就可以知道不比他大的有多少個(gè)了嗎？我們只要把比他小的位置元素個(gè)數(shù)求和，就是不比他大的。例如：A={3,5,7};我們開一個(gè)大小為8的數(shù)組b，把a(bǔ)[0] = 3 放入b[3]中，使b[3] = 0; 同理 b[5] = 1; b[7] = 2;其他我們都設(shè)置為-1，哈哈我們只需要遍歷一下b數(shù)組，如果他有數(shù)據(jù)，就來出來，鐵定是當(dāng)前最小的。如果要知道比a[2]小的數(shù)字有多少個(gè)，值只需要求出b[0] – b[6]的有數(shù)據(jù)的和就可以了。這個(gè)0(n)的速度不是蓋得。
5.
思路就是這樣咯。但是要注意兩個(gè)數(shù)相同的情況A = {1,2,3,3,4}，這種情況就不可以咯，所以還是有點(diǎn)小技巧的。
6.
處理小技巧：我們不把A的元素大小與B的下標(biāo)一一對(duì)應(yīng)，而是在B數(shù)組對(duì)應(yīng)處記錄該元素大小的個(gè)數(shù)。這不久解決了嗎。哈哈。例如A =
{1,2,3,3,4}我們開大小為5的數(shù)組b;記錄數(shù)組A中元素值為0的個(gè)數(shù)為b[0] = 0, 記錄數(shù)組A中元素個(gè)數(shù)為1的b[1] = 1,同理b[2] = 1, b[3] = 2, b[4] = 1;好了，這樣我們就知道比A[4](4)小的元素個(gè)數(shù)是多少了：count = b[0] + b[1] +
b[2] + b[3] = 4;他就把A[4]的元素放在第4個(gè)位置。
還是截張書上的圖：
再次推薦《算法導(dǎo)論》這本書，在我的上次的隨筆中有下載鏈接。哈哈。真正支持還是需要買一下紙版。呵呵。
7. 不過在編程的時(shí)候還是要注意細(xì)節(jié)的，例如我不能每次都來算一下比他小的個(gè)數(shù)。呵呵，思路就這樣了。奉上源代碼：
#include <stdio.h>
#include <stdlib.h>
//計(jì)數(shù)排序
int CountSort(int* pData, int nLen)
{
int* pCout = NULL; //保存記數(shù)數(shù)據(jù)的指針
pCout = (int*)malloc(sizeof(int) * nLen); //申請(qǐng)空間
//初始化記數(shù)為0
for (int i = 0; i < nLen; ++i)
{
pCout[i] = 0;
}
//記錄排序記數(shù)。在排序的值相應(yīng)記數(shù)加1。
for (int i = 0; i < nLen; ++i)
{
++pCout[pData[i]]; //增
}
//確定不比該位置大的數(shù)據(jù)個(gè)數(shù)。
for (int i = 1; i < nLen; ++i)
{
pCout[i] += pCout[i - 1]; //不比他大的數(shù)據(jù)個(gè)數(shù)為他的個(gè)數(shù)加上前一個(gè)的記數(shù)。
}
int* pSort = NULL; //保存排序結(jié)果的指針
pSort = (int*)malloc(sizeof(int) * nLen); //申請(qǐng)空間
for (int i = 0; i < nLen; ++i)
{
//把數(shù)據(jù)放在指定位置。因?yàn)閜Cout[pData[i]]的值就是不比他大數(shù)據(jù)的個(gè)數(shù)。
//為什么要先減一，因?yàn)閜Cout[pData[i]]保存的是不比他大數(shù)據(jù)的個(gè)數(shù)中包括了
//他自己，我的下標(biāo)是從零開始的!所以要先減一。
--pCout[pData[i]]; //因?yàn)橛邢嗤瑪?shù)據(jù)的可能，所以要把該位置數(shù)據(jù)個(gè)數(shù)減一。
pSort[pCout[pData[i]]] = pData[i];
}
//排序結(jié)束，復(fù)制到原來數(shù)組中。
for (int i = 0; i < nLen; ++i)
{
pData[i] = pSort[i];
}
//最后要注意釋放申請(qǐng)的空間。
free(pCout);
free(pSort);
return 1;
}
int main()
{
int nData[10] = {8,6,3,6,5,8,3,5,1,0};
CountSort(nData, 10);
for (int i = 0; i < 10; ++i)
{
printf("%d ", nData[i]);
}
printf("\n");
system("pause");
return 0;
}