随机快速排序 C#

Question

我正在尝试在 C# 上使用随机基准分析快速排序算法。这是我要测试的代码：

//begeeben.wordpress.com/2012/08/22/randomized-quick-sort-in-c/ using System; using System.Collections.Generic; using System.Text; using System.Diagnostics; class Quicksort {
    public static void RandomizedQuickSort(int[] input, int left, int right)
    {
        if (left < right)
        {
            int q = RandomizedPartition(input, left, right);
            RandomizedQuickSort(input, left, q - 1);
            RandomizedQuickSort(input, q + 1, right);
        }
    }
    private static int RandomizedPartition(int[] input, int left, int right)
    {
        Random random = new Random();
        int i = (left + random.Next()) % (right-left+1);

        int pivot = input[i];
        input[i] = input[right];
        input[right] = pivot;

        return Partition(input, left, right);
    }
    private static int Partition(int[] input, int left, int right)
    {
        int pivot = input[right];
        int temp;

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

        input[right] = input[i+1];
        input[i+1] = pivot;

        return i;
    }
    static void Main(string[] args)
    {
        Random random = new Random();
        Stopwatch stopWatch;
        int []array;
        int size = 10;
        for (int j = 1; j < 7; ++j)
        {
            stopWatch = Stopwatch.StartNew();
            array = new int[size];
            for (int i = 0; i < 10; ++i) array[i] = random.Next(0, 300);
            stopWatch.Start();
            RandomizedQuickSort(array, 0, size-1);
            stopWatch.Stop();
            Console.WriteLine("Number of millisec to sort " + size + " elements: " + stopWatch.ElapsedMilliseconds);
            size = size * 10;
        }
    } 
}

一切正常，直到我尝试对包含 10,000,000 个元素的数组进行排序。那时我收到堆栈溢出异常。我曾尝试使用较小的整数，但这也导致我遇到堆栈溢出问题。看起来当代码终止时，左和右都等于零。但是，合并排序异常不会捕获到这个吗？

~更新：问题是数组太大，我已经用完了整个堆！为了解决这个问题，我不得不从递归算法切换到迭代算法。

Answer 1

C# 的最大堆栈大小为 1Mb，您正在用完它。这只是递归实现的内置限制。

您有 3 个解决方案：
1) 构建算法的迭代版本（性能最高）
2) 增加筹码量，例如：

Thread T = new Thread(threadEntryPoint, stackSizeInBytes);
T.Start();

3) 将您的分析限制在该算法可以处理的列表大小内。

随机快速排序 C#

Randomized quicksort C#

c#

stack-overflow

arrays

quicksort

array-algorithms