使用快速排序排序数组

Question

我有一个数组创建10个随机整数，然后使用quicksort排序它们..我的问题是，当我改变这个创建1,000,000随机整数它不会这样做...可以帮助吗？

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace RepeatAssignmentQ2 
{ 
class Program 
{ 
    static public int Partition(int[] myArray, int left, int right) 
    { 
     int pivot = myArray[left]; 
     while (true) 
     { 
      while (myArray[left] < pivot) 
       left++; 

      while (myArray[right] > pivot) 
       right--; 

      if (left < right) 
      { 
       int temp = myArray[right]; 
       myArray[right] = myArray[left]; 
       myArray[left] = temp; 
      } 
      else 
      { 
       return right; 
      } 

     } 
    } 

    static public void QuickSort_Recursive(int[] arr, int left, int right) 
    { 
     // For Recusrion 
     if (left < right) 
     { 
      int pivot = Partition(arr, left, right); 

      if (pivot > 1) 
       QuickSort_Recursive(arr, left, pivot - 1); 

      if (pivot + 1 < right) 
       QuickSort_Recursive(arr, pivot + 1, right); 
     } 
    } 

    static void Main(string[] args) 
    { 
     Random rnd = new Random(); 
     DateTime startTime = DateTime.Now; 

     int ind = 0; 
     int length = 1000000; 
     int[] myArray = new int[length]; 

     while (ind < 1000000) 
     { 
      myArray[ind] = rnd.Next(1000000); 
      ind++; 
     } 

     int lengthTwo = 10; 

     Console.WriteLine("QuickSort by recursive method"); 

     QuickSort_Recursive(myArray,0, lengthTwo - 1); 



     for (int i = 0; i < 1000000; i++) 
     { 

      Console.WriteLine(myArray[i]); 

     } 
     Console.WriteLine("Total Time: {0}\n", DateTime.Now - startTime); 
     Console.WriteLine(); 



    } 
} 
} 

由于

编辑 - 当我囤程序具有10个编号的数组它将显示它们，并让它们排序。当我将其更改为1,000,000并运行程序时，不显示任何内容。

编辑2 - 好吧，出于某种奇怪的原因它正在这样做。我改变了上面的代码来显示更改，它现在显示它随机生成的数字，但没有对它们进行排序。但是当IT人员只需要创建10个随机数就可以对其进行排序。

Answer 1

填充和排序1,000,000个元素仍然应该非常快。

在分区方法中，您的算法存在错误。 如果left比right较小你应该增加left，降低right：

if (left < right) 
{ 
    int temp = myArray[right]; 
    myArray[right] = myArray[left]; 
    myArray[left] = temp; 
    left++; 
    right--; 
} 

分析你的程序的行为，如果myArray[left]大于或等于pivot，myArray[right]较小或等于比pivot和left比right较小。 您有一个无限循环while (true)，因为两个while被忽略，而if不会更改left或right的值。 如果数组中有重复项，则会出现这种情况。例如，当您尝试用1,000个数字填充1,000,000个元素时，就会发生这种情况。

Btw。如果用变量length和lengthTwo替换为length，则代码会更好。 为什么？在这种情况下，当你想检查程序行为的更大阵列。更改一个变量的值比五个数字更容易。

我希望我能帮上忙。

Answer 2

请原谅我，但你等了多久？我怀疑填充1mil整数数组的while循环需要很长时间，因为它调用Next方法1,000,000次。您是否看到以下输出：'通过递归方法快速排序'？

Answer 3

我刚才在这迷迷糊糊中，错误的是这里

QuickSort_Recursive（myarray的1,0，lengthTwo - 1）;

它变化到

QuickSort_Recursive（myArray的，0，长度 - 1）;

对于你的分区我认识霍尔的算法（比其他快）https://cs.stackexchange.com/questions/11458/quicksort-partitioning-hoare-vs-lomuto这里是对他们俩的伪代码（你会看到我= P + 1和j = P-1开始，否则它的好）

Answer 4

虽然这个回复离提问时间很远，但对于阅读问题的任何人来说，以下内容都很有用。

与

在这里，在问题中提到，这将会对分区功能无限循环每当转动部件的两端相似（左，右）代码的问题是修改后的代码得到它working：

static int Partition(int[] myArray, int left, int right) 
    { 
     int pivot = myArray[left]; 
     while (true) 
     { 
      while (myArray[left] < pivot) 
       left++; 

      while (myArray[right] > pivot) 
       right--; 

      if (left < right && myArray[left] == myArray[right]) 
       left++; 
      else if (left < right) 
      { 
       int temp = myArray[right]; 
       myArray[right] = myArray[left]; 
       myArray[left] = temp; 
      } 
      else 
      { 
       return right; 
      } 

     } 
    }