与快速排序算法混淆C＃

我一直在研究如何在C＃中为大学做快速排序。我几乎可以工作。只有几个数字没有按正确的顺序出现。 array：1,5,8,6,7,3,2,4,9 “sorted”into：1,5,4,6,2,3,7,8,9 instead of 1,2， 3,4,5,6,7,8,9。不知道在哪里，我在我的代码会错：与快速排序算法混淆C＃

int[] array4 = { 1, 5, 8, 6, 7, 3, 2, 4, 9}; 
QuickSort quick = new QuickSort(); 
quick.Quicksort(array4, 0, array4.Length - 1); 

public void Quicksort(int[] array, int left, int right) 
{ 
     int pivot, temp;      
     pivot = array[(left + right/2)]; 
     do 
     { 
      while ((array[left] < pivot) && (left < right)) 
       left++; 

      while ((pivot < array[right]) && (right > left)) 
       right--; 
      if (left <= right) 
      { 
       temp = array[left]; 
       array[left] = array[right]; 
       array[right] = temp; 
       left++; 
       right--; 
      } 
     } 
     while (left <= right); 

     if (left < right) Quicksort(array, left, right);    
     }    
}

感谢

来源

2016-12-03 Jonathan Mitchell

通常，当发生这种情况时，您不会在数组中的所有值中逗留。尝试更改输入数据并将'1'移动到列表的末尾。 – jdweng

您需要进行两个递归调用，一个用于左侧分区，另一个用于右侧。 – Lee

在你快速排序的方法，因为李的评论所指出的，你是不是调用带有的左侧和右侧部分的快速排序法分区/枢轴。

首先我相信你是不是在该行得到适当的支点：

pivot = array[(left + right/2)];

以上，师会先发生，所以它会分“右”两个再加入到“左”。这会给你一个错误的关键。它应该是：

pivot = array[(left + right)/2];

其次，当你进入快速排序的方法，你给出的起始索引值（左/右），并且使用这些变量来获得下一个支点。当你改变它们时，这将抛弃“左”和“右”STARTING索引。因此，您需要复制这些STARTING值并使用复制的值创建下一个分区/数据透视表。

以下是我对您的代码所做的更改，它似乎正常工作。

public static void Quicksort(int[] array, int left, int right) 
{ 
    int pivot, temp; 
    pivot = array[(left + right)/2]; 
    int originalLeft = left; 
    int originalRight = right; 
    do 
    { 
    while (array[left] < pivot) 
     left++; 

    while (pivot < array[right]) 
     right--; 
    if (left <= right) 
    { 
     temp = array[left]; 
     array[left] = array[right]; 
     array[right] = temp; 
     left++; 
     right--; 
    } 
    } 
    while (left <= right); 

    // note that the original left and right values are needed here 
    if (originalLeft < right) 
    Quicksort(array, originalLeft, right); 
    if (left < originalRight) 
    Quicksort(array, left, originalRight); 
}

希望这会有所帮助。

来源

2016-12-03 20:01:28 JohnG

你的建议已修复它。我看到我要去哪里错了。干杯！ –

与快速排序算法混淆C＃

回答

相关问题