[模板总结] - 快速排序

Leetcode 912 - 数组排序

和归并排序的思想，我们也是通过分治法来实现从局部有序最后全局有序，但是与归并排序不同的是，归并排序先分治出最小子问题（两个单一元素数组归并），先得到最小子问题合并结果然后往上层返回，得到最后合并结果。

快速排序分治思路是先通过pivot - 当前数组中一个值作为标杆，将大于放到一边，小于放到一边，我们成为partition， 然后在分治到子问题，将左右两部分继续进行partition。当到达最小子问题时，数组已经是有序。

代码如下:

public void quickSort(int[] arr, int start, int end) {

    if(start > end) return;

    int l = start; r = end;

    int mid = l + (r-l>>1); 这样做为了防止直接l+r溢出
    int pivot = arr[mid];

    // partition 这里 l<=r是为了防止死循环
    while(l<=r) {
        while(l<=r && arr[l]pivot) r--;

        if(l<=r) {

            int temp = arr[l];
            arr[l]  = arr[r];
            arr[r] = temp;
            l++; r--;
        }        
    }
    
    // partition 之后l, r指针会交错
    quickSort(arr, start, r);
    quickSort(arr, end, l);
}

时间复杂度：，最坏情况：每一次partition都只分割出一个元素的顺序(一组N-1个，一组1个)；空间复杂度：,如果不考虑系统递归的空间 。