算法与数据结构-常用排序算法总结2-计数排序

序言

排序算法大体可分为两种：

比较排序：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等 非比较排序：基数排序，计数排序，桶排序等

本文介绍非比较排序算法中的计数排序算法。

计数排序（Counting Sort）

原理：现有待排序数组A，排序后数组B和一个额外的计数数组C。

数组C的下标是数组A的元素取值。

即数组A的元素取值的空间将决定数组C的大小

数组C的第i个元素取值是数组A的元素i的个数。

动态示意图：http://www.cs.usfca.edu/~galles/visualization/CountingSort.html

要点：

计数数组元素累加：保证了赋值时能够准确定位数组A中元素应放的位置！

是一种稳定排序算法

步骤：

（1） 找出待排序数组A中最大和最小元素 计数数组C的元素个数为最大最小元素差值加一（2） 统计数组A中取值为i的元素出现次数，计入数组C的第i个元素 即C[A[i]] = 数组A中元素i出现的次数（3） 数组C计数累加 从第一个元素开始，每一项加前一项（4） 反向填充排序后数组B 将元素i放在第C[i]项，每放一个C[i]减一

时间复杂度分析：最差/最好/平均时间复杂度均为 O(n + k) = O(n)

当待排序数组是n个0~k之间整数时，运行时间是O(n + k) n表示要统计n次k表示要累加k次远快于所有基于比较的其他排序算法

空间复杂度分析：O(n + k) = O(n)

由于计数数组需要根据待排序数组元素取值差确定元素个数，对于元素取值差太大的数组，需要大量的内存

所以计数排序特别适合0到100之间的数字排序，不适合按字母顺序排序人名。在基数排序中可以用来排序数据范围很大的数组，下一篇文章中将介绍

注：计数排序只能对整数进行排序。

典型应用：某地区年龄排序问题。（年龄区间较小）

Code Example1：

/********* 函数说明 ********** //参数： array:待排序数组 n:数组元素个数 k:数组取值最大值 + 1 返回值：成功返回0，失败返回-1 ****************************/ #include <stdio.h> #include <stdlib.h> #include <string.h> int CountingSort(int *array, int n, int k) { int *countArray; //计数数组 int *temp; //暂存数组 /* 数组初始化 */ if ((countArray = (int *)malloc(sizeof(int) * k)) == NULL) return -1; if ((temp = (int *)malloc(sizeof(int) * n)) == NULL) return -1; memset(countArray, 0, k); memset(temp, 0, n); /* 统计数组中元素出现次数 */ int i; for (i = 0; i < n; i++) countArray[array[i]]++; /* 计数累加 */ for (i = 1; i < k; i++) countArray[i] = countArray[i] + countArray[i - 1]; /* 暂存数组赋值：从右往左赋值，保证排序稳定性 */ for (i = n - 1; i >= 0; i--) { temp[countArray[array[i]] - 1] = array[i]; //小于等于array[i]的元素个数有countArray[array[i]]个 countArray[array[i]]--; //自减一，小于等于array[i]的元素少一个 } /* 数组赋值 */ memcpy(array, temp, sizeof(int) * n); free(countArray); free(temp); return 0; } int main() { int a[8] = {2, 0, 2, 1, 4, 6, 7, 4}; int max = a[0]; for (int i = 1; i < 8; i++) { if (a[i] > max) max = a[i]; } //函数调用 CountingSort(a, 8, max + 1); //数组输出 for (int j = 0; j < 8; j++) { printf("%d ", a[j]); } printf("\n"); }

Code Example1：

#include <stdio.h> #include <stdlib.h> // 平均时间复杂度 ---- O(n + k) // 最差时间复杂度 ---- O(n + k) // 最优时间复杂度 ---- O(n + k) // 所需辅助空间 ------ O(n + k) const int k = 100; //基数，排序[0-99]内的整数 int C[k]; //计数数组 void CountingSort(int A[], int n) { /* 统计数组A中取值为i的元素出现次数 */ for (int i = 0; i < n; i++) { C[A[i]]++; //C[A[i]]表示小于等于元素i的元素个数，指明了该元素在排序后数组中的位置 } /* 计数累加：C[i]保存着小于等于i的元素个数 */ for (int i = 1; i < k; i++) { C[i] = C[i] + C[i - 1]; } /* 排序后数组空间申请 */ int *B = (int *)malloc(n * sizeof(int)); /* 从后向前扫描赋值，保证计数排序的稳定性 */ for (int i = n - 1; i >= 0; i--) { B[C[A[i]] - 1] = A[i]; //有C[i]个元素小于等于元素i，将数组A的元素i放到数组B的第C[i]的位置 C[A[i]]--; //--：小于等于元素i的元素个数少了一个，保证排序稳定性 } /* 将临时空间B中的数据拷贝回来 */ for (int i = 0; i < n; i++) { A[i] = B[i]; //此处为地址赋值，数组名作函数形参退化为指针 } free(B); } int main() { /* 给定数组 */ int A[] = { 15, 22, 19, 46, 27, 73, 1, 19, 8 }; //适用场景：每一个元素都在[0,100]内且有重复元素 int n = sizeof(A) / sizeof(int); /* 函数调用 */ CountingSort(A, n); /* 输出排序结果 */ printf("计数排序结果："); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } printf("\n"); return 0; }

Acknowledgements: http://blog.csdn.net/fynjy/article/details/46715289 http://www.cnblogs.com/eniac12/p/5332117.html http://blog.csdn.net/han_xiaoyang/article/details/12163251#t128（推荐）

2017.08.05