桶排序
桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效,我们需要做到这两点:
  1. 1.
    在额外空间充足的情况下,尽量增大桶的数量
  2. 2.
    使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
同时,对于桶中元素的排序,选择何种比较排序算法对于性能的影响至关重要。

1. 什么时候最快

当输入的数据可以均匀的分配到每一个桶中。

2. 什么时候最慢

当输入的数据被分配到了同一个桶中。

3. JavaScript 代码实现

1
function bucketSort(arr, bucketSize) {
2
if (arr.length === 0) {
3
return arr;
4
}
5
6
var i;
7
var minValue = arr[0];
8
var maxValue = arr[0];
9
for (i = 1; i < arr.length; i++) {
10
if (arr[i] < minValue) {
11
minValue = arr[i]; // 输入数据的最小值
12
} else if (arr[i] > maxValue) {
13
maxValue = arr[i]; // 输入数据的最大值
14
}
15
}
16
17
//桶的初始化
18
var DEFAULT_BUCKET_SIZE = 5; // 设置桶的默认数量为5
19
bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
20
var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
21
var buckets = new Array(bucketCount);
22
for (i = 0; i < buckets.length; i++) {
23
buckets[i] = [];
24
}
25
26
//利用映射函数将数据分配到各个桶中
27
for (i = 0; i < arr.length; i++) {
28
buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
29
}
30
31
arr.length = 0;
32
for (i = 0; i < buckets.length; i++) {
33
insertionSort(buckets[i]); // 对每个桶进行排序,这里使用了插入排序
34
for (var j = 0; j < buckets[i].length; j++) {
35
arr.push(buckets[i][j]);
36
}
37
}
38
39
return arr;
40
}
Copied!

4. Java 代码实现

1
public class BucketSort implements IArraySort {
2
3
private static final InsertSort insertSort = new InsertSort();
4
5
@Override
6
public int[] sort(int[] sourceArray) throws Exception {
7
// 对 arr 进行拷贝,不改变参数内容
8
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
9
10
return bucketSort(arr, 5);
11
}
12
13
private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
14
if (arr.length == 0) {
15
return arr;
16
}
17
18
int minValue = arr[0];
19
int maxValue = arr[0];
20
for (int value : arr) {
21
if (value < minValue) {
22
minValue = value;
23
} else if (value > maxValue) {
24
maxValue = value;
25
}
26
}
27
28
int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
29
int[][] buckets = new int[bucketCount][0];
30
31
// 利用映射函数将数据分配到各个桶中
32
for (int i = 0; i < arr.length; i++) {
33
int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
34
buckets[index] = arrAppend(buckets[index], arr[i]);
35
}
36
37
int arrIndex = 0;
38
for (int[] bucket : buckets) {
39
if (bucket.length <= 0) {
40
continue;
41
}
42
// 对每个桶进行排序,这里使用了插入排序
43
bucket = insertSort.sort(bucket);
44
for (int value : bucket) {
45
arr[arrIndex++] = value;
46
}
47
}
48
49
return arr;
50
}
51
52
/**
53
* 自动扩容,并保存数据
54
*
55
* @param arr
56
* @param value
57
*/
58
private int[] arrAppend(int[] arr, int value) {
59
arr = Arrays.copyOf(arr, arr.length + 1);
60
arr[arr.length - 1] = value;
61
return arr;
62
}
63
64
}
Copied!

5. PHP 代码实现

1
function bucketSort($arr, $bucketSize = 5)
2
{
3
if (count($arr) === 0) {
4
return $arr;
5
}
6
7
$minValue = $arr[0];
8
$maxValue = $arr[0];
9
for ($i = 1; $i < count($arr); $i++) {
10
if ($arr[$i] < $minValue) {
11
$minValue = $arr[$i];
12
} else if ($arr[$i] > $maxValue) {
13
$maxValue = $arr[$i];
14
}
15
}
16
17
$bucketCount = floor(($maxValue - $minValue) / $bucketSize) + 1;
18
$buckets = array();
19
for ($i = 0; $i < count($buckets); $i++) {
20
$buckets[$i] = [];
21
}
22
23
for ($i = 0; $i < count($arr); $i++) {
24
$buckets[floor(($arr[$i] - $minValue) / $bucketSize)][] = $arr[$i];
25
}
26
27
$arr = array();
28
for ($i = 0; $i < count($buckets); $i++) {
29
$bucketTmp = $buckets[$i];
30
sort($bucketTmp);
31
for ($j = 0; $j < count($bucketTmp); $j++) {
32
$arr[] = $bucketTmp[$j];
33
}
34
}
35
36
return $arr;
37
}
Copied!
Last modified 2yr ago