vlambda博客
学习文章列表

图解排序 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 的长度;


感想

这种排序不同于其它的「比较」排序,它巧妙地把待排序序列与某个有序序列建立关系,从有序列中通过这种关系再把元素计算出来,就达到了排序的目的。这种对于数据量大,但是数据取值范围比较小的序列非常适用。这种排序思想其实是一种“桶排序”的思想,下一篇会介绍。



推荐阅读:



探索技术之外的生活