數據結構與演算法-排序（十）桶排序（Bucket Sort）

2021 年 8 月 26 日
筆記
數據結構與演算法

摘要

桶排序和基數排序類似，相當於基數排序的另外一種邏輯。它是將取值範圍當做創建桶的數量，桶的長度就是序列的大小。通過處理比較元素的數值，把元素放在桶的特定位置，然後遍歷桶，就可以得到有序的序列。

邏輯

創建一定數量的桶（數組或者鏈表）。制定規則將序列中的元素均勻地分布在不同的桶中。然後對每個桶內排序，最後合併非空的桶。

流程

創建一定數量的桶
元素均勻分布在桶中（根據規則來看）
桶內排序
合併非空的桶

下面還用無序的整數元素序列，將這個序列給排序有序。

實現

獲取序列中的最大值，這裡按照最大值有多少位，來確定外部循環多少次後得到有序的序列，也就是每一位都會循環遍歷比較。

    // 獲取最大值
	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 是桶的數量

Tags: 數據結構與演算法