算法面经--基数排序

基数排序

一、算法思路

1.简单介绍

1）基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法

2. 基数排序(Radix Sort)是桶排序的扩

2.基本思想

将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

3.示意图

将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序

基数排序1.png 基数排序2.png 基数排序3.png

[图片上传失败...(image-9fa371-1591968647378)]

[图片上传失败...(image-678c0b-1591968647377)]

二、代码实现

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  int arr[] = { 53, 3, 542, 748, 14, 214};
  radixSort(arr);
  System.out.println("基数排序后 " + Arrays.toString(arr));
  }

  public static void radixSort(int[] arr){
  //1\. 得到数组中最大数的位数
  int max = arr[0];
  for(int i=0;i<arr.length;i++){
  if(arr[i]>max){
  max = arr[i];
  }
  }
  //得到最大数是几位数
  int maxLength = (max+"").length();  //利用字符串的长度求出位数
 ​
  //定义一个二维数组，表示10个桶, 每个桶就是一个一维数组
  //说明
  //1\. 二维数组包含10个一维数组
  //2\. 为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为arr.length
  //3\. 名明确，基数排序是使用空间换时间的经典算法
  int[][] bucket = new int[10][arr.length];

  //为了记录每个桶中，实际存放了多少个数据，定义一个一维数组来记录各个桶的每次放入的数据个数
  //比如：bucketElementCounts[0] , 记录的就是  bucket[0] 桶的放入数据个数
  int[] bucketElementCounts = new int[10];

  for(int i=0,n=1;i<maxLength;i++,n*=10){
  //(针对每个元素的对应位进行排序处理)， 第一次是个位，第二次是十位，第三次是百位..
  for(int j=0;j<arr.length;j++){
  //取出每个元素对应位置上的值
  int digitOfElement = arr[j]/n%10;
  //放入到对应的桶中
  bucket[digitOfElement][bucketElementCounts[digitOfElement]]=arr[j];
  bucketElementCounts[digitOfElement]++;

  }
  //按照这个桶的顺序（一维数组的下标依次取出数据，放入原来数组中）
  int index =0;
  for(int k=0;k<bucketElementCounts.length;k++){
  if(bucketElementCounts[k]!=0){
  //循环该桶即第k个桶（即第k个一维数组），放入
  for(int l =0;l<bucketElementCounts[k];l++){
  //取出元素放入到arr
  arr[index++] = bucket[k][l];
  }
  }
  //第i+1轮处理后，需要将每个bucketElementCounts[k]=0
  bucketElementCounts[k] = 0;
  }
  }
  }