Quick Sort

• 描述
  实现快速排序算法

• 分析
  随机选择待排序数组中一个元素为中心轴，将所有小于中心轴的元素移到左边，大于中心轴的元素移到右边，然后对中心轴左边和右边按照以上步骤递归下去，直至有序。
  中心轴的选择很重要，比较好的情况就是恰好选择的元素就是数组的中位数，这时候递归树相对平衡，递归树的高也就是栈的深度，树越平衡，消耗的栈空间越少，最坏情况，即待排序数组逆序，可以演化为冒泡排序，且空间复杂度O(n)。

• 时间复杂度O(nlogn)，空间复杂度O(logn)

public class Solution {

    public void quickSort(int[] arr, int left, int right) {
        int pivotIndex = partition(arr, left, right);
        if(left < pivotIndex - 1)
            quickSort(arr, left, pivotIndex - 1);
        if(right > pivotIndex)
            quickSort(arr, pivotIndex, right);
    }

    public int partition(int[] arr, int left, int right) {
        int pivot = arr[(left+right)/2];
        while(left <= right) {
            while(arr[left] < pivot)
                ++ left;
            while(arr[right] > pivot)
                -- right;
            if(left <= right) {
                swap(arr, left, right);
                ++ left;
                -- right;
            }
        }
        return left;
    }

    public void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}