桶排序与堆排序（计数排序桶排序）

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序O（n），计数排序要求输入的数据必须是有确定范围的整数。（直方图统计，再按照顺序扔出来）

7.1 算法描述

找出待排序的数组中最大和最小的元素；

统计数组中每个值为i的元素出现的次数，存入数组C的第i项；

对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；

反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

7.2 动图演示

代码实现：

void countingSort(int a[], int len) { if (!a || len <= 0) return; //通过max和min计算出临时数组所需要开辟的空间大小 int max = a[0], min = a[0]; for (int i = 0; i < len; i ) { if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } //分配临时数组，使用calloc将数组都初始化为0 int range = max - min 1; int *b = (int *)calloc(range, sizeof(int)); //使用临时数组记录原始数组中每个数的个数 for (int i = 0; i < len; i ) b[a[i] - min] = 1; //注意：这里在存储上要在原始数组数值上减去min才不会出现越界问题 int j = 0; //根据统计结果，重新对元素进行回收 for (int i = 0; i < range; i ) { while (b[i]--) a[j ] = i min; //注意：要将i的值加上min才能还原到原始数据 } //释放临时数组 free(b); b = NULL; }

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n k)，空间复杂度也是O(n k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

8.1 算法描述

设置一个定量的数组当作空桶；

遍历输入数据，并且把数据一个一个放到对应的桶里去；

对每个不是空的桶进行排序；

从不是空的桶里把排好序的数据拼接起来。

8.2 动图演示

8.3 代码实现

//快速排序，用于每个桶中的排序，具体讲解见之前的文章 void quickSort(int arr[], int left, int right) { if (left >= right) return; int l = left; int r = right; int key = arr[l]; while (l < r) { while (r > l && arr[r] > key) r--; arr[l] = arr[r]; while (l < r && arr[l] < key) l ; arr[r] = arr[l]; } arr[l] = key; quickSort(arr, left, l - 1); quickSort(arr, l 1, right); } //定义一个桶的结构体，也可以使用链表等其他实现方法 struct bucket { int node[10]; int count; //数据个数 }; void bucketSort(int a[], int len) { if (!a || len <= 0) return; int max = a[0], min = a[0]; for (int i = 1; i < len; i ) { if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } int num = (max - min 1) / 10 1; struct bucket *pBucket = (struct bucket*)calloc(num, sizeof(struct bucket)); //将a[i]放进对应的桶中 for (int i = 0; i < len; i ) { int k = (a[i] - min 1) / 10; //计算a[i]所属桶的序号 (pBucket k)->node[(pBucket k)->count] = a[i]; (pBucket k)->count ; } int pos = 0; for (int i = 0; i < num; i ) { quickSort((pBucket i)->node, 0, (pBucket i)->count - 1);//使用快速排序对每个桶中的数进行排序，当然你可以使用任意一种排序 for (int j = 0; j < (pBucket i)->count; j ) { a[pos ] = (pBucket i)->node[j]; } } free(pBucket); }

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决于对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。