Implementation of quick sorting algorithm in Java

Principle of quick sort: select a key value as the benchmark value. The sequence smaller than the benchmark value is on the left (generally unordered), and the sequence larger than the benchmark value is on the right (generally unordered). Generally, the first element of the sequence is selected.

One cycle: compare from the back to the front, and compare the reference value with the last value. If the exchange position is smaller than the reference value, if the next one is not compared, it will not be exchanged until the first value smaller than the reference value is found. After finding this value, compare it from front to back. If there is a value larger than the benchmark value, exchange the position. If there is no comparison, continue to compare the next value until the first value larger than the benchmark value is found. Until the comparison index from front to back > the comparison index from back to front, the first cycle ends. At this time, the left and right sides are orderly for the benchmark value.

Then compare the left and right sequences respectively and repeat the above cycle.

The last sentence above is not a benchmark value, which means that it is not exchanged directly with the benchmark value, but with the index where the benchmark value is located.

Let's look at another implementation.

The process of a quick sort is as follows

(1) First, select a number from the sequence as the reference number

(2) Put all the numbers larger than this number to its right, and all the numbers less than or equal to it to its left

A quick sort is also called a part, that is, the sequence is divided into two parts, one is smaller than the benchmark number, the other is larger than the benchmark number, and then

Then divide and conquer the process. Because each part may not be evenly divided, the time complexity in the worst case cannot be reduced

Guarantee always for

For the partion process, there are usually two methods

(1) Two pointers scan from head to tail to middle (bidirectional scan)

This method can be described as digging and filling, for example

Initialization: I = 0; j=9; pivot=a[0];

Now a [0] is saved in the variable pivot, which is equivalent to digging a hole in the array a [0], so you can fill in other numbers here. Starting from J, find a number less than or equal to pivot, that is, fill a [8] into a [0], but a [8] forms a new pit, and then starting from I, find a number greater than pivot, that is, fill a [3] into a [8], then a [3] forms a new pit

In this way, it doesn't stop until I = = J, and the final result is as follows

The above process is a quick sort.

summary

The above is all about the implementation of quick sorting algorithm in Java. I hope it will be helpful to you. If there are deficiencies, please leave a message to point out.