与快速排序算法 C# 混淆

Question

我一直在为大学研究如何在 C# 中进行快速排序。我快搞定了 working.Only 一些数字没有按正确的顺序出现。数组：1,5,8,6,7,3,2,4,9 "sorted" 变成：1,5,4,6,2,3,7,8,9 而不是 1、2、3、4、5、6、7、8、9。不确定我的代码哪里出错了：

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);              
        }            
 }

谢谢

Answer 1

在您的快速排序方法中，正如 Lee 的评论所指出的，您没有使用 partition/pivot 的左右部分调用快速排序方法。

首先，我确信您没有在直线上获得正确的支点：

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

上面，除法会先发生，所以它会将“右”除以二然后加上“左”。这会给你错误的支点。应该是：

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

其次，当您进入快速排序方法时，系统会为您提供起始索引值 (left/right)，您可以使用这些变量来获取下一个主元。当您更改它们时，这将丢弃“左”和“右”STARTING 索引。因此，您需要复制这些起始值并使用复制的值创建下一个 partition/pivot.

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

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);
}

希望这对您有所帮助。

与快速排序算法 C# 混淆

confused with Quick sort algorithm C#

c#

quicksort