桶排序(Bucket Sort)

桶排序核心思想是將要排序的數(shù)據(jù)分到幾個有序的桶里，每個桶里的數(shù)據(jù)在單獨進行排序。桶內排完序之后，再把每個桶里的數(shù)據(jù)按照順序依次取出，組成的序列就是有序的了。

@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 是否在桶區(qū)間中
- (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(@"桶排序前數(shù)據(jù): %@", [dataArray componentsJoinedByString:@"  "]);
    
    NSMutableArray *bucketArray = [[NSMutableArray alloc] init];
    // 根據(jù)金額在0-50，創(chuàng)建五個桶
    for (NSInteger i = 0; i < 5; i++) {
        DMBucket *bucket = [[DMBucket alloc] init];
        bucket.mStartIndex = i * 10;
        bucket.mEndIndex = i * 10 + 9;
        
        [bucketArray addObject:bucket];
    }
    
    // 將原始數(shù)據(jù)根據(jù)桶區(qū)間放入對應的桶中
    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];
            }
        }
    }
    
    // 利用快速排序對桶中數(shù)據(jù)進行排序
    for (DMBucket *bucket in bucketArray) {
        DMQuickSort *quickSort = [[DMQuickSort alloc] init];
        [quickSort quickSort:bucket.mDataArray];
    }
    
    // 將桶中排序好的數(shù)據(jù)拷貝到數(shù)組中
    NSMutableArray *resultArray = [[NSMutableArray alloc] init];
    for (DMBucket *bucket in bucketArray) {
        [resultArray addObjectsFromArray:bucket.mDataArray];
    }
    
    NSLog(@"桶排序后數(shù)據(jù): %@", [resultArray componentsJoinedByString:@"  "]);
}

@end