在 C# 中递归实现 QuickSort

Question

我开始学习算法，并尝试在 C# 中实现快速排序。这是我的代码：

class QuickSortDemo
{
    public void Swap(ref int InputA, ref int InputB)
    {
        InputA = InputA + InputB;
        InputB = InputA - InputB;
        InputA = InputA - InputB;
    }

    public int Partition(int[] InputArray, int Low, int High)
    {
        int Pivot = InputArray[Low];
        int LoopVariable1 = Low - 1;
        int LoopVariable2 = High + 1;
        while (true)
        {

            while (InputArray[--LoopVariable2] > Pivot) ;

            while (InputArray[++LoopVariable1] < Pivot) ;


            if (LoopVariable1 < LoopVariable2)
            {
                Swap(ref InputArray[LoopVariable1], ref InputArray[LoopVariable2]);
                for (int LoopVariable = Low; LoopVariable <= High; LoopVariable++)
                {
                    Console.Write(InputArray[LoopVariable] + " ");
                }
                Console.WriteLine();

            }
            else
            {
                for (int LoopVariable = Low; LoopVariable <= High; LoopVariable++)
                {
                    Console.Write(InputArray[LoopVariable] + " ");
                }
                Console.WriteLine();
                return LoopVariable2;
            }
        }
    }

    public void QuickSort(int[] InputArray,int Low, int High)
    {
        if (Low < High)
        {
            int Mid = Partition(InputArray, Low, High);
            QuickSort(InputArray, Low, Mid);
            QuickSort(InputArray, Mid + 1, High);
        }
    }
    public static void Main()
    {
        int[] InputArray = { 10, 5, 6, 8, 23, 19, 12, 17 };
        QuickSortDemo Demo = new QuickSortDemo();
        for (int LoopVariable = 0; LoopVariable < InputArray.Length; LoopVariable++)
        {
            Console.Write(InputArray[LoopVariable]+" ");
        }
        Console.WriteLine();

        Demo.QuickSort(InputArray, 0, InputArray.Length - 1);
        for (int LoopVariable = 0; LoopVariable < InputArray.Length; LoopVariable++)
        {
            Console.Write(InputArray[LoopVariable] + " ");
        }
        Console.WriteLine();
    }
}

出于某种原因，当我将数组中最右边的元素作为主元时，我无法使它工作。我不知道我做错了什么。如果有人可以解释为什么当我将最右边的元素作为支点时这不起作用，那将非常有帮助。据我了解，这应该适用于任何输入和任何枢轴元素。如果我错了，请纠正我。谢谢。

Answer 1

我仍然不能完全确定我理解了这个问题。但是当我将 Partition() 方法中的代码行从 int pivot = inputArray[low]; 更改为 int pivot = inputArray[high]; 时，我能够重现问题（无限递归），并且这样做似乎与您的叙述一致：

I can't get this to work when I take the rightmost element in the array as pivot.

如果我正确理解了这个问题，那么基本问题是当你改变你获得支点的位置时，你还需要在return调整新的中点时考虑到这一点。当前，您 return loopVariable2，从数组的下端选取枢轴时是正确的。但是如果你切换到从数组的上端选择枢轴，你需要 return loopVariable2 - 1.

另一个问题是，当您扫描时，您无条件地递增或递减相应的"loop variable"，无论当前索引是否已经在错误的分区。您需要先检查当前元素的位置，只有当该元素在正确的分区中时才调整索引。

这是 Partition() 方法的正确版本，其中使用 high 而不是 low 选择基准：

    public int Partition(int[] inputArray, int low, int high)
    {
        int pivot = inputArray[high];
        int loopVariable1 = low;
        int loopVariable2 = high;
        while (true)
        {

            while (inputArray[loopVariable2] > pivot) loopVariable2--;

            while (inputArray[loopVariable1] < pivot) loopVariable1++;


            if (loopVariable1 < loopVariable2)
            {
                Swap(ref inputArray[loopVariable1], ref inputArray[loopVariable2]);
                for (int loopVariable = low; loopVariable <= high; loopVariable++)
                {
                    Console.Write(inputArray[loopVariable] + " ");
                }
                Console.WriteLine();

            }
            else
            {
                for (int loopVariable = low; loopVariable <= high; loopVariable++)
                {
                    Console.Write(inputArray[loopVariable] + " ");
                }
                Console.WriteLine();
                return loopVariable2 - 1;
            }
        }
    }

无论哪种情况，请注意，效果是确保无论选择的主元值如何，您始终以这样的方式对数组进行分区，以确保在每一级递归中始终选择一个新的主元，从而防止无限循环。

顺便说一句，不管它值多少钱，我都不会像你那样实施 Swap() 。进行非临时变量交换是一个有趣的噱头，但这样做没有实际好处，而且确实会产生大量的代码维护和理解成本。此外，它只适用于整数类型；如果您想扩展排序实现以处理其他类型怎么办？例如。那些实施 IComparable 或您允许调用者提供 IComparer 实施的地方？

恕我直言，更好的 Swap() 方法如下所示：

    public void Swap<T>(ref T inputA, ref T inputB)
    {
        T temp = inputA;

        inputA = inputB;
        inputB = temp;
    }

Answer 2

快速排序：

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

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

            if (left < right)
                {
                int temp = numbers[right];
                numbers[right] = numbers[left];
                numbers[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);
        }
    }

在 C# 中递归实现 QuickSort

Implementing QuickSort recursively in C#

c#

quicksort