一、算法描述

基數(shù)排序是另外一種比較有特色的排序方式，它是怎么排序的呢？我們可以按照下面的一組數(shù)字做出說明：12、 104、 13、 7、 9
（1）按個位數(shù)排序是12、13、104、7、9
（2）再根據(jù)十位排序104、7、9、12、13
（3）再根據(jù)百位排序7、9、12、13、104
這里注意，如果在某一位的數(shù)字相同，那么排序結(jié)果要根據(jù)上一輪的數(shù)組確定，舉個例子來說：07和09在十分位都是0，但是上一輪排序的時候09是排在07后面的；同樣舉一個例子，12和13在十分位都是1，但是由于上一輪12是排在13前面，所以在十分位排序的時候，12也要排在13前面。

所以，一般來說，基數(shù)排序的算法應(yīng)該是這樣的？
（1）判斷數(shù)據(jù)在個位的大小，排列數(shù)據(jù)；
（2）根據(jù)（1）的結(jié)果，判斷數(shù)據(jù)在十分位的大小，排列數(shù)據(jù)。如果數(shù)據(jù)在這個位置的余數(shù)相同，那么數(shù)據(jù)之間的順序根據(jù)上一輪的排列順序確定；
（3）依次類推，繼續(xù)判斷數(shù)據(jù)在百分位、千分位......上面的數(shù)據(jù)重新排序，直到所有的數(shù)據(jù)在某一分位上數(shù)據(jù)都為0。

算法分析

二、算法分析

平均時間復(fù)雜度：O(dn)(d即表示整形的最高位數(shù))
空間復(fù)雜度：O(10n) （10表示0~9，用于存儲臨時的序列）
穩(wěn)定性：穩(wěn)定

三、算法實(shí)現(xiàn)

swift:

/********************************************************
     *函數(shù)名稱：GetNumInPos
     *參數(shù)說明：num 一個整形數(shù)據(jù)
     *          pos 表示要獲得的整形的第pos位數(shù)據(jù)
     *說明：    找到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ù)說明：pDataArray 無序數(shù)組；
     *        iDataNum為無序數(shù)據(jù)個數(shù)
     *說明：    基數(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)鍵字個數(shù)，這里為32位整形位數(shù)
        for pos in 1...KEYNUM_31 { //從各位開始到31位
            for i in 0..<iDataNum {//分配過程
                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)鍵字個數(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ù)位
        }
        
    }
    
}