随机快速排序C＃

问题描述：

我试图分析快速排序算法与C＃随机支点。这是我试图测试的代码：随机快速排序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个元素的数组进行排序。在那一点上，我得到一个堆栈溢出异常。我曾尝试使用较小的整数，但这也导致了堆栈溢出问题。看起来代码终止时，左右两者都等于零。但是，合并排序异常不会引发这种情况吗？

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

当你做一个函数调用有点堆栈被分配并没有得到释放，直到函数退出。通过递归，您可以轻松地以这种方式吃掉堆栈（tail-recursion是个例外）。 [RuntimeHelpers.EnsureSufficientExecutionStack方法（）]（https://msdn.microsoft.com/en-us/library/system.runtime.compilerservices.runtimehelpers.ensuresufficientexecutionstack.aspx）可以帮助验证这一点。 –

您可以实现算法的迭代版本。递归应避免实施像快速排序，fibonacchi等算法时，递归是伟大的，当你处理递归类型，如树 – oldovets

答

C＃有一个1MB的最大堆栈大小和你使用它的所有行动。这只是递归实现的内置限制。

你有3个解决方案：
1）构建算法的迭代版本（最高效的）
2）增加你的堆栈大小，一样的东西：

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

3）限制你的分析，列出这个算法可以处理的大小。

随机快速排序C＃

相关推荐