[排序算法总结三] 计数排序和桶排序

vlambda
2020-04-19

[排序算法总结三] 计数排序和桶排序

快排、归并、插入在相应的条件下已经很快了。但是随着计算机存储设备越来越充足，计算机存储能力也大大提高。这样不需要考虑计算机内存情况下。计数排序和桶排序进一步提高排序速度，当然也是在牺牲空间复杂度的情况下。

计数排序

计数排序，不考虑存储空间的限制，用一个很大的数组（上界是待排序数据最大值）来存放数据中每个数出现的次数，然后按照从小到大输出即可，计数排序是一种不用比较的排序思想。适合数据量大而且数据分布范围较小的情况。

实现代码：

private void countSort(int[] array , int n) { int[] data = new int[1000000]; for (int i = 0 ; i < n ; i ++) { data[array[i]]++; }
 int index = 0; for (int i = 0 ; i < 1000000 ; i ++) { int num = data[i]; if (num > 0) { while (num > 0) { array[index++] = i; num--; } } } }

计数排序时间复杂度是：O(k)，这个k值就是待排序数据最大值，一般取那个值所在量级的一个整数，是一种非比较的排序算法。也是不稳定的。

桶排序

桶排序利用计数排序思想发展而来，把数据以分布范围为划分依据放进尽可能多的桶中，桶与桶之间总体是递增的，在整个数据分布范围之内，每个桶使用快排或者其他排序进行排序。而关键就是这个桶的构造，是按照数据分布范围来构造桶。比如0-100范围内均匀分布50个数据，就构造10个桶，那么0-10的数字放进第一个桶，11-20数据放入第二个桶....91-100之内数据放入第20个桶。最后把数据全取出来即排好序了。

桶排序要求比较高：桶尽可能的多，内存要求充分，数据都是均匀分布在几个桶中，那么得知道数据的两端上界和下界，每个桶平均有n/m数据 , 这样时间复杂度O(n + n/m * log(n/m))，当桶尽可能多时，桶个数m趋近于n时，接近于O(n)，最坏情况下，数据全部分布在一个桶中，退化为O(nlogn)。

下面代码是我自己构造桶排序的一个类：

public class BuckedSort {
 public HashMap<Integer , ArrayList<Integer>> bucked; public int buckedSize;
 public BuckedSort(int[] array , int n , int buckedSize) {
 this.bucked = new HashMap<>(buckedSize); this.buckedSize = buckedSize; for (int i = 0 ; i < buckedSize ; i ++) bucked.put(i , new ArrayList<Integer>()); this.addBucked(array , n); this.sort(); }
 public BuckedSort() { }
 //把数据放入桶内 private void addBucked(int[] array , int n) { for (int i = 0 ; i < n ; i ++) { int index = array[i]/100; ArrayList<Integer> list = bucked.get(index); list.add(array[i]); bucked.put(index , list); } } //把每个桶中数组排序 private void sort() { for (int i = 0 ; i < buckedSize ; i ++) { ArrayList<Integer> list = bucked.get(i); Collections.sort(list); bucked.put(i , list); } }
 //排好序后，把桶中数据放入数组中 private void addArray(int[] array , int n) { int len = 0 , index = 0; for (int i = 0 ; i < buckedSize ; i ++) { ArrayList<Integer> list = bucked.get(i);
 len = list.size(); for (int j = 0 ; j < len ; j ++) { array[index++] = list.get(j); } //index += len; } }}

测试

使用100000个数据测试，测试结果如下：

 //桶排序 long startTimeBuckedSort = System.nanoTime(); buckedSort.addArray(buckedArray , n); //buckedSort.printArray(array , n); long endTimeBuckedSort = System.nanoTime(); double timeBuckedSort = (endTimeBuckedSort - startTimeBuckedSort)/1000000000.0;        System.out.println("桶排序时间是：" + timeBuckedSort + "s");
 //计数排序 long startTimeCountSort = System.nanoTime(); bS.countSort(countArray , n); //bS.printArray(array , n); long endTimeCountSort = System.nanoTime(); double timeCountSort = (endTimeCountSort - startTimeCountSort)/1000000000.0; System.out.println("计数排序时间是：" + timeCountSort + "s");