July 31, 2019

Quick Sort

经典 Divide and Conquer 算法。

Best time complexity: Ω(n log(n))
Average time complexity: Θ(n log(n))
Worst time complexity: O(n^2)
Worst space complecity: O(log(n))

public class Solution {
  public int[] quickSort(int[] array) {
    if (array == null || array.length <= 1) {
      return array;
    }
    quickSort(array, 0, array.length - 1);
    return array;
  }

  public void quickSort(int[] array, int left, int right) {
    if (left >= right) {
      return;
    }
    int pivotPos = partition(array, left, right);
    quickSort(array, left, pivotPos - 1);
    quickSort(array, pivotPos + 1, right);
  }

  private int partition(int[] array, int left, int right) {
    int pivotIndex = right;
    int i = left;
    int j = right - 1;
    while (i <= j) {
      if (array[i] < array[pivotIndex]) {
        i++;
      } else if (array[j] > array[pivotIndex]) {
        j--;
      } else {
        swap(array, i, j);
        i ++;
        j --;
      }
    }
    swap(array, i, pivotIndex);
    return i;
  }

  private void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
}