Three ways to implement quick sorting in PHP_PHP tutorial
This article mainly introduces three ways to implement quick sorting in PHP. Each of the three methods has its own advantages and disadvantages. Friends in need can refer to it
Written three PHP quick ranking examples. The first one is inefficient but the simplest and easiest to understand. The second one is the one-way one-time traversal method to find the median value provided in the introduction to the algorithm. The third one is two-way traversal to find the middle value. Value of the classic quicksort algorithm. The implementation and comparison of the three groups of algorithms are as follows:
Method 1: This method is more intuitive, but at the cost of losing a lot of space and using the less efficient merge function. The least efficient of the three methods. In the worst case, the algorithm degenerates to (O(n*n))
The code is as follows:
function quick_sort($array) {
if(count($array) <= 1) return $array;
$key = $array[0];
$rightArray = array();
$leftArray = array();
for($i = 1; $i < count($array); $i++) {
if($array[$i] >= $key) {
$rightArray[] = $array[$i];
} else {
$leftArray[] = $array[$i];
}
}
$leftArray = quick_sort($leftArray);
$rightArray = quick_sort($rightArray);
return array_merge($leftArray, array($key), $rightArray);
}
Method 2: This algorithm comes from the Introduction to Algorithms and is called the Nico Lomuto method (details are available on Google if you are interested). It uses the most classic one-way traversal to find the median value.
But this algorithm is O(n*n) in the worst case (for example, an array with the same value requires n-1 divisions, and each division requires O(n) time to remove an element).
The code is as follows:
function quick_sort(&$array, $start, $end) {
if ($start >= $end) return;
$mid = $start;
for ($i = $start + 1; $i <= $end; $i++) {
if ($array[$i] < $array[$mid]) {
$mid++;
$tmp = $array[$i];
$array[$i] = $array[$mid];
$array[$mid] = $tmp;
}
}
$tmp = $array[$start];
$array[$start] = $array[$mid];
$array[$mid] = $tmp;
quick_sort($array, $start, $mid - 1);
quick_sort($array, $mid + 1, $end);
}
Method 3: This method is basically a common textbook writing method. First, traverse from left to right and skip elements smaller than the middle element. At the same time, traverse from right to left and skip elements that are larger than the middle element. Then
If there is no intersection and exchange of values on both sides, continue looping until the middle point is found. Note that this method still exchanges when processing the same elements, so that in the worst case there is O(nlogn)
Efficiency. But in the following function, if $array[$right] > $key is changed to $array[$right] >=$key or $array[$left] < $key is changed to $array[$left ] <= $key is the worst
The situation will not only degrade to O(n*n). In addition to the consumption of each comparison, it will also generate the additional overhead of n interactions. There are two other test points for this question, for students who memorize by rote:
1: Whether the two whiles in the middle are interchangeable. Of course, it cannot be interchanged, because the fast disk requires an extra space to save the initial left value. In this way, when the left and right are interchanged, the right side must be used to overwrite the saved value
is the lvalue of the median, otherwise problems will occur. See this sentence $array[$left] = $array[$right];
2: $array[$right] = $key; The meaning of this statement can be omitted. This sentence cannot be omitted. You can consider an extreme case such as the ordering of two values (5,2), and you will understand it step by step.
The code is as follows:
function quick_sort_swap(&$array, $start, $end) {
if($end <= $start) return;
$key = $array[$start];
$left = $start;
$right = $end;
while($left < $right) {
while($left < $right && $array[$right] > $key)
$right--;
$array[$left] = $array[$right];
while($left < $right && $array[$left] < $key)
$left++;
$array[$right] = $array[$left];
}
$array[$right] = $key;
quick_sort_swap(&$array, $start, $right - 1);
quick_sort_swap(&$array, $right+1, $end);
}

Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

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

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics

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

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

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

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,

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

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

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 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.
