快速排序划分算法 [英] QuickSort partition algorithm
问题描述
我想从编程算法Cormen教科书的快速排序算法。下面是我的code。
I am trying to program the quicksort algorithm from Cormen Algorithm Textbook. Below is my code.
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] + " ");
}
}
}
不过,我得到一个错误的输出,当我执行此code。
But, I am getting a wrong output when I execute this code.
Original Array : 5 4 7 2 1 9 3 6 10 8
Sorted Array : 1 4 5 2 6 7 3 8 9 10
任何人能请解释什么是错的。我已经实现了这个code完全按照给定的算法导论一书。谢谢你。
Can anyone please explain what is wrong. I have implemented this code exactly as given in "Introduction to algorithms" book. Thank you.
推荐答案
没有你没有直接复制它:)我在这里...
No you have not copied it directly :) I have it here...
for(int j=p; j<r-1; j++)
应
for(int j=p; j<r; j++)
或
for(int j=p; j <= r-1; j++)
这本书写道:
The book writes:
for j = p to r - 1
,其中包括的R - 1
。记住书中有数组是从1开始,而不是0,所以一般在书的算法应该是复制小心翼翼或阵列而从1。
which includes r - 1
. And remember the book has arrays which is starting from 1 and not 0. So generally the algorithms in the book should be "copied" with great care or with arrays which goes from 1.
编辑:关于算法信息的评论 书中的算法将最后一个元素作为支点。因此,这将使它成为一个可怕的算法已经排序的数组。它最终会为O(n ^ 2),所以任何人都不得在生产中使用这个算法(除非你知道自己在做什么,你的输入)作为阵列往往有所排序。 Java的内置的算法更聪明,你可以在Javadoc读到它
Info about the algorithm for a comment The algorithm in the book takes the last element as pivot. It will therefore make it a terrible algorithm for already sorted arrays. It will end up in O(n^2) so no one should use this algorithm in production (unless you know what you are doing and what your input is) as arrays tend to be somewhat sorted. Java's build-in algorithm is more clever and you can read about it in the Javadoc
这篇关于快速排序划分算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!