1. 算法描述
计数排序(Counting Sort)不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
- 找出待排序的数组中最大和最小的元素,计算出存储数据作为数组下标,存储数据出现频率的数组范围；
- 通过(value - min),计算出数据对应的下标,存入频率数组,出现1次值为1,以后++；
- 反向填充目标数组：便利频率数组,通过index反向计算出原始值(index + min),依次加入目标数组。
2. 过程演示
Counting Sort.gif
计数排序
原始数据
8 2 6 9 4 3 2 6 4 5
min = 2
max = 9
count = max - min + 1 = 8;
// 开始计算
0 0 0 0 0 0 1 0
1 0 0 0 0 0 1 0
1 0 0 0 1 0 1 0
1 0 0 0 1 0 1 1
1 0 1 0 1 0 1 1
1 1 1 0 1 0 1 1
2 1 1 0 1 0 1 1
2 1 1 0 2 0 1 1
2 1 2 0 2 0 1 1
2 1 2 1 2 0 1 1
// 初始化已排序数组
0 0 0 0 0 0 0 0 0 0
// 开始导入
2 2 0 0 0 0 0 0 0 0
2 2 3 0 0 0 0 0 0 0
2 2 3 4 4 0 0 0 0 0
2 2 3 4 4 5 0 0 0 0
2 2 3 4 4 5 6 6 0 0
2 2 3 4 4 5 6 6 8 0
2 2 3 4 4 5 6 6 8 9
3. 代码实现
/*
* 计数排序
*/
- (NSArray *)countingSort:(NSArray *)sortArray {
NSInteger min = [[sortArray valueForKeyPath:@"@min.integerValue"] integerValue];
NSInteger max = [[sortArray valueForKeyPath:@"@max.integerValue"] integerValue];
NSInteger rateCount = max -min + 1;
NSMutableArray *rate = [NSMutableArray arrayWithCapacity:rateCount];
// 注入一个存储 count的数组
for (int i = 0; i < rateCount; i ++) {
[rate addObject:@(0)];
self.count1 ++;
}
// 把 相同的值减去最小值 作为下标 个数作为值 存入数组
for (int i = 0; i < sortArray.count; i ++) {
NSInteger rateNumber = [sortArray[i] integerValue] - min;
rate[rateNumber] = @([rate[rateNumber] integerValue] + 1);
self.count1 ++;
}
NSMutableArray *sorted = [NSMutableArray array];
for (int i = 0; i < rate.count; i ++) {
NSInteger count = [rate[i] integerValue];
for (int j = 0; j < count; j ++) {
NSInteger value = i + min;
[sorted addObject:@(value)];
self.count1 ++;
}
}
return sorted.copy;
}
4. 验证
NSArray *arr = [self pakageNumber:1000];
NSArray *arr1 = [self countingSort:arr];
count1 :3000 // 外层循环
一万条数据所用时间
time:0.009548s;
