桶排序

桶排序(Bucket Sort)

桶排序核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据在单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

代码实现如下（需要用到上一节中的快速排序，就不贴代码了）：

@interface DMBucketSort : NSObject

// 桶排序
- (void)bucketSort;

@end

@interface DMBucket : NSObject

@property (nonatomic, assign) NSInteger mStartIndex;

@property (nonatomic, assign) NSInteger mEndIndex;

@property (nonatomic, strong) NSMutableArray *mDataArray;

- (BOOL)inRange:(NSNumber *)valueNum;

@end

@implementation DMBucket

- (NSMutableArray *)mDataArray
{
    if (_mDataArray == nil) {
        _mDataArray = [[NSMutableArray alloc] init];
    }
    return _mDataArray;
}

// 判断valueNum 是否在桶区间中
- (BOOL)inRange:(NSNumber *)valueNum
{
    BOOL bFlag = NO;
    if ([valueNum integerValue] >= self.mStartIndex && [valueNum integerValue] <= self.mEndIndex) {
        bFlag = YES;
    }
    
    return bFlag;
}

@end

@implementation DMBucketSort

// 桶排序 金额在0-50之间的订单进行桶排序
- (void)bucketSort
{
    NSMutableArray *dataArray = [[NSMutableArray alloc] init];
    [dataArray addObject:[NSNumber numberWithInteger:22]];
    [dataArray addObject:[NSNumber numberWithInteger:5]];
    [dataArray addObject:[NSNumber numberWithInteger:11]];
    [dataArray addObject:[NSNumber numberWithInteger:41]];
    [dataArray addObject:[NSNumber numberWithInteger:45]];
    [dataArray addObject:[NSNumber numberWithInteger:26]];
    [dataArray addObject:[NSNumber numberWithInteger:29]];
    [dataArray addObject:[NSNumber numberWithInteger:10]];
    [dataArray addObject:[NSNumber numberWithInteger:7]];
    [dataArray addObject:[NSNumber numberWithInteger:8]];
    [dataArray addObject:[NSNumber numberWithInteger:30]];
    [dataArray addObject:[NSNumber numberWithInteger:27]];
    [dataArray addObject:[NSNumber numberWithInteger:42]];
    [dataArray addObject:[NSNumber numberWithInteger:43]];
    [dataArray addObject:[NSNumber numberWithInteger:40]];
    
    NSLog(@"桶排序前数据: %@", [dataArray componentsJoinedByString:@"  "]);
    
    NSMutableArray *bucketArray = [[NSMutableArray alloc] init];
    // 根据金额在0-50，创建五个桶
    for (NSInteger i = 0; i < 5; i++) {
        DMBucket *bucket = [[DMBucket alloc] init];
        bucket.mStartIndex = i * 10;
        bucket.mEndIndex = i * 10 + 9;
        
        [bucketArray addObject:bucket];
    }
    
    // 将原始数据根据桶区间放入对应的桶中
    for (NSInteger i = 0; i < [dataArray count]; i++) {
        NSNumber *numValue = [dataArray objectAtIndex:i];
        for (DMBucket *bucket in bucketArray) {
            if ([bucket inRange:numValue]) {
                [bucket.mDataArray addObject:numValue];
            }
        }
    }
    
    // 利用快速排序对桶中数据进行排序
    for (DMBucket *bucket in bucketArray) {
        DMQuickSort *quickSort = [[DMQuickSort alloc] init];
        [quickSort quickSort:bucket.mDataArray];
    }
    
    // 将桶中排序好的数据拷贝到数组中
    NSMutableArray *resultArray = [[NSMutableArray alloc] init];
    for (DMBucket *bucket in bucketArray) {
        [resultArray addObjectsFromArray:bucket.mDataArray];
    }
    
    NSLog(@"桶排序后数据: %@", [resultArray componentsJoinedByString:@"  "]);
}

@end

桶排序的时间复杂度分析
如果要排序的数据有n个，把它们均匀地划分到m个桶内，每个桶里就有K=n/m个元素。每个桶内部使用快速排序，时间复杂度为O(K * logK)。m个桶排序的时间复杂度就是O(m * K * logK)，因为K=n/m，所以整个桶排序的时间复杂度就是O(n * log(n/m))。当桶的个数m接近数据个数n时，log(n/m)就是一个非常小的常量，这个时候桶排序的时间复杂度接近O(n)。