基数排序

基数排序

假设有10万个手机号码，希望将这10万个手机号从小到大排序，有什么比较快速地排序方法呢？
快排时间复杂度可以做到O(nlogn)，还有更高效的排序算法吗？桶排序、计数排序能派上用场吗？手机号有11位，范围太大，显然不适合用这两种排序算法。针对这个排序问题，有没有时间复杂度是O(n)的算法呢？
这个问题里有这样的规律：假设要比较两个手机号码a,b的大小，如果在前面几位中，a手机号码已经比b手机号码大了，那后面的几位就不用看了。
借助稳定排序算法，先按照最后一位来排序手机号码，然后，再按照倒数第二位重新排序，以此类推，最后按照第一位重新排序。经过11次排序之后，手机号码就都有序了。

注意，这里按照每位来排序的排序算法要是稳定的，否则这个实现思路就是不正确的。因为如果是非稳定排序算法，那最后一次排序只会考虑最高位的大小顺序，完全不管其他位的大小关系，那么低位的排序就完全没有意义了。
根据每一位来排序，可以用刚讲过的桶排序或者计数排序，它们的时间复杂度可以做到O(n)。如果要排序的数据有K位，那就需要k次桶排序或者计数排序，总的时间复杂度是O(K*n)。当k不大的时候，比如手机号码排序的例子，k最大就是11，所以基数排序的时间复杂度就近似于O(n)。
代码实现如下：

@interface DMRadixSort : NSObject

// 基数排序
- (void)radixSort:(NSMutableArray *)dataArray;

@end

@implementation DMRadixSort

- (void)radixSort:(NSMutableArray *)dataArray
{
    NSLog(@"基数排序前：%@", dataArray);
    for (NSInteger i = 10; i >= 0; i--) {
        [self radixSort:dataArray sortIndex:i];
        NSLog(@"基数排序%ld位后数据：%@", (long)i, dataArray);
    }
    
    NSLog(@"基数排序后：%@", dataArray);
}

- (void)radixSort:(NSMutableArray *)dataArray sortIndex:(NSInteger)index
{
    // 放入0...9 十个桶中
    NSMutableArray *bucketArray = [[NSMutableArray alloc] init];
    for (NSInteger i = 0; i < 10; i++) {
        [bucketArray addObject:[[NSMutableArray alloc] init]];
    }
    
    for (NSString *tmpStr in dataArray) {
        NSString *subStr = [[tmpStr substringFromIndex:index] substringToIndex:1];
        NSInteger num = [subStr integerValue];
        NSMutableArray *tmpArray = [bucketArray objectAtIndex:num];
        [tmpArray addObject:tmpStr];
    }
    
    // 桶内数据放回原数组
    [dataArray removeAllObjects];
    for (NSInteger i = 0; i < 10; i++) {
        NSMutableArray *tmpArray = [bucketArray objectAtIndex:i];
        [dataArray addObjectsFromArray:tmpArray];
    }
}

@end

@interface DMSortDemo : NSObject

@end

@implementation DMSortDemo

- (void)demo 
{   
    // 基数排序
    DMRadixSort *radixSort = [[DMRadixSort alloc] init];
    {
        NSMutableArray *dataArray = [[NSMutableArray alloc] init];
        [dataArray addObject:@"13601005688"];
        [dataArray addObject:@"13691245679"];
        [dataArray addObject:@"53632117988"];
        [dataArray addObject:@"13981442684"];
        [dataArray addObject:@"53976224181"];
        [dataArray addObject:@"13961774368"];
        [dataArray addObject:@"23954017669"];
        [dataArray addObject:@"93901472568"];
        [radixSort radixSort:dataArray];
    }
}

@end