当前位置:  首页>> 技术小册>> Java面试指南

基数排序(Radix Sort)是一种非比较排序算法,它按照个位、十位、百位…的顺序依次对待排序元素进行排序。接下来,我将为您提供使用Java语言实现基数排序的代码和说明。

代码如下:

  1. import java.util.Arrays;
  2. public class RadixSort {
  3. public static void main(String[] args) {
  4. int[] arr = { 53, 89, 150, 36, 633, 233, 71, 66, 322 };
  5. System.out.println("Original array: " + Arrays.toString(arr));
  6. radixSort(arr);
  7. System.out.println("Sorted array: " + Arrays.toString(arr));
  8. }
  9. public static void radixSort(int[] arr) {
  10. // 找到最大数,确定要排序几次
  11. int max = arr[0];
  12. for (int i = 1; i < arr.length; i++) {
  13. if (arr[i] > max) {
  14. max = arr[i];
  15. }
  16. }
  17. int count = 0;
  18. while (max > 0) {
  19. max /= 10;
  20. count++;
  21. }
  22. // 创建桶
  23. int[][] bucket = new int[10][arr.length];
  24. // 记录每个桶中实际存放的数据个数
  25. int[] bucketElementCount = new int[10];
  26. // 对每一位进行排序,从个位开始
  27. for (int i = 0, n = 1; i < count; i++, n *= 10) {
  28. for (int j = 0; j < arr.length; j++) {
  29. int digitOfElement = arr[j] / n % 10;
  30. bucket[digitOfElement][bucketElementCount[digitOfElement]] = arr[j];
  31. bucketElementCount[digitOfElement]++;
  32. }
  33. // 将桶中的数据取出来放回原数组
  34. int index = 0;
  35. for (int k = 0; k < bucketElementCount.length; k++) {
  36. if (bucketElementCount[k] != 0) {
  37. for (int l = 0; l < bucketElementCount[k]; l++) {
  38. arr[index++] = bucket[k][l];
  39. }
  40. bucketElementCount[k] = 0;
  41. }
  42. }
  43. }
  44. }
  45. }

在这个实现中,我们使用桶来存储排序元素,桶的个数为10,分别代表数字0-9。在排序的过程中,我们先找到要排序的元素中的最大值,然后确定需要排序的次数。对于每一次排序,我们按照从低位到高位的顺序,将元素存储到对应的桶中,最后将桶中的元素按照顺序取出,放回原数组。