• 每一轮就是这轮的基准数(pivot)归位，直到所有数归位。

• partition是返回一个基准值(pivot)的index, index左边都 < arr[index], 右边都 > arr[index]

• 步骤:

  • 定基准 find pivot partition
  • 划分区 divide and conquer, partition by pivot
  • 递归调用

• optimization

  • 对于很小且部分有序的数组 插排优于快排。所以 分割到某处时 用插排。
  • pivot的选择。最理想的pivot是等分左右。
    • 三位取中 or low&high 中random
    • 若选取的为固定第一/最后 则当输入为有序时(正序/倒序)时 均沦为O(n^2)

// test case: 6,1,2,7,9,3,4,5,10,8
public void quickSort(int[] array) {
    recQuickSort1(array, 0, array.length - 1);
    recQuickSort2(array, 0, array.length - 1);
}

////// similar to preorder traversal!!!
private void recQuickSort1(int[] array, int left, int right) {
    // 确保至少有两个数
    if (left >= right) {
        return;
    }

    // 基准归位 并 切分
    int partition = partition(array, left, partition - 1);

    recQuickSort(array, left, partition - 1);
    recQuickSort(array, partition + 1, right);
}

private int partition(int[] array,int left, int right) {
    int i = left + 1;
    int j = right;
    int pivot = array[left];

    while (i <= j) {   // while(true)??
        while (i <= j && array[i] < pivot) i++;
        while (i <= j && array[j] >= pivot) j--;

        if (i > j) break;
        swap(i, j, array);
    }
    swap(j, left, array);
    return j;
}

////////////////
private void reQuickSort2(int[] array, int left, int right) {
    if (left >= right) return;
    int i = left + 1;
    int j = right;
    int pivot = array[left];

    while (i <= j) {
        while (i <= j && array[i] < pivot) i++;
        while (i <= j && array[j] >= pivot) j--;

        if (i > j) break;
        swap(i, j, array);        
    }
    swap(j, left, array);

    reQuickSort2(array, left, j - 1);     
    reQuickSort2(array, j + 1, right);    // or i? yes both work
}

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers2(int[] A) {
        quickSort(A, 0, A.length - 1);
    }

    private void quickSort(int[] A, int start, int end) {
        if (start >= end) {
            return;
        }

        int left = start, right = end;
        // key point 1: pivot is the value, not the index
        int pivot = A[(start + end) / 2];

        // key point 2: every time you compare left & right, it should be 
        // left <= right not left < right
        while (left <= right) {
            // key point 3: A[left] < pivot not A[left] <= pivot
            while (left <= right && A[left] < pivot) {
                left++;
            }
            // key point 3: A[right] > pivot not A[right] >= pivot
            while (left <= right && A[right] > pivot) {
                right--;
            }
            if (left <= right) {
                int temp = A[left];
                A[left] = A[right];
                A[right] = temp;

                left++;
                right--;
            }
        }

        quickSort(A, start, right);
        quickSort(A, left, end);
    }
}

find median

public static int findMedian(int[] nums) {
    int median = partition(tem, 0, nums.length-1, nums.length/2);
    return median;
}
public static int partition(int[] nums, int l, int r, int rank) {
        int left = l, right = r;
        int now = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= now) {
                right--;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] <= now) {
                left++;
            }
            nums[right] = nums[left];
        }
        if (left - l == rank) {
            return now;
        } else if (left - l < rank) {
            return partition(nums, left + 1, r, rank - (left - l + 1));
        } else {
            return partition(nums, l, right - 1, rank);
        }
     }

find kth largest / smallest

• heap: O(nlogk)
• partition: O(n)

wiggle sort ii

partition template

    public int partition(int[] nums, int l, int r) {
        // 初始化左右指针和pivot
        int left = l, right = r;
        int pivot = nums[left];

        // 进行partition
        while (left < right) {
            while (left < right && nums[right] >= pivot) {
                right--;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            nums[right] = nums[left];
        }

        // 返还pivot点到数组里面
        nums[left] = pivot;
        return left;         
    }