图解排序 7/10 - 计数排序
前面所讲的 6 种排序都是基于「比较」的思想,总是在比较两个元素的大小,然后交换位置。今天换个“口味”,来看看计数排序。计数排序的核心思想是把一个无序序列 A 转换成另一个有序序列 B,从 B 中逐个“取出”所有元素,取出的元素即为有序序列「没看明白,不急,后面来张图就搞明白了」。这种算法比快速排序还要快「特定条件下」,它适用于待排序序列中元素的取值范围比较小。比如对某大型公司员工按年龄排序,年龄的取值范围很小,大约在(10-100)之间。
计数排序
对数组 arr = [ 8, 1, 4, 6, 2, 3, 5, 4 ] 进行排序,使用计数排序需要找到与其对应的一个有序序列,可以使用数组的下标与 arr 做一个映射「数组的下标恰好是有序的」。遍历 arr,把 arr 中的元素放到 counArr 中,counArr 的大小是由 arr 中最大元素和最小元素决定的。「 一图胜千言 」
图中有个技巧,为了让 countArr 尽可能地小,countArr 的长度使用了 arr 中的最大值 max - arr 中的最小值 min + 1 (max - min + 1),arr[i] - min 恰好是 countArr 的下标。countArr 中记录了某个值出现的次数,比如 8 出现过 1 次,则在 countArr 中的值为 1;4 出现过 2 次,则在 countArr 中的值为 2。
代码
+ (NSArray *)countingSort:(NSArray *)datas {
// 1.找出数组中最大数和最小数
NSNumber *max = [datas firstObject];
NSNumber *min = [datas firstObject];
for (int i = 0; i < datas.count; i++) {
NSNumber *item = datas[i];
if ([item integerValue] > [max integerValue]) {
max = item;
}
if ([item integerValue] < [min integerValue]) {
min = item;
}
}
// 2.创建一个数组 countArr 来保存 datas 中元素出现的个数
NSInteger sub = [max integerValue] - [min integerValue] + 1;
NSMutableArray *countArr = [NSMutableArray arrayWithCapacity:sub];
for (int i = 0; i < sub; i++) {
[countArr addObject:@(0)];
}
// 3.把 datas 转换成 countArr,使用 datas[i] 与 countArr 的下标对应起来
for (int i = 0; i < datas.count; i++) {
NSNumber *aData = datas[i];
NSInteger index = [aData integerValue] - [min integerValue];
countArr[index] = @([countArr[index] integerValue] + 1);
}
// 4.从countArr中输出结果
NSMutableArray *resultArr = [NSMutableArray arrayWithCapacity:datas.count];
for (int i = 0; i < countArr.count; i++) {
NSInteger count = [countArr[i] integerValue];
while (count > 0) {
[resultArr addObject:@(i + [min integerValue])];
count -= 1;
}
}
return [resultArr copy];
}
代码
稳定性:在元素往 countArr 中记录时按顺序遍历,从 countArr 中取出元素也是按顺序取出,相同元素相对位置不会发生变化,故稳定。
空间复杂度:需要额外申请空间,复杂度为“桶”的个数,故为 O ( k ), k 为“桶”的个数,也就是 countArr 的长度;
时间复杂度:最好最坏都为 O(n+k), k 为“桶”的个数,也就是 countArr 的长度;
感想
这种排序不同于其它的「比较」排序,它巧妙地把待排序序列与某个有序序列建立关系,从有序列中通过这种关系再把元素计算出来,就达到了排序的目的。这种对于数据量大,但是数据取值范围比较小的序列非常适用。这种排序思想其实是一种“桶排序”的思想,下一篇会介绍。
推荐阅读:
探索技术之外的生活