图解排序 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 的长度;
感想
这种排序不同于其它的「比较」排序，它巧妙地把待排序序列与某个有序序列建立关系，从有序列中通过这种关系再把元素计算出来，就达到了排序的目的。这种对于数据量大，但是数据取值范围比较小的序列非常适用。这种排序思想其实是一种“桶排序”的思想，下一篇会介绍。
推荐阅读：
探索技术之外的生活