基數(shù)排序
假設(shè)有10萬個手機(jī)號碼，希望將這10萬個手機(jī)號從小到大排序，有什么比較快速地排序方法呢？
快排時間復(fù)雜度可以做到O(nlogn)，還有更高效的排序算法嗎？桶排序、計數(shù)排序能派上用場嗎？手機(jī)號有11位，范圍太大，顯然不適合用這兩種排序算法。針對這個排序問題，有沒有時間復(fù)雜度是O(n)的算法呢？
這個問題里有這樣的規(guī)律：假設(shè)要比較兩個手機(jī)號碼a,b的大小，如果在前面幾位中，a手機(jī)號碼已經(jīng)比b手機(jī)號碼大了，那后面的幾位就不用看了。
借助穩(wěn)定排序算法，先按照最后一位來排序手機(jī)號碼，然后，再按照倒數(shù)第二位重新排序，以此類推，最后按照第一位重新排序。經(jīng)過11次排序之后，手機(jī)號碼就都有序了。
注意，這里按照每位來排序的排序算法要是穩(wěn)定的，否則這個實現(xiàn)思路就是不正確的。因為如果是非穩(wěn)定排序算法，那最后一次排序只會考慮最高位的大小順序，完全不管其他位的大小關(guān)系，那么低位的排序就完全沒有意義了。
根據(jù)每一位來排序，可以用剛講過的桶排序或者計數(shù)排序，它們的時間復(fù)雜度可以做到O(n)。如果要排序的數(shù)據(jù)有K位，那就需要k次桶排序或者計數(shù)排序，總的時間復(fù)雜度是O(K*n)。當(dāng)k不大的時候，比如手機(jī)號碼排序的例子，k最大就是11，所以基數(shù)排序的時間復(fù)雜度就近似于O(n)。
代碼實現(xiàn)如下：
@interface DMRadixSort : NSObject
// 基數(shù)排序
- (void)radixSort:(NSMutableArray *)dataArray;
@end
@implementation DMRadixSort
- (void)radixSort:(NSMutableArray *)dataArray
{
NSLog(@"基數(shù)排序前：%@", dataArray);
for (NSInteger i = 10; i >= 0; i--) {
[self radixSort:dataArray sortIndex:i];
NSLog(@"基數(shù)排序%ld位后數(shù)據(jù)：%@", (long)i, dataArray);
}
NSLog(@"基數(shù)排序后：%@", 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];
}
// 桶內(nèi)數(shù)據(jù)放回原數(shù)組
[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
{
// 基數(shù)排序
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
