计数排序

计数排序其实是桶排序的一种特殊情况。当要排序的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]的值。

@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