自己都忘了什么时候写的了，@_@

#pragma once

#include <list>
#include <vector>
#include <stack>

using namespace std;

struct Bound
{
    size_t low;
    size_t high;
    Bound(size_t lowind,size_t highind)
    {
        this->low=lowind;
        this->high=highind;
    }
};
template <typename T>
void QSort(vector<T> & vay) //从小到大排序
{
    size_t len=vay.size();
    if( len > 2)
    {
        stack<Bound> boundS;
        Bound bd(0,len-1);
        boundS.push(bd);

        size_t low,high;
        while( ! boundS.empty() ) //当栈不为空时
        {
            bd=boundS.top();//取栈顶元素
            low=bd.low;
            high=bd.high;
            boundS.pop();//弹出栈顶元素

            low++;//用数组的排序部分的首个元素作为关键值，进行比较

            while( true ) //进行二分数组排序
            {
                while( low < high && vay[low] <= vay[bd.low] ) //用数组的排序部分的首个元素作为关键值，进行比较
                {
                    low++;
                }
                while( low < high && vay[high] > vay[bd.low] ) //vay[high] > vay[bd.low] 不能用 >=，因为要二分数组的排序部分，保证两部分的排他性
                {
                    high--;
                }
                if( low < high )
                {//交换低索引和高索引元素
                    T tmp=vay[low];
                    vay[low]=vay[high];
                    vay[high]=tmp;
                }
                else 
                {//此时，low == high 为真
                    break;
                }
            }

            //此时，low == high 为真
            if( vay[low] > vay[bd.low] )
            {
                low--;
            }
            //将关键值插入大元素和小元素的分界
            T tmp=vay[low];
            vay[low]=vay[bd.low];
            vay[bd.low]=tmp;

            if( low - bd.low > 1 ) //若小元素部分元素个数大于1个，继续排序
            {
                Bound newbd(bd.low,low-1);
                boundS.push(newbd);
            }
            if( bd.high - low > 1)//若大元素部分元素个数大于1个，继续排序
            {
                Bound newbd(low+1,bd.high);
                boundS.push(newbd);
            }
        }
    }
    else if( len == 2) //若数组长度为2，直接比较
    {
        if( vay[0] > vay[1] )
        {
            T tmp=vay[0];
            vay[0]=vay[1];
            vay[1]=tmp;
        }
    }
    //若数组长度小于2，不用排序
}

template <typename T>
struct BoundIter
{
    BoundIter(typename list<T>::iterator lowiter,typename list<T>::iterator highiter)
    {
        this->low=lowiter;
        this->high=highiter;
    }
    typename list<T>::iterator low;
    typename list<T>::iterator high;
};

template <typename T>
void QSort(list<T> & lst) //从小到大排序
{
    if( lst.size() > 2)
    {
        stack<BoundIter<T>> boundIterS;
        BoundIter<T> bd(lst.begin(),(--lst.end()));
        boundIterS.push(bd);

        list<T>::iterator low,high;
        while( ! boundIterS.empty() ) //当栈不为空时
        {
            bd=boundIterS.top();//取栈顶元素
            low=bd.low;
            high=bd.high;
            boundIterS.pop();//弹出栈顶元素

            low++;//用数组的排序部分的首个元素作为关键值，进行比较

            while( true ) //进行二分数组排序
            {
                while( low != high && *low <= *(bd.low) ) //用数组的排序部分的首个元素作为关键值，进行比较
                {
                    low++;
                }
                while( low != high && *high > *(bd.low) ) //*high > *(bd.low) 不能用 >=，因为要二分数组的排序部分，保证两部分的排他性
                {
                    high--;
                }
                if( low != high )
                {//交换低索引和高索引元素
                    T tmp=*low;
                    *low=*high;
                    *high=tmp;
                }
                else 
                {//此时，low == high 为真
                    break;
                }
            }

            //此时，low == high 为真
            if( *low > *bd.low )
            {
                low--;
            }
            //将关键值插入大元素和小元素的分界
            T tmp=*low;
            *low=*bd.low;
            *bd.low=tmp;

            if( low != bd.low ) 
            {//若小元素部分元素个数大于1个，继续排序
                low--;
                if( low != bd.low )
                {
                    BoundIter<T> newbd(bd.low,low);
                    boundIterS.push(newbd);
                }
                low++;
            }
            if( low != bd.high)
            {//若大元素部分元素个数大于1个，继续排序
                low++;
                if( low != bd.high )
                {
                    BoundIter<T> newbd(low,bd.high);
                    boundIterS.push(newbd);
                }
            }
        }
    }
    else if( lst.size() == 2) //若数组长度为2，直接比较
    {
        list<T>::iterator iter0=lst.begin();
        list<T>::iterator iter1=(++lst.begin());
        if( *iter0 > *iter1 )
        {
            T tmp=*iter0;
            *iter0=*iter1;
            *iter1=tmp;
        }
    }
    //若数组长度小于2，不用排序
}