快排模闆（分治思想）

  簡單總結一下快排算法。快排主要分為兩個階段，第一個階段為劃分，第二個階段為在劃分的基礎上再次進行劃分。先說一下劃分，何為劃分，首先要确定一個基準，這裡可以了解為先找一個數作為基準（預設是增序，反之亦然），然後将小于它的數全放到它的左邊，将大于它的數放到它的右邊，這樣通過一次劃分就确定了這個數的最終位置。接下來就很簡單了，隻要根據分治的思想，分别對左右兩個部分進行劃分即可。

  快排隻用了常數級别的輔助空間，故空間複雜度為 O ( 1 ) O(1) O(1),平均時間複雜度為 O ( n l o g n ) O(nlogn) O(nlogn)。

void quicksort(vector<int>& nums, int start, int end)
{
    if(start >= end)
        return;
    int mid = start + (end - start) / 2;
    int midval = nums[mid];
    int p = start, q = end;
    while(p <= q)
    {
        while(p <= q && nums[p] < midval)
            ++p;
        while(p <= q && nums[q] > midval)
            --q;
        if(p <= q)
        {
            swap(nums[p], nums[q]);
            ++p;
            --q;
        }
    }
    quicksort(nums, start, q);
    quicksort(nums, p, end);
}