数据结构与算法-排序(十)桶排序(Bucket Sort)

语言: CN / TW / HK

摘要

桶排序和基数排序类似,相当于基数排序的另外一种逻辑。它是将取值范围当做创建桶的数量,桶的长度就是序列的大小。通过处理比较元素的数值,把元素放在桶的特定位置,然后遍历桶,就可以得到有序的序列。

逻辑

创建一定数量的桶(数组或者链表)。制定规则将序列中的元素均匀地分布在不同的桶中。然后对每个桶内排序,最后合并非空的桶。

流程

  1. 创建一定数量的桶
  2. 元素均匀分布在桶中(根据规则来看)
  3. 桶内排序
  4. 合并非空的桶

下面还用无序的整数元素序列,将这个序列给排序有序。

实现

获取序列中的最大值,这里按照最大值有多少位,来确定外部循环多少次后得到有序的序列,也就是每一位都会循环遍历比较。

// 获取最大值
	int max = array[0];
	for (int i = 1; i < array.length; i++) {
		if (max < array[i]) {
			max = array[i];
		}
	}

桶排序实现方法

每一个整数的进制位是 0 到 9 这 10 个数,所以这里就创建10个桶,分别对应这10个数,每个桶的高度就是序列的长度。

下一步就是创建记录每个桶大小的数组,来放置元素个数,在取出桶中的元素时,就可以确定遍历的长度,减少遍历无用的空间。同时这是元素在桶中的索引位置。

// 桶数组
	int[][] buckets = new int[10][array.length];
	// 每个桶中的元素数量
	int[] bucketSizes = new int[buckets.length];

接下来,就是根据最大值的进位数量,从个位进位开始对元素进行处理排序, bucketSizes 记录对应位置数值的数量,并提供给 buckets 数组在桶中的元素索引位置。

这里比较难理解一些,比如有 23和43 这两个数据,若从个位开始处理,因为个位都是 3,那么放在桶中的位置应该是 buckets[3][0]。如果是这样,23 会被后来的 43 覆盖。那么就用一个记录 3 数值出现次数的数组,即 bucketSizes[3],当存放 23 之后,bucketSizes[3] 加 1, 那么后面放 43 的时候,它的位置就是 buckets[3][1], 避免了覆盖。

当所有元素放置完成之后,就遍历 buckets 桶,依次取出元素,在遍历桶循环时,每个桶遍历的最大值就是 bucketSizes 中的数量,就不需要把桶的长度全部遍历完,减少遍历次数。

for (int divider = 1; divider <= max; divider *= 10) {
		for (int i = 0; i < array.length; i++) {
			int no = array[i] / divider % 10;
			buckets[no][bucketSizes[no] ++] = array[i];
		}
	}
		
	int index = 0;
	for (int i = 0; i < buckets.length; i++) {
		for (int j = 0; j < bucketSizes[i]; j++) {
			array[index ++] = buckets[i][j];
		}
		bucketSizes[i] = 0;
	}

时间和空间复杂度

  • 时间复杂度:O(n + n * logn - n * logm)
  • 空间复杂度:O(n+m)
  • 属于稳定排序

m 是桶的数量