一、算法描述
基数排序是另外一种比较有特色的排序方式，它是怎么排序的呢？我们可以按照下面的一组数字做出说明：12、 104、 13、 7、 9
（1）按个位数排序是12、13、104、7、9
（2）再根据十位排序104、7、9、12、13
（3）再根据百位排序7、9、12、13、104
这里注意，如果在某一位的数字相同，那么排序结果要根据上一轮的数组确定，举个例子来说：07和09在十分位都是0，但是上一轮排序的时候09是排在07后面的；同样举一个例子，12和13在十分位都是1，但是由于上一轮12是排在13前面，所以在十分位排序的时候，12也要排在13前面。
所以，一般来说，基数排序的算法应该是这样的？
（1）判断数据在个位的大小，排列数据；
（2）根据（1）的结果，判断数据在十分位的大小，排列数据。如果数据在这个位置的余数相同，那么数据之间的顺序根据上一轮的排列顺序确定；
（3）依次类推，继续判断数据在百分位、千分位......上面的数据重新排序，直到所有的数据在某一分位上数据都为0。
算法分析
二、算法分析
平均时间复杂度：O(dn)(d即表示整形的最高位数)
空间复杂度：O(10n) （10表示0~9，用于存储临时的序列）
稳定性：稳定
三、算法实现
swift:
/********************************************************
*函数名称：GetNumInPos
*参数说明：num 一个整形数据
* pos 表示要获得的整形的第pos位数据
*说明： 找到num的从低到高的第pos位的数据
*********************************************************/
func GetNumInPos(num:Int,pos:Int)->Int{
var temp = 1
for _ in 0..<pos-1{
temp *= 10
}
return (num/temp)%10
}
/********************************************************
*函数名称：RadixSort
*参数说明：pDataArray 无序数组；
* iDataNum为无序数据个数
*说明： 基数排序
*********************************************************/
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 //关键字个数，这里为32位整形位数
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 //复位
}
}
}
}
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; //关键字个数，这里为32位整形位数
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; //复位
}
}
}
