首页 > 代码库 > 经典算法之计数排序

经典算法之计数排序

本文转自:http://blog.csdn.net/SunnyYoona/article/details/24551123

一 引言

计数排序假设n个输入元素中的每一个都是介于0-k的整数,此处k为某个整数。当k等于O(n)时,计数排序的运行时间为Θ(n)。

二 基本思想
计数排序的基本思想就是对每一个输入元素x,确定小于x的元素个数。因此我们就可以直接把x放到最终输出数组中的相应位置上。
例如:
如果有17个元素小于x,则x就位于第18个输出的位置上。当然有几个元素相同时,这个方法就略微改进一下,因为不能将它们放在同一个位置上。

三 具体实现
技术分享
假定输入数组为A[1..n],他们的值均位于0~k之间,输出排序之后的数组为B[1..n],以及临时存储数组C[0..k]。计数排序的伪代码如下:
技术分享
上图显示出了计数排序的运行过程。
在第1~2行中的for循环初始化操作之后,在第3~4行检查输入的每一个元素。如果输入元素的值为i,即增加C[i]的值。C[i]记录了值为i的元素个数。
于是,在第4行之后C[i]中存放了等于i的元素的个数。在第6~7行中,通过数组C中记录计数和,可以确定对每一个i=0,1,2.....,k,有多少输入元素是小于等于i的。
最后,在第9~11行中的for循环部分,把每一个元素A[j]放在输出数组B中与其相应的最终位置上。如果每一个元素都不相同,则当第一次执行第9行时,对每一个A[j],值C[A[j]]即为A[j]在输出数组上的最终位置上,因为共有C[A[j]]个元素小于等于A[j]。
可是由于各个元素可能不一定是不同的,因此,每当将一个值A[j]放入数组B中时,都要减小C[A[j]]额值。这会使得下一个值等于A[j]的输入元素直接进入输出数组B中A[j]的前一个位置。

四 代码
/*********************************
*   日期:2014-04-26
*   作者:SJF0115
*   题目: 计数排序
**********************************/
#include <iostream>
#include <stdio.h>
using namespace std;


void COUNTINGSORT(int *A,int *B,int len,int k){
    if(A == NULL || k <= 0 || len <= 0){
        return;
    }
    int C[k+1],i;
    //初始化
    for(i = 0;i <= k;i++){
        C[i] = 0;
    }
    //统计值为A[i]的个数,C[i]是等于i的元素个数
    for(i = 0;i < len;i++){
        C[A[i]] ++;
    }
    //确定值A[i]在最终输出数组B中位置,C[i]是小于等于i的元素个数
    for(i = 1;i <= k;i++){
        C[i] += C[i-1];
    }
    //输出到数组B中
    for(i = len-1;i >= 0;i--){
        //index元素A[i]在数组B中的下标
        int index = C[A[i]];
        B[index] = A[i];
        //如果有相同值元素的情况
        C[A[i]] --;
    }
    //B下标从1开始
}

int main(){
    int A[8] = {2,5,3,0,2,3,0,3};
    int B[9];
    COUNTINGSORT(A,B,8,5);
    for(int i = 1;i <= 8;i++){
        printf("%d\n",B[i]);
    }
    return 0;
}



五 时间复杂度分析
 
时间复杂度是多少呢?
第1~2行for循环所花时间为Θ(k)。
第3~4行for循环所花时间为Θ(n)。
第6~7行for循环所花时间为Θ(k)。
第9~11行for循环所花时间为Θ(n)。
这样总的时间就是Θ(k+n)。在实践中,档k = O(n)时,我们常采用计数排序,这时运行时间为Θ(n)。

六 特点

1.  提前必须是已知待排序的关键字为整型且范围已知。

2.  时间复杂度为O(n+k),不是基于比较的排序算法,因此效率非常之高。

3.  稳定性好,这个是计数排序非常重要的特性,可以用在后面介绍的基数排序中。

4.  但需要一些辅助数组,如C[0..k],因此待排序的关键字范围0~k不宜过大。

经典算法之计数排序