基数排序
基数排序(Radix Sort)是根据关键字中各位的值，通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。
算法思想
-
基于LSD方法的链式基数排序的基本思想
“多关键字排序”的思想实现“单关键字排序”。对数字型或字符型的单关键字，可以看作由多个数位或多个字符构成的多关键字，此时可以采用“分配-收集”的方法进行排序，这一过程称作基数排序法，其中每个数字或字符可能的取值个数称为基数。比如，扑克牌的花色基数为4，面值基数为13。在整理扑克牌时，既可以先按花色整理，也可以先按面值整理。按花色整理时，先按红、黑、方、花的顺序分成4摞（分配），再按此顺序再叠放在一起（收集），然后按面值的顺序分成13摞（分配），再按此顺序叠放在一起（收集），如此进行二次分配和收集即可将扑克牌排列有序。
-
基数排序实现步骤
判断数据在各位的大小，排列数据
根据上一步的结果，判断数据在十分位的大小，排列数据。如果数据在这个位置的余数相同，那么数据之间的顺序根据上一轮的排列顺序确定
依次类推，继续判断数据在百分位、千分位......上面的数据重新排序，直到所有的数据在某一分位上数据都为0
-
基数排序实现步骤实例
假设有欲排数据序列如下所示：
73 22 93 43 55 14 28 65 39 81
首先根据个位数的数值，在遍历数据时将它们各自分配到编号0至9的桶（个位数值与桶号一一对应）中。
分配结果分配结束后。接下来将所有桶中所盛数据按照桶号由小到大（桶中由顶至底）依次重新收集串起来，得到如下仍然无序的数据序列：
81 22 73 93 43 14 55 65 28 39
接着，再进行一次分配，这次根据十位数值来分配（原理同上）
分配结果分配结束后。接下来再将所有桶中所盛的数据（原理同上）依次重新收集串接起来，得到如下的数据序列：
14 22 28 39 43 55 65 73 81 93
观察可以看到，此时原无序数据序列已经排序完毕。如果排序的数据序列有三位数以上的数据，则重复进行以上的动作直至最高位数为止。
代码范例：
#pragma mark --- 基数排序
/**
基数排序
@param array 需要排序的Array
*/
+ (void)radixSort:(NSMutableArray *)array
{
/**
基于LSD方法的链式基数排序的基本思想
“多关键字排序”的思想实现“单关键字排序”。对数字型或字符型的单关键字，可以看作由多个数位或多个字符构成的多关键字，此时可以采用“分配-收集”的方法进行排序，这一过程称作基数排序法，其中每个数字或字符可能的取值个数称为基数。比如，扑克牌的花色基数为4，面值基数为13。在整理扑克牌时，既可以先按花色整理，也可以先按面值整理。按花色整理时，先按红、黑、方、花的顺序分成4摞（分配），再按此顺序再叠放在一起（收集），然后按面值的顺序分成13摞（分配），再按此顺序叠放在一起（收集），如此进行二次分配和收集即可将扑克牌排列有序。
基数排序:
是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。
*/
//创建空桶
NSMutableArray *buckt = [self createBucket];
//待排数组的最大数值
NSNumber *maxnumber = [self listMaxItem:array];
//最大数值的数字位数
NSInteger maxLength = numberLength(maxnumber);
// 按照从低位到高位的顺序执行排序过程
for (int digit = 1; digit <= maxLength; digit++) {
// 入桶
for (NSNumber *item in array) {
//确定item 归属哪个桶 以digit位数为基数
NSInteger baseNumber = [self fetchBaseNumber:item digit:digit];
NSMutableArray *mutArray = buckt[baseNumber];
//将数据放入空桶上
[mutArray addObject:item];
}
NSInteger index = 0;
//出桶
for (int i = 0; i < buckt.count; i++) {
NSMutableArray *array = buckt[i];
//将桶的数据放回待排数组中
while (array.count != 0) {
NSNumber *number = [array objectAtIndex:0];
array[index] = number;
[array removeObjectAtIndex:0];
index++;
}
}
}
NSLog(@"基数升序排序结果：%@", array);
}
//创建空桶
+ (NSMutableArray *)createBucket {
NSMutableArray *bucket = [NSMutableArray array];
for (int index = 0; index < 10; index++) {
NSMutableArray *array = [NSMutableArray array];
[bucket addObject:array];
}
return bucket;
}
//数据最大值
+ (NSNumber *)listMaxItem:(NSArray *)list {
NSNumber *maxNumber = list[0];
for (NSNumber *number in list) {
if ([maxNumber integerValue] < [number integerValue]) {
maxNumber = number;
}
}
return maxNumber;
}
//数字的位数
NSInteger numberLength(NSNumber *number) {
NSString *string = [NSString stringWithFormat:@"%ld", (long)[number integerValue]];
return string.length;
}
+ (NSInteger)fetchBaseNumber:(NSNumber *)number digit:(NSInteger)digit {
//digit为基数位数
if (digit > 0 && digit <= numberLength(number)) {
NSMutableArray *numbersArray = [NSMutableArray array];
// number的位数确定
NSString *string = [NSString stringWithFormat:@"%ld", [number integerValue]];
for (int index = 0; index < numberLength(number); index++) {
[numbersArray addObject:[string substringWithRange:NSMakeRange(index, 1)]];
}
// number的位数 是几位数的
NSString *str = numbersArray[numbersArray.count - digit];
return [str integerValue];
}
return 0;
}
算法分析
基数排序的性能
时间复杂度
假设在基数排序中，r为基数，d为位数。则基数排序的时间复杂度为O(d(n+r))。我们可以看出，基数排序的效率和初始序列是否有序没有关联。
空间复杂度
在基数排序过程中，对于任何位数上的基数进行“装桶”操作时，都需要n+r个临时空间。
算法稳定性
是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。
