c# - C# 中的这个 QuickSort 算法有什么问题？

Question

遗憾的是，我在使用快速排序时也遇到了问题。我已经与其他学生讨论过并尝试了标准的故障排除方法。但是我找不到我做错了什么......

static int partition(int[] A)
    {
        int pivot, i, j;
        i = 0;
        j = A.Length;
        pivot = A[i];

        do
        {
            do
            {
                i++;
            }
            while (A[i] < pivot || i < j);
            do
            {
                j--;
            }
            while (A[j] > pivot);

            swap(ref A[i], ref A[j]);
        }
        while (i < j);

        if (i <= j)
        {
            swap(ref A[i], ref A[j]);
            swap(ref A[0], ref A[j]);
        }

        return j;
    }

    static void swap(ref int a, ref int b)
    {
        int aCopy = a;
        a = b;
        b = aCopy;
    }

    static int[] QuickSort(int[] A)
    {
        int s;
        int left = 0;
        int right = A.Length;
        int[] B, C;

        if (A.Length == 0 || A.Length == 1)
            return A;
        else
        {
            s = partition(A);
            B = new int[s];
            C = new int[right - s];

            for (int i = left; i < s; i++)
            {
                B[i - left] = A[i];
            }
            for (int i = s; i < right; i++)
            {
                C[i - s] = A[i];
            }

            QuickSort(B);
            QuickSort(C);
            return A;
        }
    }

调试器不断给我一个带有 j 变量的“IndexOutOfRangeException”。我试过调整

while (A[i] < pivot || i < j);

部分。但这并没有做任何事情(好吧，它导致了一次 StackOverflowException)。

Answer 1

您有 j = A.Length，但它实际上应该是 j = A.Length - 1(基于您使用的循环)。