CLRS快速排序-工作不正常

Question

我正在尝试实现经典CLRS书中给出的快速排序算法。我在我的C#程序中精确地实现了它.但是输出没有排序。以下是我的全部代码，以及输出：

using System;

namespace clrs
{
    class MainClass
    {

        public static void Main (string[] args)
        {
            int[] numbers = { 2, 1, 4 };
            Console.WriteLine("unsorted: " + string.Join(",", numbers));
            quicksort (numbers, 0, numbers.Length-1);
            Console.WriteLine("sorted: " + string.Join(",", numbers));
            Console.WriteLine("");

            numbers = new int[]{ 7, 2, 1, 6, 1 };
            Console.WriteLine("unsorted: " + string.Join(",", numbers));
            quicksort (numbers, 0, numbers.Length-1);
            Console.WriteLine("sorted: " + string.Join(",", numbers));
            Console.WriteLine("");

            numbers = new int[]{ 2,8,7,1,3,5,6,4 };
            Console.WriteLine("unsorted: " + string.Join(",", numbers));
            quicksort (numbers, 0, numbers.Length-1);
            Console.WriteLine("sorted: " + string.Join(",", numbers));
            Console.WriteLine("");

            numbers = new int[]{ 2, 33, 6, 9, 8, 7, 1, 2, 5, 4, 7 };    
            Console.WriteLine("unsorted: " + string.Join(",", numbers));
            quicksort (numbers, 0, numbers.Length-1);
            Console.WriteLine("sorted: " + string.Join(",", numbers));
            Console.WriteLine("");
        }

        public static void quicksort(int[] a, int p, int r){
            int q;

            if (p < r){
                q = partition (a, p, r);
                quicksort(a, p, q-1);
                quicksort(a, q+1, r);
            }
        }

        public static int partition(int[] a, int p, int r){
            int x = a[r];
            int i = p - 1;

            for (int j=p; j<r-1; j++){
                if(a[j] <= x){
                    i = i + 1;

                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
            }
            int temp1 = a[i+1];
            a[i+1] = a[r];
            a[r] = temp1;

            return (i+1);
        }
    }
}

产出如下：

unsorted: 2,1,4
sorted: 2,4,1

unsorted: 7,2,1,6,1
sorted: 1,1,2,7,6

unsorted: 2,8,7,1,3,5,6,4
sorted: 2,3,1,4,5,7,8,6

unsorted: 2,33,6,9,8,7,1,2,5,4,7
sorted: 1,2,5,6,7,2,7,8,9,33,4

我已经实现了快速排序，正如它是在CLRS，第三版。我的代码编译，但输出没有完全排序。

我做错了什么？或者CLRS的psuedocode中有错误(非常不可能)？

请帮帮忙！

Answer 1

我叫恶作剧..。好像有人打错字了

这

for (int j=p; j<r-1; j++){

应该是这个

for (int j=p; j<r; j++){

测试在这里

https://dotnetfiddle.net/XgIOpx

供参考

快速排序

这是来自wiki的Lomuto分区算法。

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p - 1 )
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo - 1    
    for j := lo to hi - 1 do
        if A[j] < pivot then
            i := i + 1
            swap A[i] with A[j]
    swap A[i + 1] with A[hi]
    return i + 1

但是，您需要特别注意

for j := lo to hi - 1 do   // note the - 1
    if A[j] < pivot then   // and <

它需要是- 1或<=，而不是两者兼而有之。