时空权衡:计数排序

2016年01月05日 原创
关键词: C++ 数据结构 算法
摘要 计数排序是一种非比较的排序算法,速度快于其他排序算法。

计数排序是一种以空间换时间的排序算法,在排序中会申请额外的空间,但会减少时间的花销。计数排序可以很好的适用于待排序数据的范围一定的情况下,在待排序数据的范围很大或者无限大时,计数排序或许就无法完成工作。

所谓计数排序,就是遍历待排序数组,然后把待排序的每个数据的出现次数统计出来,根据数据的大小保存在一个临时数组中,最后根据临时数组计算出排好序的数组。

以下是该算法的伪代码:

算法  CountingSort(A[0..n-1],l,u)

  //用分布计数法,对来自于有限范围整数的一个数组进行排序

  //输入:数组A[0..n-1],数组中的整数位于l和u之间(l≤u)

  //输出:A中元素构成的非降序数组S[0..n-1]

  for j←0 to u-l do D[j]←0     //初始化频率数组(临时数组)

  for i←0 to n1 do D[A[i]-l]←D[A[i]-l]+1   //计算频率值(统计该数据的出现次数)

  for j←1 to u-l do D[j]←D[j-1]+D[j]  //计算分布值(如果频率数组是1,2,2,1,2的话,分布数组就是1,3,5,6,8)

  for i←n-1 downto 0 do

    j←A[i]-l

   S[D[j]-1]←A[i]

   D[j]←D[j]-1

  return S

假设数组值的范围是固定的,这显然是一个线性效率的算法,因为它仅仅对输入数组A从头到尾连续处理两遍。它的时间效率类型比我们遇到过的其他高效的排序算法--合并排序,快速排序和堆排序还要好。然而,要重点记忆的是,除了空间换时间之外,分布计数排序的这种高效率是因为利用了输入列表独特的自然属性。

下面是计数排序的C++程序:

#include<iostream>
using namespace std;
/*
    输入:
    arr  待排序数组
    left 最小值
    right 最大值
    n 数组长度
    输出:
    排好序的数组
*/
int* CountingSort(int* arr, int left, int right, int n) {
    int* temp = new int[right - left+1];
    memset(temp, 0, sizeof(int)*(right-left+1));
    for (int i = 0; i < n; i++) {
        temp[arr[i] - left]++;
    }
    for (int i = 1; i < right - left + 1; i++) {
        temp[i] = temp[i - 1] + temp[i];
    }
    int* result = new int[n];
    memset(result, 0, sizeof(int)*n);
    for (int i = 0; i < n; i++) {
        result[--temp[arr[i] - left]] = arr[i];

    }
    return result;
}
int main() {
    int data[] = {1,4,6,9,23,45,23,34,1,2,23,21,12,23,32};
    
    int* result = CountingSort(data, 1, 45, sizeof(data) / sizeof(int));
    for (int i = 0; i < sizeof(data) / sizeof(int); i++) {
        cout << result[i] << " ";
    }
    cout << endl;
    return 0;
}

运行结果: