java - QuickSort分区算法

Question

我正在尝试编写 Cormen 算法教科书中的快速排序算法。下面是我的代码。

class Quicksort
{
    public void qSort(int[] a, int p, int r)
    {
        if(p<r)
        {
            int q = Partition(a, p,r);
            qSort(a, p, q-1);
            qSort(a, q+1, r);
        }
     }

     private int Partition(int[] a, int p, int r)
     {
         int x = a[r];

         int i = p-1;
         int temp=0;

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

         temp = a[i+1];
         a[i+1] = a[r];
         a[r] = temp;
         return (i+1);
     }
}

public class QuickSortTest
{
     public static void main(String[] args)
     {
         Quicksort qsort = new Quicksort();
         int[] array = {5, 4, 7, 2, 1, 9, 3, 6, 10, 8};

         System.out.print("Original  Array : ");
         for(int i=0; i<array.length;i++)
         {
             System.out.print(array[i] + " ");
         }

         int length = array.length;

         qsort.qSort(array, 0, length-1);

         System.out.print("Sorted  Array : ");
         for(int i=0; i<array.length;i++)
         {
             System.out.print(array[i] + " ");
         }
     }
}

但是，当我执行这段代码时，我得到了一个错误的输出。

Original  Array : 5 4 7 2 1 9 3 6 10 8 
Sorted  Array : 1 4 5 2 6 7 3 8 9 10 

谁能解释一下哪里出了问题。我已经完全按照“算法简介”一书中给出的方式实现了这段代码。谢谢。

Answer 1

不，你没有直接复制它:)我有它......

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

应该是

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

或

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

书中写道:

for j = p to r - 1

其中包括 r - 1。请记住，书中有从 1 而不是 0 开始的数组。因此，通常应该非常小心地“复制”书中的算法，或者使用从 1 开始的数组。

编辑:关于评论算法的信息书中的算法以最后一个元素为基准。因此，对于已经排序的数组，这将使其成为一个糟糕的算法。它将以 O(n^2) 结束，所以没有人应该在生产中使用这个算法(除非你知道你在做什么以及你的输入是什么)因为数组往往是排序的。 Java 的内置算法更聪明，您可以在 Javadoc 中阅读它