快速排序

在數(shù)組中選擇一個元素K，然后將數(shù)組中大于該元素K的元素放在元素K的左邊，小于的放在右邊，形成左右兩個新的數(shù)組。
然后在左右兩邊數(shù)組中再選取一個元素M，重復上述操作。
知道最后數(shù)組的首尾是同一個元素的時候，返回。

快速排序的原址排序實現(xiàn)：
選取子數(shù)組的末一位為分隔元素。
一個for循環(huán)指針j從子數(shù)組頭開始向后遍歷，在遍歷的過程中會變成指向大于分隔元素范圍的尾。
另一個指針i指向子數(shù)組的開頭的前一位，在遍歷過程中變成指向大于分隔元素范圍的首之前一位，在交換之前會疊加指向大于分隔元素范圍的首。
當j指向的元素大于分隔元素時。i不變，for循環(huán)疊加j變?yōu)橹赶虼笥诜指粼胤秶奈病?br> 當j指向的元素小于分隔元素時。i加一，交換j下標和i下標的元素（在交換之前，i之前的元素都是小于分隔元素而指向的是大于分隔元素的元素，j指向之后的元素還沒遍歷，之前到i范圍內都是大于分隔元素的。），交換以后，把小于分隔元素的元素換到了i的位置（i又指向了大于分隔元素范圍首之前的一位），而本來就大于分隔元素的元素被向后交換。
在遍歷完以后，交換i+1(指向的是大于分隔元素范圍首)，和分隔元素（此時在子數(shù)組的尾部）。

在用一個函數(shù)遞歸該函數(shù)就可以了。

如果不取子數(shù)組尾部元素為分隔元素，而是隨即選?。耗蔷拖入S即選取一個，然后再交換選取的元素和子數(shù)組尾元素。（哈哈哈~~）

#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);
}