当前位置:Gxlcms > PHP教程 > PHP算法之桶排序

PHP算法之桶排序

时间:2021-07-01 10:21:17 帮助过:4人阅读


摘要:桶排序可以说得上是最简单的排序算法了,但是它的使用范围非常狭窄,不过不可否认的是在其适用范围内,它的性能要比快速排序还要快上很多倍。

桶排序可以说得上是最简单的排序算法了,但是它的使用范围非常狭窄,不过不可否认的是在其适用范围内,它的性能要比快速排序还要快上很多倍。


没错,桶排序也是一种非比较型排序算法,这也正是它能够超越快速排序的原因。

桶排序主要有以下缺陷:

  1. 参与排序的数组存放的必须是整数。

  2. 数组中的最大数和最小数保持在一个合理的间距内。

  3. 需要额外的内存空间。

下面将通过一个例子讲解桶排序的核心思想:

假如说我们需要对全国高考语文成绩进行排序,由于总分只有 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,

人气教程排行