2.3.20

上次更新:2020-03-16
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

事实上就是用一个栈保存每次切分后的子数组下标。
关键代码如下:

/// <summary>
/// 用快速排序对数组 a 进行升序排序。
/// </summary>
/// <typeparam name="T">需要排序的类型。</typeparam>
/// <param name="a">需要排序的数组。</param>
public override void Sort<T>(T[] a)
{
    Shuffle(a);
    Stack<int> stack = new Stack<int>();
    stack.Push(0);
    stack.Push(a.Length - 1);

    while (stack.Count != 0)
    {
        // 压入顺序是先 lo,再 hi,故弹出顺序是先 hi 再 lo
        int hi = stack.Pop();
        int lo = stack.Pop();

        if (hi <= lo)
            continue;

        int j = Partition(a, lo, hi);

        // 让较大的子数组先入栈(先排序较小的子数组)
        if (j - lo > hi - j)
        {
            stack.Push(lo);
            stack.Push(j - 1);

            stack.Push(j + 1);
            stack.Push(hi);
        }
        else
        {
            stack.Push(j + 1);
            stack.Push(hi);

            stack.Push(lo);
            stack.Push(j - 1);
        }
    }
    Debug.Assert(IsSorted(a));
}

由于栈操作比函数调用操作耗费时间更长,因此测试后的结果会比原有快排慢一些。

代码

QuickSortNonRecursive

using System;
using System.Diagnostics;
using Quick;

namespace _2._3._20
{
    /// <summary>
    /// 快速排序类。
    /// </summary>
    public class QuickSortNonRecursive : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortNonRecursive() { }

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            Shuffle(a);
            Stack<int> stack = new Stack<int>();
            stack.Push(0);
            stack.Push(a.Length - 1);

            while (stack.Count != 0)
            {
                // 压入顺序是先 lo,再 hi,故弹出顺序是先 hi 再 lo
                int hi = stack.Pop();
                int lo = stack.Pop();

                if (hi <= lo)
                    continue;

                int j = Partition(a, lo, hi);

                // 让较大的子数组先入栈(先排序较小的子数组)
                if (j - lo > hi - j)
                {
                    stack.Push(lo);
                    stack.Push(j - 1);

                    stack.Push(j + 1);
                    stack.Push(hi);
                }
                else
                {
                    stack.Push(j + 1);
                    stack.Push(hi);

                    stack.Push(lo);
                    stack.Push(j - 1);
                }
            }
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 对数组进行切分,返回枢轴位置。
        /// </summary>
        /// <typeparam name="T">需要切分的数组类型。</typeparam>
        /// <param name="a">需要切分的数组。</param>
        /// <param name="lo">切分的起始点。</param>
        /// <param name="hi">切分的末尾点。</param>
        /// <returns>枢轴下标。</returns>
        private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;
            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v))
                    if (i == hi)
                        break;
                while (Less(v, a[--j]))
                    if (j == lo)
                        break;
                if (i >= j)
                    break;
                Exch(a, i, j);
            }
            Exch(a, lo, j);
            return j;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        private void Shuffle<T>(T[] a)
        {
            Random random = new Random();
            for (int i = 0; i < a.Length; i++)
            {
                int r = i + random.Next(a.Length - i);
                T temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }
    }
}

测试用例

using System;
using Quick;

namespace _2._3._20
{
    /*
     * 2.3.20
     * 
     * 非递归的快速排序。
     * 实现一个非递归的快速排序,
     * 使用一个循环来将弹出栈的子数组切分并将结果子数组重新压入栈。
     * 注意:
     * 先将较大的子数组压入栈,这样就可以保证栈最多只会有 lgN 个元素。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            QuickSort quickNormal = new QuickSort();
            QuickSortNonRecursive quickNonRecursive = new QuickSortNonRecursive();
            int arraySize = 200000;                         // 初始数组大小。
            const int trialTimes = 4;                       // 每次实验的重复次数。
            const int trialLevel = 5;                       // 双倍递增的次数。

            Console.WriteLine("n\tnon-recursive\tnormal\tratio");
            for (int i = 0; i < trialLevel; i++)
            {
                double timeRecursive = 0;
                double timeNormal = 0;
                for (int j = 0; j < trialTimes; j++)
                {
                    int[] a = SortCompare.GetRandomArrayInt(arraySize);
                    int[] b = new int[a.Length];
                    a.CopyTo(b, 0);
                    timeNormal += SortCompare.Time(quickNormal, b);
                    timeRecursive += SortCompare.Time(quickNonRecursive, a);

                }
                timeRecursive /= trialTimes;
                timeNormal /= trialTimes;
                Console.WriteLine(arraySize + "\t" + timeRecursive + "\t\t" + timeNormal + "\t" + timeRecursive / timeNormal);
                arraySize *= 2;
            }
        }
    }
}

另请参阅

Quick 库

上一题 下一题