基數(shù)排序
基數(shù)排序(Radix Sort)是根據(jù)關鍵字中各位的值，通過對排序的N個元素進行若干趟“分配”與“收集”來實現(xiàn)排序的腺阳。
算法思想
-
基于LSD方法的鏈式基數(shù)排序的基本思想
“多關鍵字排序”的思想實現(xiàn)“單關鍵字排序”。對數(shù)字型或字符型的單關鍵字盖溺，可以看作由多個數(shù)位或多個字符構成的多關鍵字遇革，此時可以采用“分配-收集”的方法進行排序沉噩，這一過程稱作基數(shù)排序法吏祸，其中每個數(shù)字或字符可能的取值個數(shù)稱為基數(shù)对蒲。比如，撲克牌的花色基數(shù)為4贡翘，面值基數(shù)為13蹈矮。在整理撲克牌時，既可以先按花色整理床估，也可以先按面值整理。按花色整理時诱渤，先按紅丐巫、黑、方勺美、花的順序分成4摞（分配）递胧，再按此順序再疊放在一起（收集），然后按面值的順序分成13摞（分配）赡茸，再按此順序疊放在一起（收集）缎脾，如此進行二次分配和收集即可將撲克牌排列有序。
-
基數(shù)排序?qū)崿F(xiàn)步驟
判斷數(shù)據(jù)在各位的大小占卧，排列數(shù)據(jù)
根據(jù)上一步的結果遗菠，判斷數(shù)據(jù)在十分位的大小联喘，排列數(shù)據(jù)。如果數(shù)據(jù)在這個位置的余數(shù)相同辙纬，那么數(shù)據(jù)之間的順序根據(jù)上一輪的排列順序確定
依次類推豁遭，繼續(xù)判斷數(shù)據(jù)在百分位、千分位......上面的數(shù)據(jù)重新排序贺拣，直到所有的數(shù)據(jù)在某一分位上數(shù)據(jù)都為0
-
基數(shù)排序?qū)崿F(xiàn)步驟實例
假設有欲排數(shù)據(jù)序列如下所示：
73 22 93 43 55 14 28 65 39 81
首先根據(jù)個位數(shù)的數(shù)值蓖谢，在遍歷數(shù)據(jù)時將它們各自分配到編號0至9的桶（個位數(shù)值與桶號一一對應）中。
分配結果分配結束后譬涡。接下來將所有桶中所盛數(shù)據(jù)按照桶號由小到大（桶中由頂至底）依次重新收集串起來闪幽，得到如下仍然無序的數(shù)據(jù)序列：
81 22 73 93 43 14 55 65 28 39
接著，再進行一次分配涡匀，這次根據(jù)十位數(shù)值來分配（原理同上）
分配結果分配結束后盯腌。接下來再將所有桶中所盛的數(shù)據(jù)（原理同上）依次重新收集串接起來，得到如下的數(shù)據(jù)序列：
14 22 28 39 43 55 65 73 81 93
觀察可以看到渊跋，此時原無序數(shù)據(jù)序列已經(jīng)排序完畢腊嗡。如果排序的數(shù)據(jù)序列有三位數(shù)以上的數(shù)據(jù)，則重復進行以上的動作直至最高位數(shù)為止拾酝。
代碼范例：
#pragma mark --- 基數(shù)排序
/**
基數(shù)排序
@param array 需要排序的Array
*/
+ (void)radixSort:(NSMutableArray *)array
{
/**
基于LSD方法的鏈式基數(shù)排序的基本思想
“多關鍵字排序”的思想實現(xiàn)“單關鍵字排序”燕少。對數(shù)字型或字符型的單關鍵字，可以看作由多個數(shù)位或多個字符構成的多關鍵字蒿囤，此時可以采用“分配-收集”的方法進行排序客们，這一過程稱作基數(shù)排序法，其中每個數(shù)字或字符可能的取值個數(shù)稱為基數(shù)材诽。比如底挫，撲克牌的花色基數(shù)為4，面值基數(shù)為13脸侥。在整理撲克牌時建邓，既可以先按花色整理，也可以先按面值整理睁枕。按花色整理時官边，先按紅、黑外遇、方注簿、花的順序分成4摞（分配），再按此順序再疊放在一起（收集）跳仿，然后按面值的順序分成13摞（分配）诡渴，再按此順序疊放在一起（收集），如此進行二次分配和收集即可將撲克牌排列有序菲语。
基數(shù)排序:
是按照低位先排序妄辩，然后收集惑灵；再按照高位排序，然后再收集恩袱；依次類推泣棋，直到最高位。有時候有些屬性是有優(yōu)先級順序的畔塔，先按低優(yōu)先級排序潭辈，再按高優(yōu)先級排序。最后的次序就是高優(yōu)先級高的在前澈吨，高優(yōu)先級相同的低優(yōu)先級高的在前把敢。基數(shù)排序基于分別排序谅辣，分別收集修赞，所以是穩(wěn)定的。
*/
//創(chuàng)建空桶
NSMutableArray *buckt = [self createBucket];
//待排數(shù)組的最大數(shù)值
NSNumber *maxnumber = [self listMaxItem:array];
//最大數(shù)值的數(shù)字位數(shù)
NSInteger maxLength = numberLength(maxnumber);
// 按照從低位到高位的順序執(zhí)行排序過程
for (int digit = 1; digit <= maxLength; digit++) {
// 入桶
for (NSNumber *item in array) {
//確定item 歸屬哪個桶 以digit位數(shù)為基數(shù)
NSInteger baseNumber = [self fetchBaseNumber:item digit:digit];
NSMutableArray *mutArray = buckt[baseNumber];
//將數(shù)據(jù)放入空桶上
[mutArray addObject:item];
}
NSInteger index = 0;
//出桶
for (int i = 0; i < buckt.count; i++) {
NSMutableArray *array = buckt[i];
//將桶的數(shù)據(jù)放回待排數(shù)組中
while (array.count != 0) {
NSNumber *number = [array objectAtIndex:0];
array[index] = number;
[array removeObjectAtIndex:0];
index++;
}
}
}
NSLog(@"基數(shù)升序排序結果：%@", array);
}
//創(chuàng)建空桶
+ (NSMutableArray *)createBucket {
NSMutableArray *bucket = [NSMutableArray array];
for (int index = 0; index < 10; index++) {
NSMutableArray *array = [NSMutableArray array];
[bucket addObject:array];
}
return bucket;
}
//數(shù)據(jù)最大值
+ (NSNumber *)listMaxItem:(NSArray *)list {
NSNumber *maxNumber = list[0];
for (NSNumber *number in list) {
if ([maxNumber integerValue] < [number integerValue]) {
maxNumber = number;
}
}
return maxNumber;
}
//數(shù)字的位數(shù)
NSInteger numberLength(NSNumber *number) {
NSString *string = [NSString stringWithFormat:@"%ld", (long)[number integerValue]];
return string.length;
}
+ (NSInteger)fetchBaseNumber:(NSNumber *)number digit:(NSInteger)digit {
//digit為基數(shù)位數(shù)
if (digit > 0 && digit <= numberLength(number)) {
NSMutableArray *numbersArray = [NSMutableArray array];
// number的位數(shù)確定
NSString *string = [NSString stringWithFormat:@"%ld", [number integerValue]];
for (int index = 0; index < numberLength(number); index++) {
[numbersArray addObject:[string substringWithRange:NSMakeRange(index, 1)]];
}
// number的位數(shù) 是幾位數(shù)的
NSString *str = numbersArray[numbersArray.count - digit];
return [str integerValue];
}
return 0;
}
算法分析
基數(shù)排序的性能
時間復雜度
假設在基數(shù)排序中桑阶，r為基數(shù)柏副，d為位數(shù)。則基數(shù)排序的時間復雜度為O(d(n+r))蚣录。我們可以看出割择，基數(shù)排序的效率和初始序列是否有序沒有關聯(lián)。
空間復雜度
在基數(shù)排序過程中萎河，對于任何位數(shù)上的基數(shù)進行“裝桶”操作時荔泳，都需要n+r個臨時空間。
算法穩(wěn)定性
是按照低位先排序虐杯，然后收集玛歌；再按照高位排序，然后再收集擎椰；依次類推支子，直到最高位。有時候有些屬性是有優(yōu)先級順序的达舒，先按低優(yōu)先級排序值朋，再按高優(yōu)先級排序。最后的次序就是高優(yōu)先級高的在前休弃，高優(yōu)先級相同的低優(yōu)先級高的在前吞歼∪Ω啵基數(shù)排序基于分別排序塔猾，分別收集，所以是穩(wěn)定的稽坤。
