桶排序

1.思路

1. 创建一定数量的桶（比如用数组、链表作为桶）
2. 按照一定的规则（不同类型的数据，规则不同），将序列中的元素均匀分配到对应的桶
3. 分别对每个桶进行单独排序
4. 将所有非空桶的元素合并成有序序列

1.1例子

原数组为[0.34,0.47,0.29,0.84,0.45,0.38,0.35,0.76]

这里是小数，所以元素在通用的索引可以：元素值*元素数量

• 创建8个桶如下，每个桶都是数组

桶号	内容
0
1
2	[0.34,0.29,0.35]
3	[0.47,0.45,0.38]
4
5
6	[0.84,0.76]
7

• 对每个桶单独进行排序
  则变成

桶号	内容
0
1
2	[0.29,0.34,0.35]
3	[0.38,0.45,0.47]
4
5
6	[0.76,0.84]
7

• 将所有非空桶的元素合并成有序序列
  则变成
  [0.29,0.34,0.35,0.38,0.45,0.47,0.76,0.84]

1.2代码

class BucketSourt extends Sort<num>  {
  @override
  sort() {
    //创建桶
    List<List> buckets = List(list.length);
    for (var i = 0; i < list.length; i++) {
      int bucketIndex = (list[i]*list.length).floor();
      List<num> bucket = buckets[bucketIndex];
      if (bucket == null) {
        bucket = List();
        buckets[bucketIndex] = bucket;
      }
      bucket.add(list[i]);
    }
    //对每个桶进行排序
    int index = 0;
    for (var i = 0; i < buckets.length; i++) {
      if (buckets[i]==null) continue;
      buckets[i].sort();
      for (var item in buckets[i]) {
        list[index++] = item;
      }
    }
  }
  
}

实验

main(List<String> args) {
 BucketSourt bucketSourt =  BucketSourt();
 bucketSourt.list = [0.34,0.47,0.29,0.84,0.45,0.38,0.35,0.76];
 bucketSourt.sort();//这里复杂度 nlogn
 print(bucketSourt.list );
}

结果

[0.29, 0.34, 0.35, 0.38, 0.45, 0.47, 0.76, 0.84]

1.3 复杂度

空间复杂度：，m 是桶的数量
时间复杂度：

=
=
约等于 ,k为

题外

跟哈希表的思想有点像