基数排序
2021-04-19 06:29
标签：写代码 mat int color oid return 三次 例子 ++ 今天没事看了一下基数排序，说实话，我最不擅长的就是排序了，最近准备多刷一些排序题，练习一下； 首先啥是基数排序呢？来一个比较专业的说法，看看就行了： 基数排序（radix sort）属于“分配式排序”，又称桶子法，bucket或bin sort，将要排序的各各位的值分配至某些桶中，达到排序的目的；基数排序是稳定性的排序，是桶排序的扩展.... 反正就是一句话，就是将要排序的每个数的每一位进行一个排序，首先每个数的各位进行排序，然后十位进行排序，百位进行排序，依次类推 举个简单的例子，13，5，112，46,这四个数要进行排序的话，为了好看一些将位数比较少的添0，也就是变成013，005，112，046；然后我们准备10个桶，也就是一个大小为10的数组（为什么要是10呢？废话，每一位上的数字最大就是9啊！），下图所示，对个位数分别分配到对应的桶中 第二次排序：经过第一次排序的数组，再根据十位分配到各个桶 第三次排序，根据第二次排序后各个数的百位再分配到各个桶 然后结果就出来了，很神奇......妙啊妙啊！真的很有意思，嘿嘿 下面我们使用java代码来简单实现一下，首先问一下，任意给定一个int类型的整数，怎么获取它的位数呢？很简单，如下图所示： 然后再问一下，怎么获取一个整数的每一位上的数字呢？也很简单，下图所示：会依次输出4，3，2，1 ok，知道了这个时候我们就可以开始写代码了，写代码之前一定要思考一下怎么写，最好使用中文把思路写一下，无文档，不写代码！这里使用数组实现： 首先，我们肯定要将一个数组中的最大数字给找出来，因为这个最大数字的位数决定了我们需要进行排序的次数； 然后，由于是有十个桶，而每个桶里可能会放多个数据，那么最多是可以放多少个数据呢？很明显，是arr.length个，这里的arr.length指的是需要进行排序的数组中元素的个数 再然后，这十个桶应该就是一个二维数组（其实可以用其他的实现形式，比如数组+链表或者数组+栈都行，有兴趣的自己实现一下） 最后，我们每次将数组中共的数据丢到桶里，然后需要拿出来吧！所以我们也需要有个地方记录一下每个桶中元素的数量 代码如下，注释也比较清楚： 基数排序 标签：写代码 mat int color oid return 三次 例子 ++ 原文地址：https://www.cnblogs.com/wyq1995/p/13290751.html
1 public class Study0712 {
2 /**
3 * 基数排序
4 * @Title: radixSort
5 * @Description:
6 * @param arr
7 * @return: void
8 * @throws
9 */
10 public static void radixSort(int[] arr) {
11
12 // 将数组中最大的数字max找到
13 int max = arr[0];
14 for (int i = 1; i ) {
15 if (arr[i] > max) {
16 max = arr[i];
17 }
18 }
19 System.out.println("max=" + max);
20 // 十个桶
21 int[][] buckets = new int[10][arr.length];
22 // 该数组存放每一个桶中元素的数量,这个数组的索引和桶的索引对应
23 int[] bucketCount = new int[10];
24
25 // 需要排序的次数肯定就是max的位数
26 int sortNum = Integer.toString(max).length();
27 for (int j = 0; j ) {
28 // 遍历数组，第一次排序是用个位进行比较,第二次是用十位进行比较
29 for (int m = 0; m ) {
30 // 取出数组中每一个数字的某一位上的数字,这个数字就是桶的索引
31 int val = (int) (arr[m] / Math.pow(10, j) % 10);
32 // 如果val == 2,那就放在第二个桶中，第二桶中也可能有bucketCount[val]个元素了，所以放完元素之后需要++
33 buckets[val][bucketCount[val]++] = arr[m];
34 }
35
36 printTwo(buckets);
37
38 // 前面已经将元素都放进桶里了，现在取出来放到数组中
39 int index = 0;
40 for (int n = 0; n ) {
41 //遍历bucketCount中的元素，如果不为0，说明该对应的桶中有元素
42 if (bucketCount[n] != 0) {
43 for (int x = 0; x ) {
44 //获取桶中的元素，然后放入数组中，并将桶中该元素置为0
45 arr[index++] = buckets[n][x];
46 buckets[n][x] = 0;
47 }
48 }
49 //每一次将桶里的元素取出来的时候，需要将对应数组中表示该桶中元素数量置为0
50 //如果不置为0，那么在第二次从桶中拿元素放到数组中的时候，遍历bucketCount中的数据是之前桶中元素的数据（也许有6个桶中有数据）
51 bucketCount[n] =0;
52 }
53 System.out.println("第" + (j + 1) + "次排序的结果为：" + Arrays.toString(arr));
54
55 }
56
57 }
58
59 /**
60 * 遍历二维数据中的元素
61 * @Title: printTwo
62 * @Description:
63 * @param arrs
64 * @return: void
65 * @throws
66 */
67 public static void printTwo(int[][] arrs) {
68 for (int i = 0; i ) {
69 int[] arr = arrs[i];
70 for (int j = 0; j ) {
71 System.out.print(arr[j]);
72 }
73 System.out.println();
74 }
75 }
76
77 public static void main(String[] args) {
78 int[] arr = { 13, 5, 112, 46 };
79 radixSort(arr);
80
81 }
82
83 }
