Simple understanding of quick sort

High quality resource sharing

Learning route guidance （ Click unlock ）	Knowledge orientation	Crowd positioning
🧡 Python Actual wechat ordering applet 🧡	Progressive class	This course is python flask+ Perfect combination of wechat applet , From the deployment of Tencent to the launch of the project , Create a full stack ordering system .
Python Quantitative trading practice	beginner	Take you hand in hand to create an easy to expand 、 More secure 、 More efficient quantitative trading system

Detailed description

Quick sort divides the sequence to be arranged into two independent parts through one-time sorting , The keywords of some sequences are smaller than those of other sequences , Then the two parts of the sequence can be sorted separately , In order to achieve the purpose of orderly sequence .

The detailed implementation steps of quick sort are as follows ：

1. Pick an element from the sequence , be called “ The benchmark ”（pivot）;
2. Reorder the sequence , All elements smaller than the benchmark value are placed in front of the benchmark , All elements larger than the benchmark value are placed behind the benchmark （ The same number can go to either side ）. After the partition exits , The benchmark is in the middle of the sequence . This is called a partition （partition） operation ;
3. recursively （recursive） Sort the subsequence of elements smaller than the reference value and subsequence of elements larger than the reference value .

Algorithm diagram

Problem solving

How to select a benchmark for quick sort ？

The first way ： Fixed position selection reference value ; When the whole sequence has become orderly , Efficiency is very low .

The second way ： Randomly select any number in the sequence to be arranged as the reference value ; When the sequence tends to order , Can improve efficiency , But when the whole sequence is all equal , The efficiency of random fast platoon is still very low .

The third way ： From the beginning of the interval 、 tail 、 middle , Take out a number , And then compare the size , Take this 3 The middle value of the number is used as the reference value ; This method solves many special problems , But for a sequence with many duplicate values , The effect is still not good .

What is a good optimization method for quick sorting ？

First , Reasonably select the reference value , Change the fixed position selection reference value to the three-point centring method , It can solve many special situations , Achieve faster partitioning .

secondly , When the length of the sequence to be sorted is divided to a certain size , Use insert sort . When the length of the sequence to be sorted is very small or basically tends to be orderly , Insert sort is more efficient .

After sorting , Numbers equal to the reference value can be put together , These numbers can be ignored in the next split . It is very useful to solve the problem of large amount of duplicate data .

On the implementation , Recursive quick sort has two recursive operations at the end of the function , Tail recursion optimization can be used for it （ In short , That is, the tail position calls itself ）.

Code implementation

|  | package cn.fatedeity.algorithm.sort; |
|  |  |
|  | import java.util.Random; |
|  |  |
|  | /** |
|  |  *  Fast sorting algorithm  |
|  |  */ |
|  | public class QuickSort { |
|  | private static void swap(int[] numbers, int src, int target) { |
|  | int temp = numbers[src]; |
|  |  numbers[src] = numbers[target]; |
|  |  numbers[target] = temp; |
|  |  } |
|  |  |
|  | private static int[] sort(int[] numbers, int low, int high) { |
|  | if (low > high) { |
|  | return numbers; |
|  |  } |
|  | //  Reference value of random number  |
|  | Random random = new Random(); |
|  | int pivotIndex = random.nextInt(low, high + 1); |
|  | int pivot = numbers[pivotIndex]; |
|  |  swap(numbers, pivotIndex, low); |
|  |  |
|  | int mid = low + 1; |
|  | for (int i = low + 1; i <= high; i++) { |
|  | if (numbers[i] < pivot) { |
|  |  swap(numbers, i, mid); |
|  |  mid++; |
|  |  } |
|  |  } |
|  |  swap(numbers, low, --mid); |
|  |  sort(numbers, low, mid - 1); |
|  |  sort(numbers, mid + 1, high); |
|  | return numbers; |
|  |  } |
|  |  |
|  | public static int[] sort(int[] numbers) { |
|  | return sort(numbers, 0, numbers.length - 1); |
|  |  } |
|  | } |