Quicksort algorithm principle and Java recursive implementation

Quick sort An improvement on bubble sort, if the initial record sequence by keyword order or basic order, degenerate to bubble sort. Using a recursive principle, it performs best on average among all sorting methods of the same order of magnitude O(n longn). In terms of average time, is currently considered to be the best internal sorting method

The basic idea is: sort by a lie will sort the data split into separate two parts, one part of all the data are smaller than the other part of all data, and then of the two parts data respectively according to the method of quick sort, the entire sorting process can be recursive, to achieve the whole data into an orderly sequence.

Three Pointers: the first pointer is called the pivotkey pointer (pivot), and the second and third Pointers are the left and right Pointers, respectively, to the leftmost and rightmost values. Left pointer and right pointer approach to the middle from both sides at the same time, in the process of approximation and keep comparing with the pivot, the smaller than the pivot element moved to the low end, the larger than the pivot element moved to the high end, the pivot is always selected after the same, and finally in the middle, before the small after the big.

Two functions are required:

Recursive function   Public static void quickSort(int[]n,int left,int right)
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]);
  }
 }
 
 public static void quickSort(int[]n ,int left,int right){
  int pivot;
  if (left < right) {
   //Pivot, with the smaller element to the left and the larger element to the right
   pivot = partition(n, left, right);
   //Call quicksort recursively on the left and right arrays until the order is completely correct
   quickSort(n, left, pivot - 1);
   quickSort(n, pivot + 1, right);
  }
 }

 public static int partition(int[]n ,int left,int right){
  int pivotkey = n[left];
  //The pivot is selected and never changes, and ends up in the middle, smaller in front and larger in back
  while (left < right) {
   while (left < right && n[right] >= pivotkey) --right;
   //Move the elements smaller than the pivot to the low end, where the right position is empty, and wait for the low position to be filled by Numbers larger than the pivotkey
   n[left] = n[right];
   while (left < right && n[left] <= pivotkey) ++left;
   //Move the element larger than the pivot to the high end, where the left bit is empty, waiting for the number smaller than the pivotkey to fill in
   n[right] = n[left];
  }
  //When left == right, a quick sort is completed, and the left bit is equivalent to empty, waiting for pivotkey to be filled
  n[left] = pivotkey;
  return left;
 }
}