桶排序（Bucket Sort）

1. 算法描述

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

• 设置固定空桶数
• 将数据放到对应的空桶中
• 将每个不为空的桶进行排序
• 拼接不为空的桶中的数据，得到结果

2. 过程演示

Bucket Sort.png

桶排序

原始数据

34 54  12  78 3  45  9  

bucketCount = 2;

range =  78 / 2 + 1 = 40;

[34]

[34]  [54]

[12 34]  [54]

[12 34]  [54 78]

[3 12 34]  [54 78]

[3 12 34]  [45 54 78]

[3 9 12 34]  [45 54 78]


[3 9 12 34 45 54 78]

3. 代码实现

/*
 * 桶排序
 */

- (NSArray *)bucketSort:(NSArray *)sortArray
            bucketCount:(NSInteger)bucketCount {
    
    if (sortArray.count == 1) {
        return sortArray;
    }
    
    NSInteger max = [[sortArray valueForKeyPath:@"@max.integerValue"] integerValue];
    
    if (bucketCount == 0) {
        bucketCount = 1;  // 默认1个桶
    }
    NSInteger range = max / bucketCount + 1;       //计算基数最大数的倍数 补齐
    NSMutableArray *buckets = [NSMutableArray array];
    
    for (int i = 0; i < bucketCount; i ++) {
        [buckets addObject:@[].mutableCopy];
        self.count1 ++;
    }
    
    for (int i = 0; i < sortArray.count; i ++) {
        NSInteger index = [sortArray[i] integerValue] /range;
        NSMutableArray *bucket = buckets[index];
        [bucket addObject:sortArray[i]];
        NSArray *sort = [self insertSort:bucket.copy];  // 插入排序
        [bucket removeAllObjects];
        [bucket addObjectsFromArray:sort];
        self.count1 ++;
    }
    
    NSMutableArray *sortArr = [NSMutableArray array];
    for (NSMutableArray *bucket in buckets) {
        if (bucket.count > 0) {
            [sortArr addObjectsFromArray:bucket];
        }
        self.count1 ++;
    }
    
    return sortArr.copy;
}

4. 验证

 NSArray *arr = [self pakageNumber:1000];    
 NSArray *arr1 =  [self bucketSort:arr];
count1  :1020                        // 外层循环 (不计算内部排序)

一万条数据所用时间
time:1.959485s;