Java simple quick sort instance analysis

1、 Basic concepts

Find an element (you can find any one in theory) as the benchmark, and then partition the array so that the values of the elements on the left of the benchmark are not greater than the benchmark value, and the values of the elements on the right of the benchmark are not less than the benchmark value. In this way, the elements as the benchmark are adjusted to the correct position after sorting. Recursive quick sort adjusts other N-1 elements to the correct position after sorting. Finally, each element is in the correct position after sorting, and the sorting is completed. Therefore, the core algorithm of quick sort algorithm is partition operation, that is, how to adjust the position of benchmark and the final position of return benchmark in order to divide and conquer recursion.

2、 Select base element

1. Fixed datum element

If the input sequence is random, the processing time is acceptable. If the array is already ordered, the segmentation at this time is a very bad segmentation. Because each partition can only reduce the sequence to be sorted by one, this is the worst case, and the quick sort is reduced to bubble sort, with a time complexity of Θ (n^2)。 Moreover, it is quite common that the input data is orderly or partially orderly. Therefore, using the first element as a reference element is very bad and should be abandoned immediately.

2. Random reference element

This is a relatively safe strategy. Since the position of the reference element is random, the resulting segmentation will not always have inferior segmentation. When the numbers of the whole array are all equal, it is still the worst case, and the time complexity is O (n ^ 2). In fact, the probability of the theoretical worst case obtained by randomized quick sort is only 1 / (2 ^ n). Therefore, randomized quick sort can reach o (n) for most input data × Log (n)).

3. Triple median

The best division is to divide the sequence to be sorted into equal length subsequences. In the best state, we can use the middle value of the sequence, that is, the N / 2 number. However, this is difficult to calculate and will significantly slow down the speed of quick sorting. Such median estimation can be obtained by randomly selecting three elements and using their median as the reference element. In fact, randomness does not help much, so the general practice is to use the median of the three elements at the left, right and center as the reference element.

3、 Partition algorithm

Partition algorithm is the core of fast sorting. You can learn this algorithm before learning fast sorting. The following code is posted first:

The idea of this method is to find a pivot element first (the first element is found in the implementation of this method, which is actually very specific, but the description is simplified here first), and then start from both sides of the array (where to go is determined by the incoming amount parameter) generate two pointers left and right. Each time it is found that the element on the left is larger than the hub element, I will stop, and the element on the right is smaller than the hub element, J will stop, and exchange the positions of the two numbers. Until the two pointers left and right meet, insert the hub element into the left position, that is, the position it should be in.

The final result is that the [left, right] part of the array presents two parts. The final position of the hub element is less than or equal to the hub element on the left and greater than or equal to the hub element on the right. The hub element is inserted into an absolutely correct position.

4、 Implementation of sorting algorithm

The above is the whole content of this article. I hope it will be helpful to your study, and I hope you can support programming tips.