Table of Contents
桶排序可以说得上是最简单的排序算法了,但是它的使用范围非常狭窄,不过不可否认的是在其适用范围内,它的性能要比快速排序还要快上很多倍。" >桶排序可以说得上是最简单的排序算法了,但是它的使用范围非常狭窄,不过不可否认的是在其适用范围内,它的性能要比快速排序还要快上很多倍。
实现
改进
总结
Home Backend Development PHP Tutorial PHP算法之桶排序

PHP算法之桶排序

Aug 16, 2017 am 10:11 AM
php sort algorithm


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

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


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

桶排序主要有以下缺陷:

  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,

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)),但是适用范围很广。非比较型算法虽然使用范围很有限,但是其速度非常之快。所以在选择排序算法时,根据程序的数值类型以及范围,首先要考虑是否能够使用非比较型算法,如果不可以再选用比较型算法,比如快速排序。

The above is the detailed content of PHP算法之桶排序. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

PHP 8.4 Installation and Upgrade guide for Ubuntu and Debian PHP 8.4 Installation and Upgrade guide for Ubuntu and Debian Dec 24, 2024 pm 04:42 PM

PHP 8.4 brings several new features, security improvements, and performance improvements with healthy amounts of feature deprecations and removals. This guide explains how to install PHP 8.4 or upgrade to PHP 8.4 on Ubuntu, Debian, or their derivati

7 PHP Functions I Regret I Didn't Know Before 7 PHP Functions I Regret I Didn't Know Before Nov 13, 2024 am 09:42 AM

If you are an experienced PHP developer, you might have the feeling that you’ve been there and done that already.You have developed a significant number of applications, debugged millions of lines of code, and tweaked a bunch of scripts to achieve op

How To Set Up Visual Studio Code (VS Code) for PHP Development How To Set Up Visual Studio Code (VS Code) for PHP Development Dec 20, 2024 am 11:31 AM

Visual Studio Code, also known as VS Code, is a free source code editor — or integrated development environment (IDE) — available for all major operating systems. With a large collection of extensions for many programming languages, VS Code can be c

Explain JSON Web Tokens (JWT) and their use case in PHP APIs. Explain JSON Web Tokens (JWT) and their use case in PHP APIs. Apr 05, 2025 am 12:04 AM

JWT is an open standard based on JSON, used to securely transmit information between parties, mainly for identity authentication and information exchange. 1. JWT consists of three parts: Header, Payload and Signature. 2. The working principle of JWT includes three steps: generating JWT, verifying JWT and parsing Payload. 3. When using JWT for authentication in PHP, JWT can be generated and verified, and user role and permission information can be included in advanced usage. 4. Common errors include signature verification failure, token expiration, and payload oversized. Debugging skills include using debugging tools and logging. 5. Performance optimization and best practices include using appropriate signature algorithms, setting validity periods reasonably,

PHP Program to Count Vowels in a String PHP Program to Count Vowels in a String Feb 07, 2025 pm 12:12 PM

A string is a sequence of characters, including letters, numbers, and symbols. This tutorial will learn how to calculate the number of vowels in a given string in PHP using different methods. The vowels in English are a, e, i, o, u, and they can be uppercase or lowercase. What is a vowel? Vowels are alphabetic characters that represent a specific pronunciation. There are five vowels in English, including uppercase and lowercase: a, e, i, o, u Example 1 Input: String = "Tutorialspoint" Output: 6 explain The vowels in the string "Tutorialspoint" are u, o, i, a, o, i. There are 6 yuan in total

How do you parse and process HTML/XML in PHP? How do you parse and process HTML/XML in PHP? Feb 07, 2025 am 11:57 AM

This tutorial demonstrates how to efficiently process XML documents using PHP. XML (eXtensible Markup Language) is a versatile text-based markup language designed for both human readability and machine parsing. It's commonly used for data storage an

Explain late static binding in PHP (static::). Explain late static binding in PHP (static::). Apr 03, 2025 am 12:04 AM

Static binding (static::) implements late static binding (LSB) in PHP, allowing calling classes to be referenced in static contexts rather than defining classes. 1) The parsing process is performed at runtime, 2) Look up the call class in the inheritance relationship, 3) It may bring performance overhead.

What are PHP magic methods (__construct, __destruct, __call, __get, __set, etc.) and provide use cases? What are PHP magic methods (__construct, __destruct, __call, __get, __set, etc.) and provide use cases? Apr 03, 2025 am 12:03 AM

What are the magic methods of PHP? PHP's magic methods include: 1.\_\_construct, used to initialize objects; 2.\_\_destruct, used to clean up resources; 3.\_\_call, handle non-existent method calls; 4.\_\_get, implement dynamic attribute access; 5.\_\_set, implement dynamic attribute settings. These methods are automatically called in certain situations, improving code flexibility and efficiency.

See all articles