How to implement quick sort

Quick Sorting Method

HTML5 Academy-Coder: In the previous issues of "Algorithm Journey", I shared with you the bubble sorting method and the selection sorting method. They both have a time complexity of O(n^ 2) "Slow" sorting. Today I would like to share with you the most widely used and fast sorting algorithm among various sorting algorithms - quick sort [average time complexity is O (n logn)].

Tips 1: The basic knowledge of "algorithm" and "sorting" has been explained in detail in the previous "Selection Sorting Method". You can click on the relevant article link at the end of the article to view it, and I will not repeat it here.

Tips 2: If there is no special instructions, the quick sort in this article is sorted from small to large.

Principle of quick sort

Quick sort is a partition and exchange sort. It adopts the divide-and-conquer strategy, which is usually called the divide-and-conquer method.

Divide and Conquer Method

Basic idea: Decompose the original problem into several smaller sub-problems but similar structures to the original problem. Solve these subproblems recursively, and then combine the results of these subproblems into the results of the original problem.

Basic Principle

Select any number from the sequence as the "base";

All numbers smaller than the "base" are moved to the left of the "base"; all Numbers greater than or equal to the "baseline" are moved to the right of the "baseline";

After this move is completed, the "baseline" will be in the middle of the two sequences and will no longer participate in subsequent sorting;

Repeat the above steps for the two subsequences to the left and right of the "baseline" until only one number remains in all subsequences.

Principle Illustration

The existing sequence is [8, 4, 7, 2, 0, 3, 1]. The following demonstrates how to sort it using the quick sort method.

Step breakdown to implement quick sort

Select "baseline" and separate it from the original array

Get the index of the baseline first value, and then use the splice array method to get the benchmark value.

Tips: In this example, the index value of the benchmark = parseInt (sequence length / 2)

Tips: The splice method will change the original array. For example, arr = [1, 2, 3]; The base index value is 1, the base value is 2, and the original array becomes arr = [1, 3];

Traverse the sequence and split the sequence

Compare the size with the "baseline" and split it into two subsequences

Numbers smaller than the "baseline" are stored in the leftArr array, and numbers greater than or equal to the "baseline" are stored in the rightArr array

#Tips: Of course, you can also store the number less than or equal to the "baseline" in leftArr, and the number greater than the "baseline" in rightArr

Since the sequence needs to be traversed, Compare each number with the "baseline", so you need to use the for statement to implement

recursive call, traverse the subsequence and combine the results of the subsequence

Define a function whose formal parameters are used to receive arrays

1. function quickSort(arr) { };

Implement recursive call traversal Sequence, use the concat array method to combine the results of the subsequence

Judge the length of the subsequence

During the recursive call, when the length of the subsequence is equal to 1 , then stop the recursive call and return the current array.

Complete code of quick sort method

Efficiency of quick sort method

Time complexity

Worst case scenario: The "baseline" selected each time is the smallest number/the largest number in the sequence. This situation is similar to the bubble sorting method (only one number [baseline number] can be determined at a time order), the time complexity is O(n^2)

Best case: the "baseline" selected each time is the middle number in the sequence (it is the median, not the position) middle), then the current sequence is divided into two subsequences of equal length each time. At this time, the first time there are two subsequences n/2 and n/2, the second time there are four subsequences n/4, n/4, n/4, n/4, and so on, n numbers It takes a total of logn times to complete the sorting (2^x=n, x=logn), and each time it has a complexity of n, the time complexity is O(n logn)

Space complexity

Worst case: n-1 recursive calls are required, and its space complexity is O(n)

Best case: logn recursive calls are required, and its space complexity is O(logn )

Stability of the algorithm

Quick sort is an unstable sorting algorithm

For example: the existing sequence is [1, 0, 1, 3], and the "baseline" number selection is After the first round of comparison, the second 1

becomes [0, 1, 1, 3], the left sequence is [0], and the right sequence is [1, 3] (1 in the right sequence It is the first one before 1)

It is not difficult to find that the order of the two 1's in the original sequence has been destroyed, and the order has been changed, which is naturally an "unstable" sorting algorithm

About O

In the previous article "Bubble Sorting Method", we explained in detail what O is, so I won't say more here, just go to the picture

The above is the detailed content of How to implement quick sort. For more information, please follow other related articles on the PHP Chinese website!