基數排序
假設有10萬個手機號碼庙曙，希望將這10萬個手機號從小到大排序焕阿，有什么比較快速地排序方法呢狈癞？
快排時間復雜度可以做到O(nlogn)，還有更高效的排序算法嗎嚷缭？桶排序、計數排序能派上用場嗎耍贾？手機號有11位峭状，范圍太大，顯然不適合用這兩種排序算法逼争。針對這個排序問題优床，有沒有時間復雜度是O(n)的算法呢？
這個問題里有這樣的規(guī)律：假設要比較兩個手機號碼a,b的大小誓焦，如果在前面幾位中胆敞，a手機號碼已經比b手機號碼大了，那后面的幾位就不用看了杂伟。
借助穩(wěn)定排序算法移层，先按照最后一位來排序手機號碼，然后赫粥，再按照倒數第二位重新排序观话，以此類推，最后按照第一位重新排序越平。經過11次排序之后频蛔，手機號碼就都有序了。
注意秦叛，這里按照每位來排序的排序算法要是穩(wěn)定的晦溪，否則這個實現思路就是不正確的。因為如果是非穩(wěn)定排序算法挣跋，那最后一次排序只會考慮最高位的大小順序三圆，完全不管其他位的大小關系，那么低位的排序就完全沒有意義了。
根據每一位來排序舟肉，可以用剛講過的桶排序或者計數排序修噪，它們的時間復雜度可以做到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
