十大排序算法之桶排序

发表于 | 分类于
字数统计: 1.2k 字 | 阅读时长 ≈ 5 分钟

本文首发于个人博客

前言

本系列排序包括十大经典排序算法。

  • 使用的语言为：Java
  • 结构为：
    定义抽象类Sort里面实现了，交换，大小比较等方法。例如交换两个值，直接传入下标就可以了。其他的具体排序的类都继承抽象类Sort。这样我们就能专注于算法本身。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
	 * 返回值等于0，代表 array[i1] == array[i2]
	 * 返回值小于0，代表 array[i1] < array[i2]
	 * 返回值大于0，代表 array[i1] > array[i2]
	 */
	protected int cmp(int i1, int i2) {
		return array[i1].compareTo(array[i2]);
	}
	
	protected int cmp(T v1, T v2) {
		return v1.compareTo(v2);
	}
	
	protected void swap(int i1, int i2) {
		T tmp = array[i1];
		array[i1] = array[i2];
		array[i2] = tmp;
	}

  • 冒泡、选择、插入、归并、希尔、堆排序都是基于比较的排序

    • 平均时间复杂度最低O(nlogn)

  • 计数排序、桶排序、基数排序不是基于比较的排序

    • 使用空间换时间，某些时候，平均时间复杂度可以低于O(nlogn)

什么是桶排序

  • 桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（O（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。

桶排序可以看做计数排序的升级版

  • 它将要排的数据分到多个有序的桶里，每个桶里的数据再单独排序，再把每个桶的数据依次取出，即可完成排序

算法稳定性

  • 桶排序是一种稳定排序算法。

是否是原地算法

  • 何为原地算法？
    • 不依赖额外的资源或者依赖少数的额外资源，仅依靠输出来覆盖输入
    • 空间复杂度为 𝑂(1) 的都可以认为是原地算法
  • 非原地算法，称为 Not-in-place 或者 Out-of-place
  • 桶排序不属于 In-place

时空复杂度

  • 时间复杂度：O(n+k)，k为 n*logn-n*logm
  • 空间复杂度：O(n+m), m是桶的数量

代码

  • 桶排序内部的实现可以用计数排序的思路

  • 代码中创建了数组长度的四分之一个桶，具体数量根据自己需要，可以自己调整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
package YZ.Sort;

import java.util.ArrayList;
import java.util.Collections;

public class BucketSort extends Sort<Integer>{

	@Override
	protected void sort() {
		// TODO Auto-generated method stub
	    //最大最小值
	    int max = array[0];
	    int min = array[0];
	    int length = array.length/4;

	    for(int i=1; i<array.length; i++) {
	        if(array[i] > max) {
	            max = array[i];
	        } else if(array[i] < min) {
	            min = array[i];
	        }
	    }

	    //最大值和最小值的差
	    int diff = max - min;

	    //桶列表
	    ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
	    for(int i = 0; i < length; i++){
	        bucketList.add(new ArrayList<>());
	    }

	    //每个桶的存数区间
	    float section = (float) diff / (float) (length - 1) ;

	    //数据入桶
	    for(int i = 0; i < array.length; i++){
	        //当前数除以区间得出存放桶的位置 减1后得出桶的下标
	        int num = (int) (array[i] / section) - 1;
	        if(num < 0){
	            num = 0;
	        }
	        bucketList.get(num).add(array[i]);
	    }

	    //桶内排序
	    for(int i = 0; i < bucketList.size(); i++){
	        //jdk的排序速度当然信得过
	        Collections.sort(bucketList.get(i));
	    }

	    //写入原数组
	    int index = 0;
	    for(ArrayList<Integer> arrayList : bucketList){
	        for(int value : arrayList){
	        	array[index] = value;
	            index++;
	        }
	    }
	}

}

结果

数据源：

从1到80000之间随机生成20000个数据来测试

Integer[] array = Integers.random(20000, 1, 80000);

结果如下

【CountingSort】
稳定性：true 耗时：0.005s(5ms) 比较次数：0 交换次数：0

【QuickSort】
稳定性：false 耗时：0.009s(9ms) 比较次数：33.27万 交换次数：1.32万

【MergeSort】
稳定性：true 耗时：0.01s(10ms) 比较次数：26.10万 交换次数：0

【RadixSort】
稳定性：true 耗时：0.014s(14ms) 比较次数：0 交换次数：0

【ShellSort】
稳定性：false 耗时：0.016s(16ms) 比较次数：43.34万 交换次数：0

【HeapSort】
稳定性：false 耗时：0.023s(23ms) 比较次数：51.09万 交换次数：2.00万

【BucketSort】
稳定性：true 耗时：0.024s(24ms) 比较次数：0 交换次数：0

【SelectionSort】
稳定性：true 耗时：0.514s(514ms) 比较次数：2.00亿 交换次数：2.00万

【InsertionSort1】
稳定性：true 耗时：1.362s(1362ms) 比较次数：9935.15万 交换次数：9933.15万

【BubbleSort】
稳定性：true 耗时：2.529s(2529ms) 比较次数：2.00亿 交换次数：9933.15万

代码地址：