基数排序（Radix Sort）

1. 算法描述

基数排序(Radix Sort)桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。
具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

• 获取待排序中的最大数max;
• 指数exp起始从1开始,*=10,直到max / exp = 0;
• 遍历每个数据除以exp,对10取余,拿到当前位数的数值,存入0-9相应的桶中;
• 拼接桶中数据,继续进行下一次遍历;

2. 过程演示

Radix Sort.gif

基数排序

原始数据

34 54  12  78 3  45  9  

exp = 1;

0  0  0  0  [34]  0  0  0  0  0

0  0  0  0  [34 54]  0  0  0  0  0

0  0  [12]  0  [34 54]  0  0  0  0  0

0  0  [12]  0  [34 54]  0  0  0  [78]  0

0  0  [12]  [3]  [34 54]  0  0  0  [78]  0

0  0  [12]  [3]  [34 54]  [45]  0  0  [78]  0

0  0  [12]  [3]  [34 54]  [45]  0  0  [78]  [9]

-> 12 3 34 54 45 78 9

 
exp = 10;

0 [12] 0 0 0 0 0 0 0 0 

[3] [12] 0 0 0 0 0 0 0 0 

[3] [12] 0 [34] 0 0 0 0 0 0 

[3] [12] 0 [34] 0 [54] 0 0 0 0 

[3] [12] 0 [34] [45] [54] 0 0 0 0 

[3] [12] 0 [34] [45] [54] 0  [78] 0 0

[3, 9] [12] 0 [34] [45] [54] 0  [78] 0 0

3. 代码实现

/*
 * 基数排序
 */
- (NSArray *)radixSort:(NSArray *)sortArray {
    NSInteger exp = 1;    // 指数。当对数组按各位进行排序时，exp=1；按十位进行排序时，exp=10；...
    NSInteger max = [[sortArray valueForKeyPath:@"@max.integerValue"] integerValue];
    NSArray *output = sortArray;
    for (exp = 1;max / exp > 0 ; exp *= 10) {
        
        NSMutableArray *radix = [NSMutableArray array];
        for (int i = 0; i < 10; i ++) {
            radix[i] = @[].mutableCopy;
        }
        
        for (int i = 0; i < output.count; i ++) {
            NSInteger residue = ([output[i] integerValue] / exp) % 10;
            NSMutableArray *r = radix[residue];
            [r addObject:output[I]];
        }
        
        NSMutableArray *sort = [NSMutableArray array];
        
        for (NSMutableArray *arr in radix) {
            if (arr.count > 0) {
                [sort addObjectsFromArray:arr];
            }
        }
        output = sort.copy;
    }
    
    return output;
}

4. 验证

 NSArray *arr = [self pakageNumber:1000];    
 NSArray *arr1 =  [self radixSort:arr];
count1  :3                      // 外层循环
count2 :3060               // 内层循环
time :0.014959s