一麸祷、算法描述
基數(shù)排序是另外一種比較有特色的排序方式澎怒，它是怎么排序的呢？我們可以按照下面的一組數(shù)字做出說(shuō)明：12阶牍、 104喷面、 13、 7走孽、 9
（1）按個(gè)位數(shù)排序是12惧辈、13、104磕瓷、7盒齿、9
（2）再根據(jù)十位排序104念逞、7、9边翁、12翎承、13
（3）再根據(jù)百位排序7、9符匾、12叨咖、13、104
這里注意啊胶，如果在某一位的數(shù)字相同甸各，那么排序結(jié)果要根據(jù)上一輪的數(shù)組確定，舉個(gè)例子來(lái)說(shuō)：07和09在十分位都是0创淡，但是上一輪排序的時(shí)候09是排在07后面的痴晦；同樣舉一個(gè)例子，12和13在十分位都是1琳彩，但是由于上一輪12是排在13前面誊酌，所以在十分位排序的時(shí)候，12也要排在13前面露乏。
所以碧浊，一般來(lái)說(shuō)，基數(shù)排序的算法應(yīng)該是這樣的瘟仿？
（1）判斷數(shù)據(jù)在個(gè)位的大小箱锐，排列數(shù)據(jù)；
（2）根據(jù)（1）的結(jié)果劳较，判斷數(shù)據(jù)在十分位的大小驹止，排列數(shù)據(jù)。如果數(shù)據(jù)在這個(gè)位置的余數(shù)相同观蜗，那么數(shù)據(jù)之間的順序根據(jù)上一輪的排列順序確定臊恋；
（3）依次類推，繼續(xù)判斷數(shù)據(jù)在百分位墓捻、千分位......上面的數(shù)據(jù)重新排序抖仅，直到所有的數(shù)據(jù)在某一分位上數(shù)據(jù)都為0。
算法分析
二砖第、算法分析
平均時(shí)間復(fù)雜度：O(dn)(d即表示整形的最高位數(shù))
空間復(fù)雜度：O(10n) （10表示0~9撤卢，用于存儲(chǔ)臨時(shí)的序列）
穩(wěn)定性：穩(wěn)定
三、算法實(shí)現(xiàn)
swift:
/********************************************************
*函數(shù)名稱：GetNumInPos
*參數(shù)說(shuō)明：num 一個(gè)整形數(shù)據(jù)
* pos 表示要獲得的整形的第pos位數(shù)據(jù)
*說(shuō)明： 找到num的從低到高的第pos位的數(shù)據(jù)
*********************************************************/
func GetNumInPos(num:Int,pos:Int)->Int{
var temp = 1
for _ in 0..<pos-1{
temp *= 10
}
return (num/temp)%10
}
/********************************************************
*函數(shù)名稱：RadixSort
*參數(shù)說(shuō)明：pDataArray 無(wú)序數(shù)組梧兼；
* iDataNum為無(wú)序數(shù)據(jù)個(gè)數(shù)
*說(shuō)明： 基數(shù)排序
*********************************************************/
func RadixSort(pDataArray:inout [Int], iDataNum:Int){
var radixArrays = [[Int]]()
for _ in 0..<10 {
radixArrays.append([Int](repeating: 0, count: iDataNum+1))
}
let KEYNUM_31 = 10 //關(guān)鍵字個(gè)數(shù)放吩，這里為32位整形位數(shù)
for pos in 1...KEYNUM_31 { //從各位開(kāi)始到31位
for i in 0..<iDataNum {//分配過(guò)程
let num = GetNumInPos(num: pDataArray[i], pos: pos)
radixArrays[num][0] = radixArrays[num][0]+1
let index = radixArrays[num][0]
radixArrays[num][index] = pDataArray[i]
}
var j = 0
for m in 0..<10 { //收集
if radixArrays[m][0] != 0{
for k in 1...radixArrays[m][0] {
pDataArray[j] = radixArrays[m][k]
j = j + 1
}
radixArrays[m][0] = 0 //復(fù)位
}
}
}
}
OC:
- (int)GetNumInPos:(int)num pos:(int)pos{
int temp = 1;
for (int i=0; i<pos-1; i++) {
temp *= 10;
}
return (num/temp)%10;
}
- (void)RadixSort:(NSMutableArray *) pDataArray iDataNum:(int)iDataNum{
NSMutableArray *radixArrays = [NSMutableArray array];
for (int i=0; i<10; i++) {
NSMutableArray *arr = [NSMutableArray array];
for (int i=0; i<iDataNum; i++) {
[arr addObject:@0];
}
[radixArrays addObject:arr];
}
int KEYNUM_31 = 10; //關(guān)鍵字個(gè)數(shù)，這里為32位整形位數(shù)
for (int pos =1; pos<=KEYNUM_31; pos++) {
for (int i=0; i<iDataNum; i++) {
int num = [self GetNumInPos:[pDataArray[i] intValue] pos:pos];
int num2 = [radixArrays[num][0] intValue]+1;
radixArrays[num][0] = @(num2);
radixArrays[num][num2] = pDataArray[i];
}
for (int i=0,j=0; i<10; i++) {
for (int k=1; k<=[radixArrays[i][0] intValue]; k++) {
pDataArray[j]=radixArrays[i][k];
j=j+1;
}
radixArrays[i][0] = @0; //復(fù)位
}
}
}
