經(jīng)典排序算法-計(jì)數(shù)排序CountSort
注意與基數(shù)排序區(qū)分,這是兩個(gè)不同的排序
計(jì)數(shù)排序的過程類似小學(xué)選班干部的過程,如某某人10票,作者9票,那某某人是班長,作者是副班長
大體分兩部分,第一部分是拉選票和投票,第二部分是根據(jù)你的票數(shù)入桶
看下具體的過程,一共需要三個(gè)數(shù)組,分別是待排數(shù)組,票箱數(shù)組,和桶數(shù)組
int *nData= new int[] ; //待排數(shù)組,以{ 6, 2, 4, 1, 5, 9} 為例
int *pCount = new int[Max{nData[i]+1}]; //票箱數(shù)組 ****特別注意pCount的長度問題Max>=nData.Length
int *pSort = new int[Max{nData[i]+1]; //桶數(shù)組
最后再看桶數(shù)組,先看待排數(shù)組和票箱數(shù)組
初始狀態(tài),迭代變量i = 0時(shí),待排數(shù)組[i] = 6,票箱數(shù)組[i] = 0,這樣通過迭代變量建立了數(shù)字與其桶號(hào)(即票數(shù))的聯(lián)系
待排數(shù)組[ 6 2 4 1 5 9 ] i = 0時(shí),可以從待排數(shù)組中取出6
票箱數(shù)組[ 0 0 0 0 0 0 ] 同時(shí)可以從票箱數(shù)組里取出6的票數(shù)0,即桶號(hào)
拉選票的過程
首先6出列開始拉選票,6的票箱是0號(hào),6對其它所有數(shù)字說,誰比我小或與我相等,就給我投票,不然揍你
于是,2 4 1 5 分別給6投票,放入0號(hào)票箱,6得四票
待排數(shù)組[ 6 2 4 1 5 9 ]
票箱數(shù)組[ 4 0 0 0 0 0 ]
接下來2開始拉選票,對其它人說,誰比我小,誰投我票,不然弄你!于是1投了一票,其他人比2大不搭理,心想你可真二
于是2從1那得到一票
待排數(shù)組[ 6 2 4 1 5 9 ]
票箱數(shù)組[ 4 1 0 0 0 0 ]
再然后是,
4得到2和1的投票,共計(jì)兩票
1得到0票,沒人投他
5得到2,4,1投的三張票
9是最大,得到所有人(自己除外)的投票,共計(jì)5票(數(shù)組長度-1票)
投票完畢時(shí)的狀態(tài)是這樣
待排數(shù)組[ 6 2 4 1 5 9 ]
票箱數(shù)組[ 4 1 2 0 3 5 ]
入桶的過程
投票過程結(jié)束,每人都擁有自己的票數(shù),桶數(shù)組說,看好你自己的票數(shù),進(jìn)入與你票數(shù)相等的桶,GO
6共計(jì)5票,進(jìn)入5號(hào)桶
2得1票,進(jìn)入1號(hào)桶,有幾票就進(jìn)幾號(hào)桶
4兩票,進(jìn)2號(hào)桶,5三票進(jìn)3號(hào)桶,9有5票,進(jìn)5號(hào)桶
待排數(shù)組[ 6 2 4 1 5 9 ]
票箱數(shù)組[ 4 1 2 0 3 5 ]
-----------------------
入桶前 [ 0 1 2 3 4 5 ] //里邊的數(shù)字表示桶編號(hào)
入桶后 [ 1 2 4 5 6 9 ] //1有0票,進(jìn)的0號(hào)桶
排序完畢,順序輸出即可[ 1 2 4 5 6 9]
可以看到,數(shù)字越大票數(shù)越多,9得到除自己外的所有人的票,5票,票數(shù)最多所以9最大,
每個(gè)人最多擁有[數(shù)組長度減去自己]張票
1票數(shù)最少,所以1是最小的數(shù),
計(jì)數(shù)排序同時(shí)兼有桶排的高效和快排的霸道,
/**/////////////////////////////////////////////////**//*
一共需要三個(gè)數(shù)組,分別是待排數(shù)組nData,票箱數(shù)組(計(jì)數(shù)數(shù)組）pCount,和桶數(shù)組(存儲(chǔ)結(jié)果數(shù)組)pSort.
*/
/**////////////////////////////////////////////////
#include <iostream>
using namespace std;
//輸出函數(shù)Output()
bool Output(int b[],int length)
{
for (int i=0;i<length;i++)
{
cout<<b[i]<<" ";
}
cout<<endl;
return true;
}
//計(jì)數(shù)排序核心代碼
int CountSort(int* pData, int nLen)
{
//從待排序數(shù)組中找到最大值，以確定動(dòng)態(tài)數(shù)組的長度，以盡量減少內(nèi)存空間消耗
int Max=pData[0];
for (int i= 1;i<nLen;i++)
{
if (Max<pData[i])
{
Max=pData[i];
}
}
Max++; //數(shù)組中需要在pCout[Max]中存值，故nLen=max+1
//int* pCout = NULL; //保存記數(shù)數(shù)據(jù)的指針
//pCout = (int*)malloc(sizeof(int) * nLen); //申請空間-C實(shí)現(xiàn)
int* pCout = new int[Max]; //C++實(shí)現(xiàn)
//初始化記數(shù)為0
for (i = 0; i < Max; ++i)
{
pCout[i] = 0;
}
//記錄排序記數(shù)。在排序的值相應(yīng)記數(shù)加1。
for (i = 0; i < nLen; i++)
{
pCout[pData[i]]++; //增
}
//確定不比該位置大的數(shù)據(jù)個(gè)數(shù)。
for (i = 1; i < Max; ++i)
{
pCout[i] += pCout[i - 1]; //不比他大的數(shù)據(jù)個(gè)數(shù)為他的個(gè)數(shù)加上前一個(gè)的記數(shù)。
}
//int* pSort = NULL; //保存排序結(jié)果的指針
//pSort = (int*)malloc(sizeof(int) * nLen); //申請空間
int *pSort=new int[Max];
for (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]; //保存待排數(shù)組元素
}
//排序結(jié)束，復(fù)制到原來數(shù)組中。
for (i = 0; i < nLen; ++i)
{
pData[i] = pSort[i];
}
//最后要注意釋放申請的空間。
//free(pCout); //C實(shí)現(xiàn)
//free(pSort);
delete pSort; //C++實(shí)現(xiàn)
delete pCout;
return 1;
}
int main()
{
// int nData[10] = {8,6,3,6,5,8,3,5,1,0};
//動(dòng)態(tài)輸入待排序數(shù)組
int size_nData;
cout<<"Enter the numble of nData: size_nData=";
cin>>size_nData;
cout<<endl<<"Enter nData(size_nData values):";
int* nData=new int[size_nData];
for (int i=0;i<size_nData;i++)
{
cin>>nData[i];
}
cout<<endl<<"former:"<<endl;
Output(nData,size_nData);
cout<<endl<<"later:"<<endl;
CountSort(nData, size_nData);
Output(nData,size_nData);
cout<<endl;
delete nData;
return 0;
}改代碼已經(jīng)成功運(yùn)行過，歡迎大家進(jìn)一步完善。