八大排序之堆排序--基数排序 java

电玩女神 2022-05-09 05:46 237阅读 0赞

## 八大排序之堆排序 - - 基数排序 java ##

算法过程：  
1、初始化：构造一个10\*n的二维数组，一个长度为n的数组用于存储每次位排序时每个桶子里有多少个元素。  
2、循环操作：从低位开始（我们采用LSD的方式），将所有元素对应该位的数字存到相应的桶子里去（对应二维数组的那一列）。然后将所有桶子里的元素按照桶子标号从小到大取出，对于同一个桶子里的元素，先放进去的先取出，后放进去的后取出（保证排序稳定性）。这样原数组就按该位排序完毕了，继续下一位操作，直到最高位排序完成。

代码：

import java.util.Scanner;
        
        public class Main {
        	public static void main(String[] args) {
        		Scanner sc = new Scanner(System.in);
        		String[] st = sc.nextLine().split(",");
        		int[] arr = new int[st.length];
        		for (int i = 0; i < arr.length; i++) {
        			arr[i] = Integer.parseInt(st[i]);
        		}
        		radixSort(arr);
        		for (int num : arr) {
        			System.out.print(num + " ");
        		}
        	}
        
        	public static void radixSort(int[] arr) {
        		// 指数 -- 当对数组按各位进行排序时，exp=1；按十位进行排序时，exp=10；...
        		int exp;
        		// 数组a中的最大值
        		int max = getMax(arr);
        		// 从个位开始，对数组a按"指数"进行排序
        		for (exp = 1; max / exp > 0; exp *= 10) {
        			countSort(arr, exp);
        		}
        	}
        
        	public static int getMax(int[] arr) {
        		int max;
        		max = arr[0];
        		for (int i = 1; i < arr.length; i++) {
        			if (max < arr[i]) {
        				max = arr[i];
        			}
        		}
        		return max;
        	}
        
        	public static void countSort(int[] arr, int exp) {
        		// 存储"被排序数据"的临时数组
        		int[] output = new int[arr.length];
        		int[] buckets = new int[10];
        		// 将数据出现的次数存储在buckets[]中
        		for (int i = 0; i < arr.length; i++) {
        			buckets[(arr[i] / exp) % 10]++;
        		}
        		// 更改buckets[i]。目的是让更改后的buckets[i]的值，是该数据在output[]中的位置。
        		for (int i = 1; i < 10; i++) {
        			buckets[i] += buckets[i - 1];
        		}
        		// 将数据存储到临时数组output[]中
        		for (int i = arr.length - 1; i >= 0; i--) {
        			output[buckets[(arr[i] / exp) % 10] - 1] = arr[i];
        			buckets[(arr[i] / exp) % 10]--;
        		}
        		// 将排序好的数据赋值给arr[]
        		for (int i = 0; i < arr.length; i++) {
        			arr[i] = output[i];
        		}
        		output = null;
        		buckets = null;
        	}
        }