經(jīng)典排序算法-計數(shù)排序CountSort
注意與基數(shù)排序區(qū)分,這是兩個不同的排序

計數(shù)排序的過程類似小學(xué)選班干部的過程,如某某人10票,作者9票,那某某人是班長,作者是副班長

大體分兩部分,第一部分是拉選票和投票,第二部分是根據(jù)你的票數(shù)入桶

看下具體的過程,一共需要三個數(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ù)組[i] = 6,票箱數(shù)組[i] = 0,這樣通過迭代變量建立了數(shù)字與其桶號(即票數(shù))的聯(lián)系

待排數(shù)組[ 6 2 4 1 5 9 ] i = 0時,可以從待排數(shù)組中取出6

票箱數(shù)組[ 0 0 0 0 0 0 ] 同時可以從票箱數(shù)組里取出6的票數(shù)0,即桶號

拉選票的過程

首先6出列開始拉選票,6的票箱是0號,6對其它所有數(shù)字說,誰比我小或與我相等,就給我投票,不然揍你

于是,2 4 1 5 分別給6投票,放入0號票箱,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的投票,共計兩票

1得到0票,沒人投他

5得到2,4,1投的三張票

9是最大,得到所有人(自己除外)的投票,共計5票(數(shù)組長度-1票)

投票完畢時的狀態(tài)是這樣

待排數(shù)組[ 6 2 4 1 5 9 ]

票箱數(shù)組[ 4 1 2 0 3 5 ]

入桶的過程

投票過程結(jié)束,每人都擁有自己的票數(shù),桶數(shù)組說,看好你自己的票數(shù),進入與你票數(shù)相等的桶,GO

6共計5票,進入5號桶

2得1票,進入1號桶,有幾票就進幾號桶

4兩票,進2號桶,5三票進3號桶,9有5票,進5號桶

待排數(shù)組[ 6 2 4 1 5 9 ]

票箱數(shù)組[ 4 1 2 0 3 5 ]

-----------------------

入桶前 [ 0 1 2 3 4 5 ] //里邊的數(shù)字表示桶編號

入桶后 [ 1 2 4 5 6 9 ] //1有0票,進的0號桶

排序完畢,順序輸出即可[ 1 2 4 5 6 9]

可以看到,數(shù)字越大票數(shù)越多,9得到除自己外的所有人的票,5票,票數(shù)最多所以9最大,

每個人最多擁有[數(shù)組長度減去自己]張票

1票數(shù)最少,所以1是最小的數(shù),

計數(shù)排序同時兼有桶排的高效和快排的霸道,

/**////////////////////////////////////////////////
/**//*
  一共需要三個數(shù)組,分別是待排數(shù)組nData,票箱數(shù)組(計數(shù)數(shù)組）pCount,和桶數(shù)組(存儲結(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;
  }

//計數(shù)排序核心代碼
int CountSort(int* pData, int nLen)
{
    //從待排序數(shù)組中找到最大值，以確定動態(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實現(xiàn)
    int* pCout = new int[Max]; //C++實現(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ù)個數(shù)。
    for (i = 1; i < Max; ++i)
    {
        pCout[i] += pCout[i - 1];    //不比他大的數(shù)據(jù)個數(shù)為他的個數(shù)加上前一個的記數(shù)。
    }
    
    //int* pSort = NULL;            //保存排序結(jié)果的指針
    //pSort = (int*)malloc(sizeof(int) * nLen);    //申請空間
    int *pSort=new int[Max];
    for (i = 0; i < nLen; ++i)
  {
        //把數(shù)據(jù)放在指定位置。因為pCout[pData[i]]的值就是不比他大數(shù)據(jù)的個數(shù)。
        //為什么要先減一，因為pCout[pData[i]]保存的是不比他大數(shù)據(jù)的個數(shù)中包括了
        //他自己，我的下標(biāo)是從零開始的!所以要先減一。
        --pCout[pData[i]];    //因為有相同數(shù)據(jù)的可能，所以要把該位置數(shù)據(jù)個數(shù)減一。
        pSort[pCout[pData[i]]] = pData[i];     //保存待排數(shù)組元素          
    }
    
    //排序結(jié)束，復(fù)制到原來數(shù)組中。
    for (i = 0; i < nLen; ++i)
  {
        pData[i] = pSort[i];
    }
    
    //最后要注意釋放申請的空間。
    //free(pCout);   //C實現(xiàn)
    //free(pSort);
    delete pSort;  //C++實現(xiàn)
    delete pCout;

    return 1;
}

int main()
{
   // int nData[10] = {8,6,3,6,5,8,3,5,1,0};
    //動態(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)成功運行過，歡迎大家進一步完善。