2.3.20 #

解答 #

事实上就是用一个栈保存每次切分后的子数组下标。

关键代码如下：

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

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

        if (hi <= lo)
            continue;

        var 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 #

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

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

            if (hi <= lo)
                continue;

            var 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;
        var 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)
    {
        var random = new Random();
        for (var i = 0; i < a.Length; i++)
        {
            var r = i + random.Next(a.Length - i);
            var temp = a[i];
            a[i] = a[r];
            a[r] = temp;
        }
    }
}

测试用例

var quickNormal = new QuickSort();
var quickNonRecursive = new QuickSortNonRecursive();
var arraySize = 200000; // 初始数组大小。
const int trialTimes = 4; // 每次实验的重复次数。
const int trialLevel = 5; // 双倍递增的次数。

Console.WriteLine("n\tnon-recursive\tnormal\tratio");
for (var i = 0; i < trialLevel; i++)
{
    double timeRecursive = 0;
    double timeNormal = 0;
    for (var j = 0; j < trialTimes; j++)
    {
        var a = SortCompare.GetRandomArrayInt(arraySize);
        var 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 库