publicstaticvoidradixSort(int[] arr){ int[][] bucket = newint[10][arr.length]; int[] bucketElementCounts = newint[10]; //获取最大数有多少位 int max = arr[0]; for (int i = 0; i < arr.length; i++) { if (max < arr[i]) { max = arr[i]; } } int maxLength = (max + "").length(); for (int k = 0, n = 1; k < maxLength; k++, n *= 10) { for (int i = 0; i < arr.length; i++) { int digitOfElement = arr[i] / n % 10; bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[i]; bucketElementCounts[digitOfElement]++; } int index = 0; for (int i = 0; i < bucketElementCounts.length; i++) { if (bucketElementCounts[i] != 0) { for (int j = 0; j < bucketElementCounts[i]; j++) { arr[index++] = bucket[i][j]; } } bucketElementCounts[i] = 0; } } } }
publicstaticvoidmain(String[] args){; // 创建要给8000000个的随机的数组,八百万 int[] arr = newint[8000000]; for (int i = 0; i < 8000000; i++) { arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数 }
Date data1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String date1Str = simpleDateFormat.format(data1); System.out.println("排序前的时间是=" + date1Str);
radixSort(arr);
Date data2 = new Date(); String date2Str = simpleDateFormat.format(data2); System.out.println("排序后的时间是=" + date2Str); }
publicstaticvoidradixSort(int[] arr){ int[][] bucket = newint[10][arr.length]; int[] bucketElementCounts = newint[10]; //获取最大数有多少位 int max = arr[0]; for (int i = 0; i < arr.length; i++) { if (max < arr[i]) { max = arr[i]; } } int maxLength = (max + "").length(); for (int k = 0, n = 1; k < maxLength; k++, n *= 10) { for (int i = 0; i < arr.length; i++) { int digitOfElement = arr[i] / n % 10; bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[i]; bucketElementCounts[digitOfElement]++; } int index = 0; for (int i = 0; i < bucketElementCounts.length; i++) { if (bucketElementCounts[i] != 0) { for (int j = 0; j < bucketElementCounts[i]; j++) { arr[index++] = bucket[i][j]; } } bucketElementCounts[i] = 0; } } } }