计数排序

计数排序

计数排序其实是桶排序的一种特殊情况。当要排序的n个数据，所处的范围并不大的时候，比如最大值是K，就可以把数据划分成K个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。
假设有8个考生，分数在0到5分之间。这8个考生的成绩放在一个数组A[8]中，它们分别是:2，5，3，0，2，3，0，3。
考生的成绩从0到5分，使用大小为6的数组C[6]表示桶，其中下标对应分数。不过，C[6]内存储的并不是考生，而是对应的考生个数。只需要遍历一遍考生分数就可以得到C[6]的值。

从图中可以看出，分数为3的考生有3个，小于3分的考生有4个，所以，成绩为3分的考生在排序之后的有序数组R[8]中，会保存下标4，5，6的位置。

如何快速计算出，每个分数的考生在有序数组中对应的存储位置呢？
对C[6]数组顺序求和，C[6]存储的数据就变成了下面这样子。C[K]里存储小于等于分数K的考生个数。

从后到前依次扫描数组A。比如当扫描到3时，从数组C中取出下标为3的值7，也就是说，到目前为止，包括自己在内，分数小于等于3的考生有7个，也就是说3是数组R中的第7个元素（也就是数组R中下标为6的位置）。当3放入到数组R中后，小于等于3的元素就只剩下了6个了，所以相应的C[3]要减1，变成6。
以此类推，当扫描到第2个分数为3的考生的时候，就会把它放入数组R中第6个元素的位置（也就是下标为5的位置）。当扫描完整个数组A后，数组R内的数据就是按照分数从小到大有序排列的了。

代码实现如下：

@interface DMCountingSort : NSObject

// 计数排序
- (void)countingSort:(NSMutableArray *)dataArray;;

@end

@implementation DMCountingSort

- (void)countingSort:(NSMutableArray *)dataArray
{
    NSLog(@"计数排序前:%@", [dataArray componentsJoinedByString:@"  "]);
    if ([dataArray count] > 1) {
        // 获取最大值
        NSNumber *num = [dataArray objectAtIndex:0];
        NSInteger maxValue = [num integerValue];
        for (NSInteger i = 1; i < [dataArray count]; i++) {
            NSNumber *curNum = [dataArray objectAtIndex:i];
            if ([curNum integerValue] > maxValue) {
                maxValue = [curNum integerValue];
            }
        }
        
        // 初始化0...maxValue 数组 值为0
        NSMutableArray *tmpArray = [[NSMutableArray alloc] init];
        for (NSInteger j = 0; j <= maxValue; j++) {
            [tmpArray addObject:[NSNumber numberWithInteger:0]];
        }
        
        // 计算原始数据中每个数出现的次数，存储到对应的下标中
        for (NSNumber *curNum in dataArray) {
            NSInteger index = [curNum integerValue];
            NSNumber *tmpNum = [tmpArray objectAtIndex:index];
            NSInteger tmpValue = [tmpNum integerValue] + 1;
            [tmpArray replaceObjectAtIndex:index withObject:[NSNumber numberWithInteger:tmpValue]];
        }
        NSLog(@"原始数据出现次数：%@", [tmpArray componentsJoinedByString:@"  "]);
        
        // 计数值累加
        for (NSInteger i = 1; i < [tmpArray count]; i++) {
            NSNumber *tmpNum = [tmpArray objectAtIndex:i];
            NSNumber *oneNum = [tmpArray objectAtIndex:i - 1];
            NSInteger tmpValue = [tmpNum integerValue] + [oneNum integerValue];
            [tmpArray replaceObjectAtIndex:i withObject:[NSNumber numberWithInteger:tmpValue]];
        }
        NSLog(@"原始数据出现次数累加之后：%@", [tmpArray componentsJoinedByString:@"  "]);
        
        // 初始化 结果数组值为null
        NSMutableArray *resultArray = [[NSMutableArray alloc] init];
        for (NSInteger j = 0; j < [dataArray count]; j++) {
            [resultArray addObject:@"*"];
        }
        // 倒序原数据数组
        for (NSInteger i = [dataArray count] - 1; i >= 0; i--) {
            NSNumber *curNum = [dataArray objectAtIndex:i];
            NSInteger index = [curNum integerValue];
            
            NSNumber *tmpNum = [tmpArray objectAtIndex:index];
            NSInteger finalIndex = [tmpNum integerValue];
            
            // 将当前数据 curNum 放入对应的下标位置
            [resultArray replaceObjectAtIndex:finalIndex - 1 withObject:curNum];
            
            // 修改 累加值
            [tmpArray replaceObjectAtIndex:index withObject:[NSNumber numberWithInteger:finalIndex - 1]];
            
            NSLog(@"数据变化：%@  ---- %@", [resultArray componentsJoinedByString:@"  "], [tmpArray componentsJoinedByString:@"  "]);
        }
        
        // 结果拷贝到原数组
        [dataArray removeAllObjects];
        [dataArray addObjectsFromArray:resultArray];
    }
    NSLog(@"计数排序后:%@", [dataArray componentsJoinedByString:@"  "]);
}

@end

@interface DMSortDemo : NSObject

@end

@implementation DMSortDemo

- (void)demo 
{   
    // 计数排序
    DMCountingSort *countingSort = [[DMCountingSort alloc] init];
    {
        NSMutableArray *dataArray = [[NSMutableArray alloc] init];
        [dataArray addObject:[NSNumber numberWithInteger:2]];
        [dataArray addObject:[NSNumber numberWithInteger:5]];
        [dataArray addObject:[NSNumber numberWithInteger:3]];
        [dataArray addObject:[NSNumber numberWithInteger:0]];
        [dataArray addObject:[NSNumber numberWithInteger:2]];
        [dataArray addObject:[NSNumber numberWithInteger:3]];
        [dataArray addObject:[NSNumber numberWithInteger:0]];
        [dataArray addObject:[NSNumber numberWithInteger:3]];
        [countingSort countingSort:dataArray];
    }
}

@end

计数排序只能用在数据范围不大的场景中，如果数据范围K比要排序的数据n大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。