algorithm - 快速排序实现中的错误

Question

我必须实现快速排序。来自 Programming Pearls这是代码:

public class Quick{
    public static void quicksort(int x[], int l, int u)
    {
        if (l>=u)
            return;
        int t = x[l];
        int i = l;
        int j = u;

        do
        {
            i++;
        } while (i<=u && x[i]<t);

        do
        {
            j--;
            if (i>=j) break;
        } while (x[j]>t);

        swap(x, i, j);
        swap(x, l, j);

        quicksort(x, l  , j-1);
        quicksort(x, j+1, u  );
    }

    public static void main(String[]args)
    {
        int x[] = new int[]{55,41,59,26,53,58,97,93};
        quicksort(x, 0, x.length-1);
        for (int i=0; i<x.length; i++)
        {
            System.out.println(x[i]);
        }
    }

    public static void swap(int x[], int i, int j)
    {
        int s = x[i];
        x[i] = x[j];
        x[j] = s;
    }
}

它不起作用。这是输出:

59
41
55
26
53
97
58
93

为什么它不起作用？

Answer 1

应该是:

int t=x[l]; 
int  i=l; 
->    int  j=u + 1; 

此外，您错误地翻译了伪代码:这是在 C# 中(与 C 非常相似，只需更改数组声明):

public static class Sort
{
    public static void quicksort(int[] x, int l, int u)
    {
        if (l >= u)
            return;

        int t = x[l];
        int i = l;
        int j = u + 1;

        while (true)  // In C, make this while(1)
        {
            do
            {
                i++;
            } while (i <= u && x[i] < t);

            do
            {
                j--;
            } while (x[j] > t);

            if (i >= j)
                break;

            swap(x, i, j);
        }

        swap(x, l, j);

        quicksort(x, l, j - 1);
        quicksort(x, j + 1, u);
    }


    public static void swap(int[] x, int i, int j)
    {
        int s = x[i];
        x[i] = x[j];
        x[j] = s;
    }

用这个调用:

    static void Main(string[] args)
    {
        int[] x = new int[] { 55, 41, 59, 26, 53, 58, 97, 93 };

        Sort.quicksort(x, 0, x.Length - 1);
        for (int i = 0; i < x.Length; i++)
        {
            Console.WriteLine(x[i]);
        }
    }

产生:

26
41
53
55
58
59
93
97