数据结构笔记(十五)排序算法之计数排序

发布于 / 程序猿 / 0 条评论

计数排序(英文:Counting sort)是一个非基于比较且具有稳定的线性时间的排序算法,该算法于1954年由Harold H. Seward提出。

基础知识

计数排序使用一个额外的数组C,其中第i个元素是待排序数组A中值等i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。

由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存

算法过程

通俗地理解,例如有10个年龄不同的人,统计出有8个人的年龄比A小,那A的年龄就排在第9位,用这个方法可以得到其他每个人的位置,也就排好了序。当然,年龄有重复时需要特殊处理(保证稳定性),这就是为什么最后要反向填充目标数组,以及将每个数字的统计减去1的原因。

具体步骤

  • 找出待排序的数组中最大和最小的元素
  • 统计数组中每个值为i的元素出现的次数,存入数组C的第i项
  • 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)
  • 反向填充目标数组:将每个元素i放在新数组Ctmp的第C[i]项,每放一个元素就将C[i]减去1

图文演示

对序列a2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2进行计数排序。

  • 计数数组C初始情况

  • 将序列a中元素存入C数组中并统计数量

  • 计数数组C统计完成情况

  • 将序列a中元素a[i]放入新数组Ctmp相应位置

  • 排序完成,序列a有序

算法实现

  • 非稳定版本
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
using namespace std;
const int maxn = 100000;
const int Max = 30000;
int a[maxn];

const int cnt = 100010; // 计数数组C的长度
int C[cnt];
int Ctmp[maxn];

void display(int a[], int n)
{
    for (int i = 0; i < n; ++i)
    {
        cout << a[i] << "  ";
        if ((i+1) % 10 == 0)
            cout << endl;
    }
}

void counting_sort(int a[], int n)
{
    memset(C, 0, sizeof(C));
    for (int i = 0; i < n; ++i)
        ++C[a[i]];
    for (int i = 1; i < cnt; ++i) // 注意i约束条件
        C[i] += C[i-1];
    for (int i = 0; i < n; ++i) // 正向填充
        Ctmp[--C[a[i]]] = a[i];
    for (int i = 0; i < n; ++i) // 拷贝回原数组
        a[i] = Ctmp[i];
}

void getTime(void f(int [], int), int a[], int n)
{
    clock_t _start, _end;
    _start = clock();
    f(a, n);
    _end = clock();
    cout << (double)(_end - _start) / CLOCKS_PER_SEC << endl;
}

int main()
{
    srand((unsigned)time(NULL)); // 设置随机数种子
    for (int i = 0; i < maxn; ++i)
        a[i] = rand() % Max;
    display(a, maxn);
    getTime(stable_counting_sort, a, maxn);
    display(a, maxn);
    return 0;
}
  • 稳定版本
void stable_counting_sort(int a[], int n) 
{
    memset(C, 0, sizeof(C));
    for (int i = 0; i < n; ++i)
        ++C[a[i]];
    for (int i = 1; i < cnt; ++i) // 注意i约束条件
        C[i] += C[i-1];
    for (int i = n; i > 0; --i) // 反向填充
        Ctmp[--C[a[i-1]]] = a[i-1];
    for (int i = 0; i < n; ++i) // 拷贝回原数组
        a[i] = Ctmp[i];
}
  • 实测不同规模序列程序运行时间
对于30000以内的数[稳定版]
当 maxn = 10000     时,时间为 0.001s
当 maxn = 100000    时,时间为 0.002s
当 maxn = 1000000   时,时间为 0.018s
当 maxn = 10000000  时,时间为 0.019s

算法分析

  • 时间复杂度

当输入的元素是n个0到k之间的整数时,它的运行时间是O(n+k),k其实就是整数的范围。

计数排序的优势在于在对一定范围内的整数排序时快于任何比较排序算法,但是这是一种牺牲空间换取时间的做法。而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序(基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序,堆排序)

  • 稳定性

计数排序是稳定排序,但是需要进行特殊处理。

说明

中基础知识和理论分析部分来源于维基百科计数排序。推荐阅读:计数排序,传说时间复杂度为0(n)的排序


The end.
2018-01-03 星期三

转载原创文章请注明,转载自: 太傅 » 数据结构笔记(十五)排序算法之计数排序
Not Comment Found