排序优化——模拟栈及三路快排

几乎所有的编程语言都会提供排序函数，比如 C 语言的 qsort()， C++ STL 中的 sort()，这些排序函数是如何实现的呢？

1. 如何选择合适的排序算法？

如果要实现一个通用的高效率的排序函数，我们应该选择那种排序算法呢？

• 各种排序算法的特点如下所示。
  

• 线性排序算法的时间复杂度比较低，适用场景特殊，因此不适合作为通用的排序函数。

• 小规模数据可以选择时间复杂度为 $O(n^2)$O(n2) 的算法，大规模数据选择时间复杂度为 $O(nlogn)$O(nlogn) 的算法则会更加高效。为了兼顾任意规模的数据，一般会首选复杂度为 $O(nlogn)$O(nlogn) 的算法来实现排序函数。

• 归并排序虽然最好情况、最坏情况和平均情况下时间复杂度都可以做到 $O(nlogn)$O(nlogn)，但它不是原地排序算法，空间复杂度为 $O(n)$O(n)，排序的时候需要的额外空间和源数据一般大，空间消耗过高。

---

2. 如何优化快速排序？

快速排序最坏情况下时间复杂度退化为 $O(n^2)$O(n2) ，我们怎样来避免这种情况的发生呢？

• 实际上，这种 $O(n^2)$O(n2) 复杂度出现的主要原因还是分区点选取得不合理。

• 理想的分区点应该是，被分区点分开的两个区间，数据的数量差不多。

2.1. 分区点优化问题

• 三数取中法。从待排序数据首、尾、中分别取出一个数，然后对比大小，以这三个数的中间值作为分区点。

• 如果排序数据比较多，可能要“五数取中”或者“十数取中”。

• 随机法。每次从要排序的区间随机选择一个元素作为分区点，这种情况下，就可以避免每次分区点都选得非常糟糕。

2.2. 堆栈溢出问题

快速排序是利用递归来实现的，当递归的的深度过深时，就会导致堆栈溢出。

• 限制递归深度。当递归次数超过我们设定的阈值时，就停止递归。
• 在堆上模拟函数调用栈。手动模拟递归压栈出栈过程，解除系统栈大小的限制。

---

3. C 语言的 qsort() 函数？

• qsort 优先使用归并排序，在数据规模比较小的时候，以空间换时间。

• 当数据规模比较大时，qsort 会改为快速排序，以三数取中法来选取分区点。

• qsort 通过在堆上模拟函数调用栈来解决堆栈溢出问题。

• 当快速排序区间内元素小于等于 4 时，qsort 退化为插入排序。因为在小数据规模下， $O(n^2)$O(n2) 时间复杂度算法并不一定比 $O(nlogn)$O(nlogn) 的算法执行时间长。

---

4. 模拟栈的快速排序算法

int Partition(float data[], int left, int right)
{
    int i = left, j = left;
    int pivot = data[right];

    for (j = left; j < right; j++)
    {
        if (data[j] < pivot)
        {
            int temp = data[i];
            data[i] = data[j];
            data[j] = temp;
            i++;
        }
    }

    data[j] = data[i];
    data[i] = pivot;
    return i;
}

void Quick_Sort(float data[], int left, int right)
{
    if (left < right)
    {
        stack<int> s;
        s.push(left);
        s.push(right);

        while (!s.empty())
        {
            int j = s.top();
            s.pop();
            int i = s.top();
            s.pop();

            int mid = Partition(data, i, j);
            // 至少有两个元素
            if (mid-1 > i)
            {
                s.push(i);
                s.push(mid-1);
            }
            if (j > mid+1)
            {
                s.push(mid+1);
                s.push(j);
            }
        }
    }
}

5. 三路划分快速排序

针对有重复数据的情况，三路划分将数据分为三部分：小于主元的、等于主元的和大于主元的，然后递归调用的时候只对两端的数据再排序，而不用处理中间相等的情况。

void Quick_Sort_3_Way(float data[], int left, int right)
{
    if (left < right)
    {
        float pivot = data[right];
        int l = left - 1;
        int j = left;
        int r = right;

        /*
        [left, l] 小于主元
        [l+1, j] 等于主元
        [j+1, right] 大于主元
        */

        while (j < r)
        {
            if (data[j] < pivot)
            {
                swap(data[j], data[++l]);
                j++;
            }
            else if (data[j] > pivot)
                swap(data[j], data[--r]);
            else    j++;
        }
        swap(data[j], data[right]);
        Quick_Sort_3_Way(data, left, l);
        Quick_Sort_3_Way(data, j+1, right);
    }
}

参考资料-极客时间专栏《数据结构与算法之美》

获取更多精彩，请关注「seniusen」!