基数排序(桶排序) 算法与数据结构

第一步
以LSD为例，假设原来有一串数值如下所示： 73, 22, 93, 43, 55, 14, 28, 65, 39, 81 首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中： 0 1 81 2 22 3 73 93 43 4 14 5 55 65 6 7 8 28 9 39 第二步
接下来将这些桶子中的数值重新串接起来，成为以下的数列： 81, 22, 73, 93, 43, 14, 55, 65, 28, 39 接着再进行一次分配，这次是根据十位数来分配： 0 1 14 2 22 28 3 39 4 43 5 55 6 65 7 73 8 81 9 93 第三步
接下来将这些桶子中的数值重新串接起来，成为以下的数列： 14, 22, 28, 39, 43, 55, 65, 73, 81, 93 这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。 LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。 java实现

public static int getMax(int[] list) { int max = list[0]; for (int i = 1; i < list.length; i++) { if (max < list[i]) { max = list[i]; } } return max; }

// 基数排序 public static void radixSort(int[] list) { // 获得列表中的最大数 int max = getMax(list); System.out.println("最大值是：" + max); //获得最大位数 int d = 1; while (true) { max = max / 10; if (max == 0) break; d++; } System.out.println("最大值位数是：" + d); int k = 1; int rate = 1; while (k <= d) { int m = 0; int[][] tmplist = new int[10][list.length]; //数组的第一维表示可能的余数0-9 int[] order = new int[10]; for (int i = 0; i < list.length; i++) { int tmpkey = (list[i] / rate) % 10; tmplist[tmpkey][order[tmpkey]] = list[i]; //相同余数的放到同一桶的下一个坑里 order[tmpkey] = order[tmpkey] + 1; } //将排序后的数组重新填入原list for (int j = 0; j < order.length; j++) {for (int i = 0; i < order[j]; i++) { list[m] = tmplist[j][i]; m++; }} k++; rate = rate * 10; print(list); } }