摘要：桶排序可以说得上是最简单的排序算法了，但是它的使用范围非常狭窄，不过不可否认的是在其适用范围内，它的性能要比快速排序还要快上很多倍。
没错，桶排序也是一种非比较型排序算法，这也正是它能够超越快速排序的原因。
桶排序主要有以下缺陷：
参与排序的数组存放的必须是整数。
数组中的最大数和最小数保持在一个合理的间距内。
需要额外的内存空间。
下面将通过一个例子讲解桶排序的核心思想：
假如说我们需要对全国高考语文成绩进行排序，由于总分只有 150 分，而且所有的值都在 [0, 150] 之间，所以我们可以申请一个大小为 151 的辅助数组。
|
1 2 3 4 5 |
var countArray = []; for(var i = 0; i <= 150; i++) { countArray[i] = 0; }
|
首先我们将数组的值都置为 0。然后我们以各考生的成绩为下标递增辅助数组的值。比如说一个考生成绩为 90，那么我们就让 countArray[90]++，这样一直运算下去，直到所有的考生成绩都被遍历完，我们就可以统计出来每个分数有多少考生，然后再将辅助数组中的值复制回原数组，整个数组自然而然就有序了！
大概了解了桶排序的思想，下面就来实现一下，假说某年参加高考的学生共有 500 万人，我们对其语文成绩进行排序。
下面是排序代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | function countSort(array, k) { var length = array.length, countArray = [], i;
for (i = 0; i < k; i++) { countArray[i] = 0; }
for (i = 0; i < length; i++) { countArray[array[i]]++; }
var z = 0; for (i = 0; i < k; i++) { while (countArray[i]-- > 0) { array[z++] = i; } } }
|
下面是测试代码：
|
1 2 3 4 5 6 7 8 9 10 11 |
var array = [];
for(var i = 0; i < 5000000; i++) { array.push(Math.floor(Math.random() * 151)); }
console.time(); countSort(array,151); console.timeEnd(); console.log(array);
|
以上代码在我电脑上的运行时间在 23ms 左右，可见，桶排序排序 500万数据的速度是如此之快，而我用快速排序对同一个数组进行排序，花了 320 ms 左右。
所以，如果在合适的时机选择计数排序，将节省很多时间。
看了以上代码也许你发现了，上述代码如果排序一个数值在 [10000, 10200] 范围内的数组的话，将申请大量的内存，为了节省内存，我们不得不改进这个算法，让其适应指定范围内排序。
很简单的，我们可以在方法中设置一个 low 和 max 参数，就可以灵活自如了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | function countSort(array, low, max) { var length = array.length, countArray = [], i, k = max - low + 1;
for (i = 0; i < k; i++) { countArray[i] = 0; }
for (i = 0; i < length; i++) { countArray[array[i] - low]++; }
var z = 0; for (i = 0; i < k; i++) { while (countArray[i]-- > 0) { array[z++] = i + low; } }
console.log(countArray.length); }
|
最近一直在学习排序算法，发现比较型算法虽然速度比较慢一些(比较型算法的下限是 O(NlogN))，但是适用范围很广。非比较型算法虽然使用范围很有限，但是其速度非常之快。所以在选择排序算法时，根据程序的数值类型以及范围，首先要考虑是否能够使用非比较型算法，如果不可以再选用比较型算法，比如快速排序。
Atas ialah kandungan terperinci PHP算法之桶排序. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!
Algoritma penggantian halaman
Bagaimana untuk membuka fail php
Apakah kaedah pengisihan?
Bagaimana untuk mengalih keluar beberapa elemen pertama tatasusunan dalam php
Apa yang perlu dilakukan jika penyahserialisasian php gagal
Bagaimana untuk menyambungkan php ke pangkalan data mssql
Bagaimana untuk menyambung php ke pangkalan data mssql
Bagaimana untuk memuat naik html
![[Web front-end] Permulaan pantas Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
