Note:

想到双指针相向而行，当array[i], 遇到比pivot大的就swap(array, i, j—);

Key word:

比pivot小的放左边，比pivot大的放右边，不用维持相对顺序

class Solution {
	public void partition(int[] array, int pivotIndex) {
    int pivot = array[pivotIndex];
    swap(array, pivotIndex, array.length - 1);
    // 交换之后不保证相对顺序，两指针相向而行
    int i = 0;
    int j = array.length - 2;
    while (i <= j) {
      if (array[i] < pivot) {
        i++;
      } else {
        swap(array, i, j--);
      }
    }
    swap(array, i, array.length - 1);
  }

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

Complexity Analysis:

TC: O(N);

SC: O(1);