快速排序
在数组中选择一个元素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);
}
