Java implements the quick sort algorithm of Quicktsort

Introduction to quicksort algorithm
Quick sort and Merge sort partition method is used to design the algorithm, the difference is that the Merge sort an array can be divided into two basic equal length subarray, respectively after sorted and Merge (Merge) operation, and quick sort molecules array when a more artistic, take a base element, after break up the base element to the left of the element are smaller than base element, element of the right of the element is not less than the benchmark, so you just need to order of the two sub array respectively, no longer need to Merge operations like Merge sort. The selection of the reference elements has a great impact on the efficiency of the algorithm, and the best case is that the two subarrays are roughly the same size. For simplicity, let's pick the last element, but the more advanced way is to take a median and swap it with the last element, and then do the same thing. Split is at the heart of quicksort. The worst running time for quicksort is O(n2), but the expected running time is O(NLGN).

Quicksort algorithm Java implementation
1. Split the array into two sub-arrays and add a reference element: select the last element as the reference element, and the index variable records the position of the last element less than the reference element, initialize it to start- 1, and find the new element less than the reference element, index plus 1. From the first element to the penultimate element, compare to the base element in turn, less than the base element, index plus 1, swap the position of the index and the current position of the element. At the end of the loop, index+1 gets the position where the reference element should be, swapping index+1 with the last element.
2. Sort two subarrays [start, index] and [index+2, end] respectively
As in Java implementation of Insertsort, you first implement an array utility class. The code is as follows:

public class ArrayUtils {

     public static void printArray(int[] array) {
      System.out.print("{");
      for (int i = 0; i < array.length; i++) {
       System.out.print(array[i]);
       if (i < array.length - 1) {
        System.out.print(", ");
       }
      }
      System.out.println("}");
     }
     public static void exchangeElements(int[] array, int index1, int index2) {
      int temp = array[index1];
      array[index1] = array[index2];
      array[index2] = temp;
     }
    }

The Java implementation of quicksort and the test code are as follows:

public class QuickSort {
  public static void main(String[] args) {
   int[] array = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3 };
   System.out.println("Before sort:");
   ArrayUtils.printArray(array);
   quickSort(array);
   System.out.println("After sort:");
   ArrayUtils.printArray(array);
  }
  public static void quickSort(int[] array) {
   subQuickSort(array, 0, array.length - 1);
  }
  private static void subQuickSort(int[] array, int start, int end) {
   if (array == null || (end - start + 1) < 2) {
    return;
   }
   int part = partition(array, start, end);
   if (part == start) {
    subQuickSort(array, part + 1, end);
   } else if (part == end) {
    subQuickSort(array, start, part - 1);
   } else {
    subQuickSort(array, start, part - 1);
    subQuickSort(array, part + 1, end);
   }
  }
  private static int partition(int[] array, int start, int end) {
   int value = array[end];
   int index = start - 1;
   for (int i = start; i < end; i++) {
    if (array[i] < value) {
     index++;
     if (index != i) {
      ArrayUtils.exchangeElements(array, index, i);
     }
    }
   }
   if ((index + 1) != end) {
    ArrayUtils.exchangeElements(array, index + 1, end);
   }
   return index + 1;
  }
 }