7.计数排序(Counting Sort)
计数排序不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序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不是很大并且序列比较集中时,计数排序是一个很有效的排序算法。
8.桶排序(Bucket Sort)
桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。桶排序 (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)。很显然,桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少。但相应的空间消耗就会增大。
,