数据结构-基数排序(java代码)

解题思路:

        正整数从小到大的基数排序就是从个位数开始，将待排序数组中的值按照个位数从小到大的顺序进行排序，然后再进行十位数的排序，以此类推，直到数组中的最大值的最高位排序完毕即可。

        算法过程如图所示，创建10个容器，遍历待排序数组，个位数为0的值存储在下标为0的容器中，以此类推，将数组中的每一个值都存储在相应下标的容器中，数组遍历完便存储完毕，然后再从下标为0的容器开始依次将容器中的值赋值给数组。然后在十位数上进行类似操作，以此类推，直到数组中的最大值的最高位排序完毕，基数排序完成。
        注意事项:

参考代码:

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		//保存待排序数组
		int[] num = new int[n];
		for (int i = 0; i < num.length; i++) {
			num[i] = scanner.nextInt();
		}
		//基数排序
		radixSort(num);
		for (int i = 0; i < num.length; i++) {
			System.out.print(num[i] + " ");
		}
		System.out.println();
		scanner.close();
	}

	public static void radixSort(int[] num) {
		//用max存储待排序数组中最大值
		int max = num[0];
		for (int i = 0; i < num.length; i++) {
			if (max < num[i]) {
				max = num[i];
			}
		}
		//maxDight存储最大值有多少位
		int maxDigit = String.valueOf(max).length();
		//一趟循环比较一位，进行maxDight次循环，第一次循环比较个位，第二次循环比较十位，以此类推
		for (int i = 0, n = 1; i < maxDigit; i++, n= n*10) {
			//创建bucket存储数据，长度从0~9，bucket[0]存储当前循环比较的位中为0的数，以此类推
			ArrayList[] bucket = new ArrayList[10];
			for (int j = 0; j < bucket.length; j++) {
				bucket[j] = new ArrayList();
			}
			//遍历待排序数组，position为数组的每一个数在当前循环中比较的位上的值
			for (int j = 0; j < num.length; j++) {
				int position = num[j] / n %10;
				bucket[position].add(num[j]);
			}
			int k = 0;
			//将存储在bucket中的值赋值给待排序数组
			for (ArrayList arrayList : bucket) {
				for (Object temp : arrayList) {
					num[k++] = (int) temp;
				}
			}
			//清除bucket中的数据
			for (ArrayList arrayList : bucket) {
				arrayList.clear();
			}
		}
	}
}