CodeBeauty
春暖花开
posts - 6,comments - 3,trackbacks - 0

经典排序算法-计数排序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;
}

改代码已经成功运行过,欢迎大家进一步完善。

posted on 2012-05-09 10:19 代码之美 阅读(384) 评论(0)  编辑 收藏 引用 所属分类: 经典排序算法(C/C++实现)

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理