计数排序（Counting Sort）

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;