【数据结构】大量数据（20万）的快速排序的递归与非递归算法、三数取中思想

快速排序的挖坑法与prev、cur法，我们在上一篇博客的第6个排序中讲的非常详细，http://10740184.blog.51cto.com/10730184/1774508【数据结构】常用排序算法（包括：选择排序，堆排序，冒泡排序，选择排序，快速排序，归并排序）    

有兴趣的话，相信聪明的你，一看就会秒懂快速排序的思想。

下面，我们将快速排序优化：

1、三数取中来优化快速排序

优化原因：

快速排序的擦差不多每次将序列一分为二，时间复杂度是O(n*lgn).

我们思考，快速排序的时间复杂度是O(n*lgn)，在序列乱序时，它的效率很高。但是，当序列有序或者接近有序时，效率就没有那么高了。

如果一个序列是这样的：

｛10，5，1，4，5，9，6，1｝    

我们针对上述序列，如果要排成升序的话，我们要找一个数满足挖坑法里面的挪数据条件，或者说prev、cur法中的交换数据条件时，可能一直将序列从头遍历，找到结束或者快要结束才找到或者还没有找到，这时候相当于效率就变成了o(n^2)了。

优化方法：

因此，我们想到了三数取中的思想。即序列的三个位置最左边left,最右边right,中间mid，三个数取出中间大小的数，用这个数做key.

三数取中的代码如下：

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

2.非递归的实现

优化原因：

当一个序列较小时，每次将序列再成两半，递归处理两半的序列。

但是，当要给20万、30万这样的序列排序时，每次递归的话，无疑每次调用函数建立栈帧会很很大的系统开销，甚至会耗尽系统的空间。

优化方法：用栈stack模拟实现栈帧，每次压栈出栈---》即递归写法。

递归代码如下：

int PartSort(int* a, int left, int right)
{
    assert(a);
    int cur = left;
    int prev = cur - 1;
    int key = mid(a,left,right);
    swap(key, a[right]);

    while (cur < right)
    {
        if (a[cur] <= a[right])
        {
            swap(a[++prev], a[cur]);
        }
        cur++;
    }
    swap(a[++prev], a[right]);
    
    return prev;
}


void QuickSort(int* a, int left, int right)
{
    int prev = PartSort(a,left, right);

    if (prev - 1 > left)
    {
        QuickSort(a, left, prev - 1);
    }

    if (prev + 1 < right)
    {
        QuickSort(a, prev + 1, right);
    }

}

非递归代码如下（推荐）：

//prev、cur法，也可以采用挖坑法等其他办法
int PartSort(int* a, int left, int right)
{
    assert(a);
    int cur = left;
    int prev = cur - 1;
    int key = mid(a,left,right);
    swap(key, a[right]);//将三数取中得到的数据与a[right]处交换。

    while (cur < right)
    {
        if (a[cur] <= a[right])
        {
            swap(a[++prev], a[cur]);
        }
        cur++;
    }
    swap(a[++prev], a[right]);
    
    return prev;
}


void QuickSort_NonR(int* a, int left, int right)
{
    stack<int> s;
    //左右区间压入栈中，或者此时也可以定义一个结构体，里面有左右区间，一次把左右区间都压进去
    s.push(left);
    s.push(right);
    while (!s.empty())
    {
        //[left,right]
        int curRight = s.top();//压栈先压的是左区间，先进后出，取数据先取右区间
        s.pop();
        int curLeft = s.top();
        s.pop();
        int prev = PartSort(a, curLeft, curRight);//将这个区间进行一次快速排序
        if (prev - 1 > curLeft)
        {
            s.push(curLeft);//压入新分的左端序列
            s.push(prev - 1);
        }
        if (prev + 1 < curRight)
        {
            s.push(prev + 1);//压入新分的右段区间
            s.push(curRight);
        }
    }
}