經典排序算法-計數排序CountSort
注意與基數排序區分,這是兩個不同的排序

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

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

看下具體的過程,一共需要三個數組,分別是待排數組,票箱數組,和桶數組

int *nData= new int[] ; //待排數組,以{ 6, 2, 4, 1, 5, 9} 為例

int *pCount = new int[Max{nData[i]+1}]; //票箱數組   ****特別注意pCount的長度問題Max>=nData.Length

int *pSort = new int[Max{nData[i]+1]; //桶數組

最后再看桶數組,先看待排數組和票箱數組

初始狀態,迭代變量i = 0時,待排數組[i] = 6,票箱數組[i] = 0,這樣通過迭代變量建立了數字與其桶號(即票數)的聯系

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

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

拉選票的過程

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

于是,2 4 1 5 分別給6投票,放入0號票箱,6得四票

待排數組[ 6 2 4 1 5 9 ]

票箱數組[ 4 0 0 0 0 0 ]

接下來2開始拉選票,對其它人說,誰比我小,誰投我票,不然弄你!于是1投了一票,其他人比2大不搭理,心想你可真二

于是2從1那得到一票

待排數組[ 6 2 4 1 5 9 ]

票箱數組[ 4 1 0 0 0 0 ]

再然后是,

4得到2和1的投票,共計兩票

1得到0票,沒人投他

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

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

投票完畢時的狀態是這樣

待排數組[ 6 2 4 1 5 9 ]

票箱數組[ 4 1 2 0 3 5 ]

入桶的過程

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

6共計5票,進入5號桶

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

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

待排數組[ 6 2 4 1 5 9 ]

票箱數組[ 4 1 2 0 3 5 ]

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

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

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

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

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

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

1票數最少,所以1是最小的數,

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

/**////////////////////////////////////////////////
/**//*
  一共需要三個數組,分別是待排數組nData,票箱數組(計數數組）pCount,和桶數組(存儲結果數組)pSort.
*/
/**////////////////////////////////////////////////

#include <iostream>
using namespace std;

//輸出函數Output()
bool Output(int b[],int length)
{
    for (int i=0;i<length;i++)
    {
        cout<<b[i]<<"  ";
       }
    cout<<endl;
    return true;
  }

//計數排序核心代碼
int CountSort(int* pData, int nLen)
{
    //從待排序數組中找到最大值，以確定動態數組的長度，以盡量減少內存空間消耗
    int Max=pData[0];
    for (int i= 1;i<nLen;i++)
    {
        if (Max<pData[i])
        {
            Max=pData[i];
        }
    }
    Max++;   //數組中需要在pCout[Max]中存值，故nLen=max+1
    //int* pCout = NULL;            //保存記數數據的指針
    //pCout = (int*)malloc(sizeof(int) * nLen);    //申請空間-C實現
    int* pCout = new int[Max]; //C++實現
    //初始化記數為0
    for (i = 0; i < Max; ++i)
    {
        pCout[i] = 0;
    }
    
    //記錄排序記數。在排序的值相應記數加1。
    for (i = 0; i < nLen; i++)
    {
        pCout[pData[i]]++;        //增
    }
    
    //確定不比該位置大的數據個數。
    for (i = 1; i < Max; ++i)
    {
        pCout[i] += pCout[i - 1];    //不比他大的數據個數為他的個數加上前一個的記數。
    }
    
    //int* pSort = NULL;            //保存排序結果的指針
    //pSort = (int*)malloc(sizeof(int) * nLen);    //申請空間
    int *pSort=new int[Max];
    for (i = 0; i < nLen; ++i)
  {
        //把數據放在指定位置。因為pCout[pData[i]]的值就是不比他大數據的個數。
        //為什么要先減一，因為pCout[pData[i]]保存的是不比他大數據的個數中包括了
        //他自己，我的下標是從零開始的!所以要先減一。
        --pCout[pData[i]];    //因為有相同數據的可能，所以要把該位置數據個數減一。
        pSort[pCout[pData[i]]] = pData[i];     //保存待排數組元素          
    }
    
    //排序結束，復制到原來數組中。
    for (i = 0; i < nLen; ++i)
  {
        pData[i] = pSort[i];
    }
    
    //最后要注意釋放申請的空間。
    //free(pCout);   //C實現
    //free(pSort);
    delete pSort;  //C++實現
    delete pCout;

    return 1;
}

int main()
{
   // int nData[10] = {8,6,3,6,5,8,3,5,1,0};
    //動態輸入待排序數組
    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;
}

改代碼已經成功運行過，歡迎大家進一步完善。