在基数排序中，没有任何元素的比较和交换，元素只是在每一轮中从一个队列移动到另一个队列。对于给定的基数，遍历数据的轮次是一个常数，它与排序关键字的数目无关，于是，基数排序算法的时间复杂度为O(n)
1.基数排序算法要根据给定问题特别设计；
2.如果排序关键字中的数字数目与列表中元素的数目接近，那么算法的时间复杂度接近O(n平方)；
3.基数影响空间复杂度。
package MySort;
import java.util.Arrays;
public class MySortTest9 {
public static void main(String[] args) {
int[] data = { 1, 3, 6, 2, 4, 8, 9, 5, 12 };
// 5.分配排序（基数排序）
System.out.println("基数排序：\t" + Arrays.toString(radixSort(data, getMaxWeishu(data))));
}
// 求得最大位数d
public static int getMaxWeishu(int[] a) {
int max = a[0];
for (int i = 0; i < a.length; i++) {
if (a[i] > max)
max = a[i];
}
int tmp = 1, d = 1;
while (true) {
tmp *= 10;
if (max / tmp != 0) {
d++;
} else
break;
}
return d;
}
// pos=1表示个位，pos=2表示十位
public static int getNumInPos(int num, int pos) {
int tmp = 1;
for (int i = 0; i < pos - 1; i++) {
tmp *= 10;
}
return (num / tmp) % 10;
}
private static int[] radixSort(int[] data, int d) {
int[][] array = new int[10][data.length + 1];
for (int i = 0; i < 10; i++) {
array[i][0] = 0;
// array[i][0]记录第i行数据的个数
}
for (int pos = 1; pos <= d; pos++) {
for (int i = 0; i < data.length; i++) {
// 分配过程
int row = getNumInPos(data[i], pos);
int col = ++array[row][0];
array[row][col] = data[i];
}
for (int row = 0, i = 0; row < 10; row++) {
// 收集过程
for (int col = 1; col <= array[row][0]; col++) {
data[i++] = array[row][col];
}
array[row][0] = 0;
// 复位，下一个pos时还需使用
}
}
return data;
}
}
上述文字均来自网络的整理，接下来我会慢慢整理，根据个人理解优化文字部分；
以下为上述代码的合集
package MySort;
import java.util.Arrays;
/*
上述文字均来自网络的整理，接下来我会慢慢整理，根据个人理解优化文字部分；
以下为上述代码的合集
*/
public class MySortTest {
public static void main(String[] args) {
// 原始数据
int[] data1 = { 1, 3, 6, 2, 4, 8, 9, 5, 12 };
int[] data2 = { 1, 3, 6, 2, 4, 8, 9, 5, 12 };
int[] data3 = { 1, 3, 6, 2, 4, 8, 9, 5, 12 };
int[] data4 = { 1, 3, 6, 2, 4, 8, 9, 5, 12 };
int[] data5 = { 1, 3, 6, 2, 4, 8, 9, 5, 12 };
int[] data6 = { 1, 3, 6, 2, 4, 8, 9, 5, 12 };
int[] data7 = { 1, 3, 6, 2, 4, 8, 9, 5, 12 };
int[] data8 = { 1, 3, 6, 2, 4, 8, 9, 5, 12 };
// 1.插入排序:直接插入排序
System.out.println("插入排序：\t" + Arrays.toString(insertSort(data1)));
// 1.插入排序:希尔排序
System.out.println("希尔排序：\t" + Arrays.toString(shellSort(data2)));
// 2.交换排序:冒泡排序
System.out.println("冒泡排序：\t" + Arrays.toString(bubbleSort(data3)));
// 2.交换排序:快速排序
System.out.println("快速排序：\t" + Arrays.toString(quickSort(data4, 0, data4.length - 1)));
// 3.选择排序:直接选择排序
System.out.println("直接排序：\t" + Arrays.toString(chooseSort(data5)));
// 3.选择排序:堆排序
System.out.println("堆排序：\t" + Arrays.toString(heapSort(data6)));
// 4.归并排序
mergeSort(data7, 0, data7.length - 1);
System.out.println("归并排序：\t" + Arrays.toString(data7));
// 5.分配排序（基数排序）
System.out.println("基数排序：\t" + Arrays.toString(radixSort(data8, getMaxWeishu(data8))));
}