快排 QuickSort

概念

快排是一种分治（Divide and Conquer）算法，在这种算法中，我们把大问题变成小问题，然后将小问题逐个解决，当小问题解决完时，大问题也迎刃而解。
快排的基本概念就是选取一个目标元素，然后将目标元素放到数组中正确的位置。然后根据排好序后的元素，将数组切分为两个子数组，用相同的方法，在没有排好序的范围使用相同的操作。

具体步骤

1. 对于当前的数组，取最后一个元素当做基准数（pivot）
2. 将所有比基准数小的元素排到基准数之前，比基准数大的排在基准数之后
3. 当基准数被放到准确的位置之后，根据基数数的位置将元素切分为前后两个子数组
4. 对子数组采用步骤1~4的递归操作，直到子数组的长度小于等于1为止

复杂度分析

时间复杂度：O(n^2)，平均时间复杂度：O(nlogN）
空间复杂度：O(n)，平均空间复杂度：O(logN)
在最坏的情况下，如果元素一开始就是从大到小倒序排列的，那么我们每个元素都需要调换，时间复杂度就是O(n^2)。当正常情况下，我们不会总碰到这样的情况，假设我们每次都找到一个中间的基准数，那么我们需要切分logN次，每层的划分(Partition)是O(N)，平均时间复杂度就是O(nlogN)。空间的复杂度取决于递归的层数，最糟糕的情况我们需要O(N)层，一般情况下，我们认为平均时间复杂度是O(logN)。

public void quickSort(int[] array, int left, int right) {
    if(left >= right) return;
    int partitionIndex = partition(array, left, right);
    quickSort(array, left, partitionIndex - 1);
    quickSort(array, partitionIndex + 1, right);
}
public int partition(int[] array, int left, int right) {
    int pivot = array[right];
    int leftIndex = left;
    int rightIndex = right - 1;
    while(true) { 
        while(leftIndex < right & array[leftIndex] <= pivot) {
            leftIndex++;
        }
        while(rightIndex >= left && array[rightIndex] > pivot) {
            rightIndex--;
        }
        if (leftIndex > rightIndex) break;
        swap(array, leftIndex, rightIndex);
    }
    swap(array, leftIndex, right); // swap pivot to the right position
    return leftIndex;
}
public void swap(int[] array, int left, int right) {
    int temp = array[left];
    array[left] = array[right];
    array[right] = temp;
}