基数排序(radix Sort)

10大排序算法.png

基数排序非常适合用于整数排序，尤其是正整数

• 复杂度：
  最好、最坏、平均时间复杂度：O(d*(n+k)), d是最大值得位数，k是进制
  空间复杂度：O(n+k) , k是进制
  稳定性：稳定排序

• 执行流程：
  依次对个位数、十位数、百位数、千位数...进行排序(从低位到高位)

基数排序.png

private void sort(){ 
  
    //找出最大值
    int max = list[0];
   for(int i = 1; i < list.length;i++) {
       if(list[i] > max ) {  
          max = list[I]; 
       }
   }

      /**
      x /1% 10得到个位数  x/10%10得到十位数  x/100%10得到百位数
     个位数： 593 / 1 % 10 = 3
     十位数： 593 / 10 % 10 = 9
     百位数:    593 / 100 % 10 = 5
      */
   //排序
    for(int divider = 1; divider <= max; divider *=10) {
        countingSort(divider);
    }

}

   //对个 、十、 百、 千...位进行排序, 统计0 ~ 9出现的次数
   private void countingSort(int divider) {

   //1.开辟内存空间，存储次数
   int counts = new int[10];
   //2.1统计每个整数出现的次数
   for(int i = 0;i < list.length;i++)  {
      int idx =  list[i]/divider%10;
      counts[idx]++;
   }

  //2.2累加次数，每遍历一位就拿前一位的次数加当前元素出现次数
  for(int i = 1;i < counts.length;i++) {
      counts[i]  =   counts[i] + counts[i-1];
  }
  
//3.从后往前遍历元素，将它放在有序序列中的合适位置
 //技巧：从后往前遍历可以保证稳定性，相同数字相对位置不变
int[] output = new int[list.length];
for(int i = array.length - 1; i >=0;i--) {
     //array[i] : list数组i位置的元素在counts数组中的索引
     //counts[list[i]]: 索引位存储的次数
     //--(counts[list[i]]): 索引位存储的次数减1后再把得到的值存起来, 这个减1后得到的值就是 list数组i位置的元素将来在有序序列中的索引
      int idx = --(counts[list[i]/divider%10]);
     // 将元素放在有序序列中的合适位置
      output[idx] = list[I];
}

//4.将排好序的数组覆盖掉array
for(int i = 0;i < list.length;i++) {
    list[i] = output[I];
}

基数排序-另一种思路

执行流程：

1. 创建一个二维数组list，list中添加10个数组(因为基数范围是[0,9])，这10个数组的长度最好是原数组的长度
   2.遍历原数组获取其中元素的个、十、百、千位数值，按顺序([0,9])存储到list中
   3.遍历list获取每个数组中的元素放进原数组中就得到了有序序列

基数排序-另一种思路.png

时间复杂度：O(dn)
空间复杂度：O(kn+k)
d: 最大值的位数
k: 进制

private void sort() {
   //1.寻找最大值
   int max = list[0];
   for(int i = 1;i < list.length;i++) {
        if(array[I] > max) {
             max = list[I];
        }
   }
    
   //2.排序
   //桶数组
    int[][] buckets = new int[10][list.length];
    //每个桶元素的数量
    int bucketSizes = new int[buckets.length];
   for(int divider = 1;divider <= max; divider *10) {

        //2.1.将数组元素放到对应的桶里面去
       for(int i = 0;i < list.length;i++) {
         int no = list[i]/divider%10;
         buckets[no][bucketSizes[no]++] = list[i];
      }
 
     //2.2.从桶里面取出元素放进原数组
      int idx = 0;
     for(int i = 0;i < buckets.length;i++) {
         for(int j = 0;j < bucketSizes[I];j++) {
              list[idx++] =  buckets[i][j];
          }
          bucketSizes[i] = 0;
     }

  }
 
}