基数排序
基数排序：LSD法，最低位优先 ，先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列；即元素从这个位排好序，然后再从十位排好序，直到最高位排序完成。时间复杂度为：O(d(n+radix)) 。
LSD基数排序：
- C++
void RadixSort(vector<int> &v, int d, int size){
int i, j, digit = 1;
queue<int> digitQueue[10]; //对应位的队列
for(i = 0; i < d; i++){
for(j = 0; j < size; j++){
digitQueue[(v[j] / digit)%10].push(v[j]);
}
j = 0;
for(int digitValue = 0; digitValue < 10; digitValue++){
while(!digitQueue[digitValue].empty()){
v[j] = digitQueue[digitValue].front();
digitQueue[digitValue].pop();
j++;
}
}
cout <<"经过第 " << i << " 次排序的结果如下:" << endl;
for(j = 0; j < size; j++){
cout << v[j] << " ";
}
cout << endl;
digit *= 10;
}
}
- JAVA
/**
* @param array 数组
* @param d 最高的位数 如 9999 则为4位
* @param len 数组长度
*/
public static void radixSort(int[] array, int d, int len){
int i, j, digit = 1;
Queue<Integer>[] digitQueue = new LinkedList[10]; //对应位的队列：个 十 百 千 万
for (i = 0; i < 10; i++){ //init instance
digitQueue[i] = new LinkedList<>();
}
for (i = 0; i < d; i++){ //从低位到高位遍历进行排序
for (j = 0; j < len; j++){
digitQueue[(array[j] / digit) % 10].offer(array[j]);
}
j = 0;
for (int digitValue = 0; digitValue < 10; digitValue++){
while (!digitQueue[digitValue].isEmpty()){
array[j] = digitQueue[digitValue].poll();
j++;
}
}
digit *= 10;
System.out.print(String.format("经过第%d次排序的结果如下：", i));
for (j = 0; j < len; j++){
System.out.print(array[j] + " ");
}
System.out.println();
}
}
测试样例
- 100, 594, 300, 99, 7
经过第0次排序的结果如下：100 300 594 7 99
经过第1次排序的结果如下：100 300 7 594 99
经过第2次排序的结果如下：7 99 100 300 594
----- end -----