排序的相关算法--快排2（非递归）【菜鸟学习日记】

今天接着上一篇，优化改进一下快排，以及非递归去实现，并且分析一下它的相关效率问题

上一篇我们用了三种方法实现了基础快排，但是也有一些问题要去进行改进

---

问题一、快排给数据时，如果遇到最坏的情况

这里我们要对快排算法进行分析

分析快排的时间效率，取决于进行了多少趟排序，也就是我们递归的深度

这里我们分析最好与最坏的情况

我们分别都来画图示意一下

1、快排最好的情况–每趟又能将所排的序列一分为二，将表分成两个大小相等的序列，类似于折半查找，效率为O（NlogN)

这个例子还不是最理想的，但大致就是像这个例子一样

2、快排的最坏情况–序列已经排好

第一趟进行n-1次比较，第二趟n-2 …
(n-1)+(n-2)+…+1=n2/2

所以快排的效率就是O（logN)

---

如果是像这样的情况，第一次选key时，我们就要注意，不要选到9，所以我们写了一个函数，三数取中，避免我们选到当前待排序列的最大或最小

//三数取中（优化快排的最坏情况）
int GetMidIndex(int*a, int left, int right)
{
    int mid = left + ((right - left) >> 1);
    //left  mid  right
    //三个数比大小，取中数，这样就可以避免掉最坏的情况
    if (a[left] < a[mid])
    {
        if (a[mid] < a[right])
        {
            return mid;
        }
        else if (a[left]<a[right])
        {
                return right;
        }
        else
        {
            return left;
        }
    }
    else   //left>mid
    {
        if (a[mid] > a[right])
        {
            return mid;
        }
        else if (a[left]>a[right])
        {
            return right;
        }
        else
        {
            return left;
        }
    }
}

---

问题二、对于栈，害怕栈溢出的优化

对于小区间用插入排序

//对于递归版的再优化，少用栈帧
void QuickSortBetter(int*a, int left, int right)
{
    //a不能为空
    assert(a);

    //a不能只有一个数
    if (left >= right)
        return;

    //小区间进行优化，不用递归更快
    if (right - left < 10)
    {
        //小区间用插入排序
        InsertSort(a + left, right - left + 1);
    }
    else
    {
        int div = _PartSort2(a, left, right);
        //再排剩下的左边的和右边的区域
        QuickSortBetter(a, left, div - 1);
        QuickSortBetter(a, div + 1, right);
    }
}

还有就是非递归的实现

//非递归实现快排--用栈
void QuickSortNonR(int* a, int begin, int end)
{
    stack<int> s;
    if (begin < end)
    {
        s.push(end);
        s.push(begin);
    }

    //当栈里还有数，说明还有待排列的区间
    while (!s.empty())
    {
        int left = s.top();
        s.pop();
        int right = s.top();
        s.pop();

        int div = _PartSort2(a, left, right);
        if (left < div - 1) //说明左区域还有至少两个数，还要排,将其Push,待排
        {
            s.push(div - 1);
            s.push(left);
        }
        if (div + 1 < right)
        {
            s.push(right);
            s.push(div + 1);
        }
    }
    //排列完成
}