基数排序(Redix Sort)

[toc]

基数排序非常适合用于整数排序（尤其是非负整数）

1.思路

依次对个位数、十位数、百位数、千位数、万位数...进行排序（从低位到高位）
例子
原数组
[129,69,593,23,6,89,54,8]

对个位数排序后为
[593,23,54,126,6,8,69,89]
对十位数排序后为
[6,8,23,126,54,69,89,593]
对百位数排序后为
[6,8,23,54,69,89,126,583]达到有序

2.代码实现

2.1基于计数排序实现

class RedixSourt extends Sort<num> {
  @override
  sort() {
     //找到最大值
   int max = list[0];
   for (var i = 1; i < list.length; i++) {
     if (list[i]>max) {
       max = list[i];
     }
   }

      // 个位数: array[i] / 1 % 10 = 3
        // 十位数：array[i] / 10 % 10 = 9
        // 百位数：array[i] / 100 % 10 = 5
        // 千位数：array[i] / 1000 % 10 = ...
   for (var divider = 1; divider <= max; divider *=10) {
     _countsort(divider);
   }

  }

  ///
  /// Author: liyanjun
  /// description: 每一轮采取计数排序
  ///
  _countsort(int divider) {
    //找到最大值和最小值
    // int max = list[0];
    // int min = max;
    // for (var i = 1; i < list.length; i++) {
    //   if (list[i] > max) {
    //     max = list[i];
    //   }
    //   if (list[i] < min) {
    //     min = list[i];
    //   }
    // }
    //因为0~9 位数不多，可以认为就是0，9
    //开辟控件，存储次数
    List counts = List.filled(10, 0);
    //统计每个整数出现的次数 list[i]的基数
    for (var i = 0; i < list.length; i++) {
      int no = list[i]~/divider % 10;
      counts[no]++;
    }
    //累加次数
    for (var i = 1; i < counts.length; i++) {
      counts[i]  += counts[i-1];
    }
    //倒序遍历数组，将它放到有序数组的合适位置
    //得到元素k在有序数组的索引
    List<int> newList = List(list.length);
    for (var i = list.length - 1; i >= 0; i--) {
      int no = list[i]~/divider % 10;
      int k = no;//这里要统计基数的值
      newList[--counts[k]] = list[i];
    }
    //将有序数组赋值给list
    list = newList;
  }

}

2.1.1复杂度分析

• 最好、最坏、平均时间复杂度： ，d 是最大值的位数，k 是进制,这里k是10。属于稳定排序
• 空间复杂度：O(n + k)，k 是进制

2.2 思路2

1.每一轮放进一个二维数组 [10][list.length]
2.比较基数位置的数字是多少，就放在哪一而数组

过程如图
如图所示

image.png

代码

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

    // 个位数: array[i] / 1 % 10 = 3
    // 十位数：array[i] / 10 % 10 = 9
    // 百位数：array[i] / 100 % 10 = 5
    // 千位数：array[i] / 1000 % 10 = ...

    /// 1.每一轮放进一个二维数组 [10][list.length]
    /// 2.比较基数位置的数字是多少，就放在哪一而数组
    //桶数组
    List<List<int>> buckets = List.generate(10,(index) =>List.generate(list.length, (index) => 0));
    //每个桶的元素数量，方便最后取值
    List<int> bucketsSize = List.filled(buckets.length, 0);
    for (var divider = 1; divider <= max; divider *= 10) {
      for (var i = 0; i < list.length; i++) {
        int no = list[i] ~/ divider % 10;
        buckets[no][bucketsSize[no]++] = list[i];
      }
      int index = 0;
      for (var i = 0; i < buckets.length; i++) {
        for (var j = 0; j < bucketsSize[i]; j++) {
          list[index++] = buckets[i][j];
        }
        bucketsSize[i] = 0;
      }
    }
  }

2.2.1复杂度分析

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