RadixSort
class Queue {
int data[];
int front;
int rear;
}
public class RadixSort {
public static int getMaxNumber(int array[]) {
int tmp = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] > tmp) {
tmp = array[i];
}
}
return tmp;
}
public static int getMaxDigit(int maxnumber) {
int maxdigit = 0;
for (int i = maxnumber; i > 0; i = i / 10) {
maxdigit++;
}
return maxdigit;
}
public static void radixSort(int array[]) {
int max_number = getMaxNumber(array);
int max_digit = getMaxDigit(max_number);
//十个队列，分别存储数位数值为0-9的元素,各队列初始化
Queue [] queues = new Queue[10];
for(int i = 0; i <= 9; i++) {
queues[i] = new Queue();
queues[i].data = new int[array.length];
queues[i].front = queues[i].rear = -1;
}
int current_digit = 1;
while(current_digit <= max_digit) {
int current_digit_base = (int) Math.pow(10,current_digit-1);
//根据余数（队号）分配入队
for(int i = 0; i <= array.length-1; i++) {
int remainder = array[i] / current_digit_base % 10;
queues[remainder].rear++;//初始状态为-1
queues[remainder].data[queues[remainder].rear] = array[i];
}
//从队号0-9顺序出队收集元素
int tmp = 0;
for (int i = 0; i < queues.length; i++) {
while (queues[i].front != queues[i].rear) {
queues[i].front++;//初始状态为-1
array[tmp++] = queues[i].data[queues[i].front];
}
//收集后queues[i]重新回到-1状态
queues[i].front = queues[i].rear = -1;
}
current_digit ++;
}
}
}
待改进1：排序分析、时间复杂度和空间复杂度分析
待改进2：排序GIF图
小白发文，有错及不足请指出，嘻嘻????~~~，Learning on the way~~~
