目录
- 一、简介
- 二、代码实现
- 三、应用场景
一、简介
| 算法 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 排序方式 | 稳定性 |
|---|---|---|---|---|---|---|
| 桶排序 | O(n+k ) | O(n+k) | O(n^2) | O(n+k) | Out-place | 稳定 |
稳定：如果A原本在B前面，而A=B，排序之后A仍然在B的前面；
不稳定：如果A原本在B的前面，而A=B，排序之后A可能会出现在B的后面；
时间复杂度： 描述一个算法执行所耗费的时间；
空间复杂度：描述一个算法执行所需内存的大小；
n：数据规模；
k：“桶”的个数；
In-place：占用常数内存，不占用额外内存；
Out-place：占用额外内存。
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，需要做到这两点：
在额外空间充足的情况下，尽量增大桶的数量
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
什么时候最快?
当输入的数据可以均匀的分配到每一个桶中。
什么时候最慢?
当输入的数据被分配到了同一个桶中。
算法步驟：
- 1.
确定桶的数量：根据输入数据的范围和数量确定需要多少个桶。
首先确定桶的个数。因为桶排序最好是将数据均匀地分散在各个桶中，那么桶的个数最好是应该根据数据的分散情况来确定。首先找出所有数据中的最大值mx和最小值mn；
根据mx和mn确定每个桶所装的数据的范围 size，有
size = (mx - mn) / n + 1，n为数据的个数，需要保证至少有一个桶，故而需要加个1；
求得了size即知道了每个桶所装数据的范围，还需要计算出所需的桶的个数cnt，有
cnt = (mx - mn) / size + 1，需要保证每个桶至少要能装1个数，故而需要加个1；- 2.
将数据分配到各个桶中：遍历输入数据，根据数据的值将数据分配到对应的桶中。
求得了size和cnt后，即可知第一个桶装的数据范围为 [mn, mn + size)，第二个桶为 [mn + size, mn + 2 * size)，…，以此类推，因此步骤2中需要再扫描一遍数组，将待排序的各个数放进对应的桶中。- 3.
对每个桶内的数据进行排序：对每个非空的桶内的数据进行排序，可以使用插入排序等方法。- 4.
合并各个桶的数据：按照桶的顺序将各个桶内的数据合并为最终的排序结果。
示意图
元素分布在桶中：
然后，元素在每个桶中排序：
二、代码实现
public void bucketSort(int[] nums) {
int n = nums.length;
int mn = nums[0], mx = nums[0];
// 找出数组中的最大最小值
for (int i = 1; i < n; i++) {
mn = Math.min(mn, nums[i]);
mx = Math.max(mx, nums[i]);
}
int size = (mx - mn) / n + 1; // 每个桶存储数的范围大小，使得数尽量均匀地分布在各个桶中，保证最少存储一个
int cnt = (mx - mn) / size + 1; // 桶的个数，保证桶的个数至少为1
List<Integer>[] buckets = new List[cnt]; // 声明cnt个桶
for (int i = 0; i < cnt; i++) {
buckets[i] = new ArrayList<>();//每一个桶都是一个集合
}
// 扫描一遍数组，将数放进桶里
for (int i = 0; i < n; i++) {
int idx = (nums[i] - mn) / size;
buckets[idx].add(nums[i]);
}
// 对各个桶中的数进行排序，这里用库函数快速排序
for (int i = 0; i < cnt; i++) {
buckets[i].sort(null); // 默认是按从小打到排序
}
// 依次将各个桶中的数据放入返回数组中
int index = 0;
for (int i = 0; i < cnt; i++) {
for (int j = 0; j < buckets[i].size(); j++) {
nums[index++] = buckets[i].get(j);
}
}
}
demo示例一下
public class BucketSort {
public static void bucketSort(int[] nums) {
int n = nums.length;
int mn = nums[0], mx = nums[0];
// 找出数组中的最大最小值
for (int i = 1; i < n; i++) {
mn = Math.min(mn, nums[i]);
mx = Math.max(mx, nums[i]);
}
int size = (mx - mn) / n + 1; // 每个桶存储数的范围大小，使得数尽量均匀地分布在各个桶中，保证最少存储一个
System.out.println("每个桶的储存数量大小 " + size);
int cnt = (mx - mn) / size + 1; // 桶的个数，保证桶的个数至少为1
System.out.println("桶的个数 " + cnt);
List<Integer>[] buckets = new List[cnt]; // 声明cnt个桶
for (int i = 0; i < cnt; i++) {
buckets[i] = new ArrayList<>();//每一个桶都是一个集合
}
for (int i = 0; i < n; i++) {
int number1 = mn + i * size;
int number2 = mn + (i + 1) * size;
System.out.println("第" + i + "个桶存理应存放数据范围 " + number1 + "----" + number2);
}
// 扫描一遍数组，将数放进桶里
for (int i = 0; i < n; i++) {
int idx = (nums[i] - mn) / size;
buckets[idx].add(nums[i]);
System.out.println("第" + idx + "个桶存放了" + nums[i]);
}
// 对各个桶中的数进行排序，这里用库函数快速排序
for (int i = 0; i < cnt; i++) {
buckets[i].sort(null); // 默认是按从小打到排序
}
// 依次将各个桶中的数据放入返回数组中
int index = 0;
for (int i = 0; i < cnt; i++) {
for (int j = 0; j < buckets[i].size(); j++) {
nums[index++] = buckets[i].get(j);
}
}
}
public static void bucketSort2(int[] nums) {
int n = nums.length;
int mn = nums[0], mx = nums[0];
// 找出数组中的最大最小值
for (int i = 1; i < n; i++) {
mn = Math.min(mn, nums[i]);
mx = Math.max(mx, nums[i]);
}
int size = (mx - mn) / n + 1; // 每个桶存储数的范围大小，使得数尽量均匀地分布在各个桶中，保证最少存储一个
int cnt = (mx - mn) / size + 1; // 桶的个数，保证桶的个数至少为1
List<Integer>[] buckets = new List[cnt]; // 声明cnt个桶
for (int i = 0; i < cnt; i++) {
buckets[i] = new ArrayList<>();
}
// 扫描一遍数组，将数放进桶里
for (int i = 0; i < n; i++) {
int idx = (nums[i] - mn) / size;
buckets[idx].add(nums[i]);
}
// 对各个桶中的数进行排序，这里用库函数快速排序
for (int i = 0; i < cnt; i++) {
buckets[i].sort(new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return b - a; // 从大到小排序
}
});
}
// 依次将各个桶中的数据放入返回数组中
int index = 0;
for (int i = cnt - 1; i >= 0; i--) {
for (int j = 0; j < buckets[i].size(); j++) {
nums[index++] = buckets[i].get(j);
}
}
}
public static void main(String[] args) {
int[] nums = {12, 11, 15, 50, 7, 65, 3, 99};
System.out.println("排序前 ：" + Arrays.toString(nums));
bucketSort(nums);
System.out.println("桶排序从小到大排序后 ：" + Arrays.toString(nums));
bucketSort2(nums);
System.out.println("桶排序从大到小排序后 ：" + Arrays.toString(nums));
}
}
三、应用场景
桶排序适用于数据量较大且分布较均匀的情况，可以在一定程度上提高排序的效率。
- 排序整数或浮点数： 桶排序适用于排序整数或浮点数，特别是在这些数的范围不是很大的情况下。通过将数分配到不同的桶中，可以在每个桶内使用其他排序算法（如插入排序、快速排序）来对桶内的数进行排序，最终将桶中的数合并得到有序序列。
- 均匀分布的数据： 如果输入数据是均匀分布的，即数据在不同的范围内基本均匀分布，那么桶排序的效果会很好。因为桶排序将数据分配到不同的桶中，可以保证数据在各个桶中基本均匀分布，从而减少排序的复杂度。
- 外部排序： 桶排序也适用于外部排序，即当数据量非常大，无法一次性加载到内存中进行排序时。在外部排序中，可以将数据分成若干块，每块数据可以加载到内存中进行桶排序，然后将排序后的数据写回磁盘，最终将所有块合并得到有序序列。
- 计数排序的扩展： 桶排序是计数排序的一种扩展，适用于更大范围的数据。当计数排序不适用于数据范围很大的情况时，桶排序可以更好地处理这种情况。
桶排序的关键点：
确定桶的数量和大小：在进行桶排序之前，需要确定桶的数量和大小。桶的数量可以根据待排序数据的范围来确定，而桶的大小可以根据数据的分布情况来选择。通常情况下，桶的数量可以取数据个数的平方根或者数据范围的大小。数据分配到桶中：一旦确定了桶的数量和大小，接下来需要将待排序数据分配到对应的桶中。这通常涉及到计算每个数据在哪个桶内，可以根据数据的大小和桶的范围来确定。对每个非空桶内的数据进行排序：在桶排序中，每个非空桶内的数据需要进行排序。这可以使用任意一种排序算法，如插入排序、快速排序等。在实际应用中，通常选择适合桶内数据规模的排序算法。合并各个桶的数据：最后一步是将各个桶内的数据按照顺序合并为最终的排序结果。这通常涉及遍历所有桶，按照桶的顺序将数据合并起来。处理边界情况：在实现桶排序时，需要考虑处理一些边界情况，例如空桶的情况、数据分布不均匀的情况等。这些情况可能会影响桶排序的性能和正确性。
参考链接：
十大经典排序算法（Java实现）
