快速排序

在数组中选择一个元素K，然后将数组中大于该元素K的元素放在元素K的左边，小于的放在右边，形成左右两个新的数组。
然后在左右两边数组中再选取一个元素M，重复上述操作。
知道最后数组的首尾是同一个元素的时候，返回。

快速排序的原址排序实现：
选取子数组的末一位为分隔元素。
一个for循环指针j从子数组头开始向后遍历，在遍历的过程中会变成指向大于分隔元素范围的尾。
另一个指针i指向子数组的开头的前一位，在遍历过程中变成指向大于分隔元素范围的首之前一位，在交换之前会叠加指向大于分隔元素范围的首。
当j指向的元素大于分隔元素时。i不变，for循环叠加j变为指向大于分隔元素范围的尾。
当j指向的元素小于分隔元素时。i加一，交换j下标和i下标的元素（在交换之前，i之前的元素都是小于分隔元素而指向的是大于分隔元素的元素，j指向之后的元素还没遍历，之前到i范围内都是大于分隔元素的。），交换以后，把小于分隔元素的元素换到了i的位置（i又指向了大于分隔元素范围首之前的一位），而本来就大于分隔元素的元素被向后交换。
在遍历完以后，交换i+1(指向的是大于分隔元素范围首)，和分隔元素（此时在子数组的尾部）。

在用一个函数递归该函数就可以了。

如果不取子数组尾部元素为分隔元素，而是随即选取：那就先随即选取一个，然后再交换选取的元素和子数组尾元素。（哈哈哈~~）

#include <algorithm>
#include <vector>
#include <iostream>
#include <stack>
using namespace std;

void print(vector<int> &source)
{
    cout<<endl;
    for(auto i:source)
    {
        cout<<i<<" ";
    }
    cout<<endl;
}

size_t partition(size_t start,size_t end,vector<int> &source)
{
    size_t index=start;
    int target=source[end];
    for(int j=start;j<end;j++)
    {
        if(source[j]<target)
        {
            swap(source[j],source[index]);
            index++;
        }
    }
    swap(source[index],source[end]);

    print(source);
    
    return index;
}

void quicksort(size_t start, size_t end,vector<int> &source)
{
    if(start >= end)
    {
        return;
    }
    int p = partition(start,end,source);

    quicksort(start,p-1,source);
    quicksort(p+1,end,source);
}

void quicksortUseStack(size_t start,size_t end,vector<int> &source)
{
    stack<size_t> st;
    if(start<end)
    {
        st.push(start);
        st.push(end);
    }
    size_t s;//start
    size_t e;//end
    size_t p;//partition
    while(!st.empty())
    {
        e=st.top();
        st.pop();
        s=st.top();
        st.pop();

        p=partition(s,e,source);

        if(s<(p-1))
        {
            st.push(s);
            st.push(p-1);
        }
        if((p+1)<e)
        {
            st.push(p+1);
            st.push(e);
        }
    }
}

int main()
{
    vector<int> a{1,2,4,9,6,1,3,5,8,0,3,2,1,7,9,3,8};
    print(a);
    
    quicksortUseStack(0,a.size()-1,a);
    print(a);
}