Quick sort algorithm principle and java recursive implementation

Quick sort is an improvement on bubble sort. If the initial record sequence is ordered by keywords or basically ordered, it degenerates into bubble sort. It uses the recursive principle and has the best average performance among all sorting methods of the same order of magnitude O(n longn). In terms of average time, it is currently considered the best internal sorting method

The basic idea is: split the data to be sorted into two independent parts through one-way sorting, and all the data in one part is smaller than All the data in the other part must be small, and then use this method to quickly sort the two parts of the data respectively. The entire sorting process can be performed recursively, so that the entire data becomes an ordered sequence.

Three pointers: The first pointer is called the pivotkey pointer (pivot), the second pointer and the third pointer are the left pointer and the right pointer respectively, pointing to the leftmost value and the rightmost value respectively. value. The left pointer and the right pointer approach from both sides to the middle at the same time. During the approach, they are constantly compared with the pivot, moving elements smaller than the pivot to the low end, and moving elements larger than the pivot to the high end. Once selected, it will never change, ending up in the middle, smaller in front and larger in the back.

Requires two functions:

① Recursive function public static void quickSort(int[]n,int left,int right)
② Split function (one-pass quick sort function) public static int partition(int[]n,int left,int right)

JAVA source code (successfully run):

package testSortAlgorithm;
public class QuickSort {
 public static void main(String[] args) {
  int [] array = {49,38,65,97,76,13,27};
  quickSort(array, 0, array.length - 1);
  for (int i = 0; i < array.length; i++) {
   System.out.println(array[i]);
  }
 }
 /*先按照数组为数据原型写出算法，再写出扩展性算法。数组{49,38,65,97,76,13,27}
  * */
 public static void quickSort(int[]n ,int left,int right){
  int pivot;
  if (left < right) {
   //pivot作为枢轴，较之小的元素在左，较之大的元素在右
   pivot = partition(n, left, right);
   //对左右数组递归调用快速排序，直到顺序完全正确
   quickSort(n, left, pivot - 1);
   quickSort(n, pivot + 1, right);
  }
 }

 public static int partition(int[]n ,int left,int right){
  int pivotkey = n[left];
  //枢轴选定后永远不变，最终在中间，前小后大
  while (left < right) {
   while (left < right && n[right] >= pivotkey) --right;
   //将比枢轴小的元素移到低端，此时right位相当于空，等待低位比pivotkey大的数补上
   n[left] = n[right];
   while (left < right && n[left] <= pivotkey) ++left;
   //将比枢轴大的元素移到高端，此时left位相当于空，等待高位比pivotkey小的数补上
   n[right] = n[left];
  }
  //当left == right，完成一趟快速排序，此时left位相当于空，等待pivotkey补上
  n[left] = pivotkey;
  return left;
 }
}

Please pay attention to more articles related to the principles of quick sorting algorithm and java recursive implementation PHP Chinese website!