Simple example of quick sort in Java

This article mainly introduces Java simple quick sorting examples in detail, which has certain reference value. Interested friends can refer to it

1. Basic concepts

Find an element (theoretically you can find any one) as the pivot (pivot), and then partition the array so that the value of the element to the left of the pivot is not greater than the pivot value, and the value of the element to the right of the pivot is not less than The base value, so that the element used as the base is adjusted to the correct position after sorting. Recursive quick sort adjusts the 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 the quick sort algorithm is the partition operation, that is, how to adjust the position of the benchmark and adjust the final position of the returned benchmark for divide and conquer recursion.

2. Select the benchmark element

1. Fixed the benchmark element

If the input sequence is random, the processing time is acceptable. If the array is already sorted, the division at this time is a very bad division. Because each division can only reduce the sequence to be sorted by one, this is the worst case scenario. Quick sorting becomes bubble sorting, and the time complexity is Θ(n^2). Moreover, it is quite common for the input data to be ordered or partially ordered. Therefore, using the first element as the base element is very bad and should be abandoned immediately.

2. Random base yuan

This is a relatively safe strategy. Since the position of the reference element is random, the resulting segmentation will not always be a poor-quality segmentation. When the entire array numbers are all equal, it is still the worst case and the time complexity is O(n^2). In fact, the probability of randomizing quicksort to get the theoretical worst case is only 1/(2^n). Therefore, randomized quick sort can achieve the expected time complexity of O(n×log(n)) for most input data.

3. Take the middle of three numbers

The best division is to divide the sequence to be sorted into subsequences of equal length. In the best state, we can use the middle value of the sequence, that is N/2th number. However, this is difficult to calculate and will significantly slow down quicksort. Such an estimate of the median can be obtained by randomly selecting three elements and using their median as the base element. In fact, randomness doesn't help much, so the general approach is to use the median of the three elements at the left end, right end, and center position as the base element.

3. Partition algorithm

The partition algorithm is the core of quick sort. Before learning quick sort, you can learn this algorithm first. Paste the code first:

  public int partition(int[] num,int left,int right){
    if(num==null || num.length<=0 || left<0 || right>=num.length){
      return 0;
    }
    int prio=num[left+(right-left)/2];  //获取数组中间元素的下标
    while (left<=right){         //从两端交替向中间扫描
      while (num[left]<prio)
        left++;
      while (num[right]>prio)
        right--;
      if (left<=right){
        swap(num,left,right);    //最终将基准数归位 
        left++;
        right--;
      }
    }
    return left;
  }

The idea of ​​​​this method is to first find a pivot element (the first element is found in the implementation of this method, there are actually many articles on it) Here we simplify the description first), and then generate two pointers left and right from both sides of the array (the specific where to where is determined by the passed in parameters). Every time it is found that the element on the left is greater than the pivot element, i will stop, and the element on the right is less than The pivot element j stops and exchanges the positions of the two numbers. Until the two pointers left and right meet. Then insert the pivot element into the left position, which is where it should be.

The final result of this is to make the [left, right] part of the array appear in two parts. The final position of the pivot element on the left is less than or equal to the pivot element, and the final position on the right is greater than or equal to the pivot element. The pivot element is inserted into an absolutely correct position.

4. Implementation of sorting algorithm

package sort;
/**
 * 快速排序
 * 快速排序采用了分治策略。就是在一个数组中取一个基准数字，把小的数放基准的左边，大的数放基准的右边。
 * 基准左边和右边分别是新的序列。在新的序列中再取一个基准数字，小的放左边，大的放右边。
 * 这个里面用到的递归。我们需要三个参数，一个是数组，另外两个是序列的边界
 * @author HJS
 */
public class QuickSort{

  void sort(int num[],int left,int right){
    if (left
The above is the detailed content of Simple example of quick sort in Java. For more information, please follow other related articles on the PHP Chinese website!