将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序
要求:将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序
package com.xuge.sort; import java.util.Arrays; /** * author: yjx * Date :2022/5/3022:05 **/ public class RadixSort { public static void main(String[] args) { int[] arr = {53, 3, 542, 748, 14, 214}; redisSort(arr); } public static void redisSort(int[] arr) { //1.得到数组中最大的位数 int max = arr[0]; for(int i=1;i<arr.length;i++){ if(max<arr[i]){ max=arr[i]; } } int maxLength = (max + "").length(); //2.遍历maxLength轮 for (int i = 0 ,n=1; i < maxLength; i++,n*=10) { //针对每一个位排序 //1.第一轮排序 针对每个元素各位 //2.二维数组包含10个一维数组,每个一维数组大小定位arr.length; //3.是使用空间换时间的经典算法 int[][] buceket = new int[10][arr.length]; //为了记录每个桶实际存放的数据个数 //buceketElementCounts[0]记录第0个桶放入数据个数 int[] buceketElementCounts = new int[10]; for (int j = 0; j < arr.length; j++) { //取出每个元素的个位数 int digitOfElement = arr[j] /n%10; //放入到对应桶中 buceket[digitOfElement][buceketElementCounts[digitOfElement]] = arr[j]; //后移 buceketElementCounts[digitOfElement]++; } //按造这个桶的顺序(一维数组下标,依次取出数据,放入原来数组) int index = 0; //遍历每一个桶,依次取数据 for (int k = 0; k < buceketElementCounts.length; k++) { //如果桶中有数据,才放入数据 if (buceketElementCounts[k] != 0) { //循环第k个桶,即第k个一维数组 for (int l = 0; l < buceketElementCounts[k]; l++) { //取出元素放入arr[index]中 arr[index++] = buceket[k][l]; } } //第一轮处理后,需要将buceketElementCounts置0 buceketElementCounts[k] = 0; } System.out.println("第"+(i+1)+"轮排序:" + Arrays.toString(arr)); } /* //1.第一轮排序 针对每个元素各位 //2.二维数组包含10个一维数组,每个一维数组大小定位arr.length; //3.是使用空间换时间的经典算法 int [] [] buceket=new int [10][arr.length]; //为了记录每个桶实际存放的数据个数 //buceketElementCounts[0]记录第0个桶放入数据个数 int []buceketElementCounts=new int [10]; for(int j=0;j<arr.length;j++){ //取出每个元素的个位数 int digitOfElement=arr[j]%10; //放入到对应桶中 buceket[digitOfElement][buceketElementCounts[digitOfElement]]=arr[j]; //后移 buceketElementCounts[digitOfElement]++; } //按造这个桶的顺序(一维数组下标,依次取出数据,放入原来数组) int index=0; //遍历每一个桶,依次取数据 for(int k=0;k<buceketElementCounts.length;k++){ //如果桶中有数据,才放入数据 if(buceketElementCounts[k]!=0){ //循环第k个桶,即第k个一维数组 for(int l=0;l<buceketElementCounts[k];l++){ //取出元素放入arr[index]中 arr[index++]=buceket[k][l]; } } //第一轮处理后,需要将buceketElementCounts置0 buceketElementCounts[k]=0; } System.out.println("第一轮排序:"+ Arrays.toString(arr)); for(int j=0;j<arr.length;j++){ //取出每个元素的十位数 int digitOfElement=arr[j]/10%10; //放入到对应桶中 buceket[digitOfElement][buceketElementCounts[digitOfElement]]=arr[j]; //后移 buceketElementCounts[digitOfElement]++; } //按造这个桶的顺序(一维数组下标,依次取出数据,放入原来数组) index=0; //遍历每一个桶,依次取数据 for(int k=0;k<buceketElementCounts.length;k++){ //如果桶中有数据,才放入数据 if(buceketElementCounts[k]!=0){ //循环第k个桶,即第k个一维数组 for(int l=0;l<buceketElementCounts[k];l++){ //取出元素放入arr[index]中 arr[index++]=buceket[k][l]; } } //第二轮处理后,需要将buceketElementCounts置0 buceketElementCounts[k]=0; } System.out.println("第二轮排序:"+ Arrays.toString(arr)); for(int j=0;j<arr.length;j++){ //取出每个元素的十位数 int digitOfElement=arr[j]/100; //放入到对应桶中 buceket[digitOfElement][buceketElementCounts[digitOfElement]]=arr[j]; //后移 buceketElementCounts[digitOfElement]++; } //按造这个桶的顺序(一维数组下标,依次取出数据,放入原来数组) index=0; //遍历每一个桶,依次取数据 for(int k=0;k<buceketElementCounts.length;k++){ //如果桶中有数据,才放入数据 if(buceketElementCounts[k]!=0){ //循环第k个桶,即第k个一维数组 for(int l=0;l<buceketElementCounts[k];l++){ //取出元素放入arr[index]中 arr[index++]=buceket[k][l]; } } //第二轮处理后,需要将buceketElementCounts置0 buceketElementCounts[k]=0; } System.out.println("第三轮排序:"+ Arrays.toString(arr)); */ } }
public static void main(String[] args) { // int[] arr = {53, 3, 542, 748, 14, 214}; // redisSort(arr); int arr2[] = new int[800000]; for (int i = 0; i < 800000; i++) { arr2[i] = (int) (Math.random() * 800000000);//生成随机数[0,80000000); } System.out.println("====输出数组====="); Date data = new Date(); SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String str = sdf.format(data); System.out.println("排序前的时间是:" + str);//23 redisSort(arr2); Date data2 = new Date(); String str2 = sdf.format(data2); System.out.println("排序后的时间是" + str2);//25 }