我正在尝试使用Cormen算法教科书编写快速排序算法.以下是我的代码.
class Quicksort
{
public void qSort(int[] a,int p,int r)
{
if(p<r)
{
int q = Partition(a,p,r);
qSort(a,q-1);
qSort(a,q+1,r);
}
}
private int Partition(int[] a,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,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
任何人都可以解释有什么问题.我完全按照“算法简介”一书中的说明实现了这段代码.谢谢.
解决方法
不,你没有直接复制它:)我在这里…
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中阅读它
