[Calculate every Week] ten classic sorting algorithm of the quick sort

The time complexity of sorting

Quicksort process

1. It picks an element from the sequence, called the pivot;
2. Reorder the sequence so that all elements smaller than the base value are placed in front of the base value, and all elements larger than the base value are placed after the base value (the same number can be on either side). After the partition exits, the benchmark is in the middle of the series. This is called a partition operation;
3. Recursively sort the subsequence of elements less than the base value and the subsequence of elements greater than the base value;

Code implementation

public class QuickSortTest01 {


  public static void quicksort(int[] arr, int left, int right) {

    if (left >= right) {
      return;
    }

    int flag = left;
    int start = left;
    int end = right;

    while (left < right) {
      while ((left < right) && (arr[right] >= arr[flag])) {
        right--;
      }
      if (arr[right] < arr[flag]) {
        int tmp = arr[right];
        arr[right] = arr[flag];
        arr[flag] = tmp;
        flag = right;
      }

      while ((left < right) && (arr[left] <= arr[left])) {
        left++;
      }

      if (arr[left] > arr[flag]) {
        int tmp = arr[left];
        arr[left] = arr[flag];
        arr[flag] = tmp;
        flag = left;
      }
    }

    quicksort(arr, start, flag - 1);
    quicksort(arr, flag + 1, end);


  }


  /** * Placeholder method **@param arr
   * @param left
   * @param right
   */
  public static void quick_sort(int[] arr, int left, int right) {
    if (left < right) {

      //Swap(s[l], s[(l + r) / 2]); // Swap the middle number with the first number. See note 1
      int i = left, j = right, x = arr[left];

      while (i < j) {
        while (i < j && arr[j] >= x) // Look from right to left for the first number less than x
          j--;
        if (i < j) {
          arr[i++] = arr[j];
        }

        while (i < j && arr[i] < x) // Look from left to right for the first number greater than or equal to x
          i++;
        if (i < j) {
          arr[j--] = arr[i];
        }
      }
      arr[i] = x;
      quick_sort(arr, left, i - 1); // Call recursively
      quick_sort(arr, i + 1, right); }}public static void main(String[] args) {
    int[] arr = new int[] {23.100.10.5.2.200};

    quick_sort(arr, 0, arr.length - 1); System.out.println(arr); }}Copy the code