快速排序（递归的三种方法及其优化、非递归方法）

1.传统方法
思路：任意找一个key,begin和end从两头找，begin找大（相对于key），end找小，找到了就交换。完毕之后将key放在中间为boundary，再用两边的区间递归上面的做法，直到元素有序。

int Partition(int *a,int left,int right)
{
    assert(a);
    int begin = left,end = right - 1,key = a[right];
    while(begin < end)
    {
        while(a[begin] < key && begin <= end)
        {
            begin++;
        }
        while(a[end] > key && end >= begin)
        {
            --end;
        }
        if(begin < end)
        {
            swap(a[begin],a[end]);
        }
    }
    if(a[begin] > a[right])
    {
        swap(a[begin],a[right]);
        return begin;
    }
    else
    {
        return right;
    }
}
void QuickSort(int *a,int left,int right)
{
    assert(a);
    if(right > left)
    {
        int boundary = Partition(a,left,right);
        QuickSort(a,left,boundary - 1);
        QuickSort(a,boundary + 1,right);
    }
}

2.延伸方法（代码较简洁）
思路：定义prev和cur，prev刚开始在cur前一个，两个都在左边，prev往前指向小的，cur往前指向大的，逐次交换直到最后面。

int Partition2(int *a,int left,int right)
{
    assert(a);
    int cur = left,prev = left - 1,key = a[right];
    while(cur < right)
    {
        if(a[cur] < key && (++prev) != cur)
        {
            swap(a[prev],a[cur]);
        }
        ++cur;
    }
    swap(a[++prev],a[right]);
    return prev;
}
void QuickSort2(int *a,int left,int right)
{
    assert(a);
    if(right > left)
    {
        int boundary = Partition2(a,left,right);
        QuickSort(a,left,boundary - 1);
        QuickSort(a,boundary + 1,right);
    }
}

3.挖坑填数法
原理：找一个key，key的位置为最前（最后也行），key的位置就相当于一个坑，begin从前往后找小，若找到了比key更小的就填补到key的位置,自己的位置就等于有个坑了，再从前往后找小，若找到了比key更小的就填补到上一个坑的位置，重复以上步骤，直到数列有序。

int Partition3(int *a,int left,int right)
{
    assert(a);
    int begin = left,end = right,key = a[right];
    while(begin < end)
    {
        while(a[begin] <= key && begin <= end)
        {
            ++begin;
        }
        if(begin < end)
        {
            a[end] = a[begin];
        }
        while(a[end] >= key && begin <= end)
        {
            --end;
        }
        if(begin < end)
        {
            a[begin] = a[end];
        }
    }
    a[begin] = key;
    return begin;
}
void QuickSort3(int *a,int left,int right)
{
    assert(a);
    if(right > left)
    {
        int boundary = Partition3(a,left,right);
        QuickSort(a,left,boundary - 1);
        QuickSort(a,boundary + 1,right);
    }
}

4.优化
（1）从上面方法可以看出当选的key越接近数列中最大值或最小值时，递归的次数越多，算法效率越低，所以我们要尽量把key选的适中。以下是三数取中法：

int GetMidIndex(int *a,int left,int right)
{
    assert(a);
    int mid = left -(left - right)/2;
    if(a[left] < a[right])
    {
        if(a[mid] < a[left])
            return left;
        else if(a[mid] < a[right])
            return mid;
        else
            return right;
    }
    else
    {
        if(a[mid] < a[right])
            return right;
        if(a[mid] < a[left])
            return mid;
        else
            return left;
    }
}

（2）
数组长度大时候用快排，排到一定程度，数组变小了之后用插入排序提高效率。
因为直接插入对小区间效率较高。
5.非递归方法

void QuickSort5(int *a,int left,int right)
{
    assert(a);
    stack<int> s;
    if(right > left)
    {

        int boundary = Partition5(a,left,right);
        if(left < boundary - 1)
        {
            s.push(left);
            s.push(boundary - 1);
        }
        if(boundary+1 < right)
        {
            s.push(boundary+1);
            s.push(right);
        }
        while(!s.empty())
        {
            int end = s.top();
            s.pop();
            int begin = s.top();
            s.pop();
            boundary = Partition2(a,begin,end);

            if(begin < boundary - 1)
            {
                //左边界在下，右边界在上。
                s.push(begin);
                s.push(boundary - 1);
            }
            if(boundary + 1 < end)
            {
                s.push(boundary+1);
                s.push(end);
            }
        }
    }
}