Java 快速排序分区算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3444382/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
QuickSort partition algorithm
提问by Race
I am trying to program the quicksort algorithm from Cormen Algorithm Textbook. Below is my code.
我正在尝试编写 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] + " ");
}
}
}
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
Can anyone please explain what is wrong. I have implemented this code exactly as given in "Introduction to algorithms" book. Thank you.
任何人都可以请解释什么是错的。我已经完全按照“算法简介”一书中的说明实现了这段代码。谢谢你。
采纳答案by Lasse Espeholt
No you have not copied it directly :) I have it here...
不，您没有直接复制它:) 我在这里...
for(int j=p; j<r-1; j++)
should be
应该
for(int j=p; j<r; j++)
or
或者
for(int j=p; j <= r-1; j++)
The book writes:
书中写道：
for j = p to r - 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.
其中包括r - 1. 请记住，这本书有从 1 开始而不是从 0 开始的数组。因此，通常应该非常小心地“复制”书中的算法或使用从 1 开始的数组。
Edit: Info about the algorithm for a commentThe 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
编辑：有关评论算法的信息本书中的算法将最后一个元素作为枢轴。因此，对于已经排序的数组，它会成为一个糟糕的算法。它将以 O(n^2) 结束，所以没有人应该在生产中使用这个算法（除非你知道你在做什么以及你的输入是什么），因为数组往往有点排序。Java 的内置算法更聪明，你可以在 Javadoc 中阅读它
回答by whaley
If you want some reference on how to implement quick sort, you could try checking the actual source code for Arrays.sort(*) in the jdk, which is a modified version of quick sort. (http://www.oracle.com/technetwork/java/javase/downloads/index.htmlto download if you don't already have src.zip in your jdk installation).
如果你想要一些关于如何实现快速排序的参考，你可以尝试检查 jdk 中 Arrays.sort(*) 的实际源代码，这是快速排序的修改版本。（http://www.oracle.com/technetwork/java/javase/downloads/index.html下载，如果您的 jdk 安装中还没有 src.zip ）。
回答by mdev
Providing one more implementation in java. It is also based on the same algorithm and takes care of duplicate elements in the array too.
在java中提供另一种实现。它也基于相同的算法并处理数组中的重复元素。
public void sort( int[] inputArray, int lo, int high){
int pivotIndex = partition(inputArray,lo,high);
System. out .println("Got PivotIndex as " + pivotIndex);
if (lo < pivotIndex -1)
sort(inputArray,lo,pivotIndex - 1);
if (pivotIndex+1 < high)
sort(inputArray,pivotIndex+1,high);
return ;
}
private int partition( int[] inputArray, int leftPtr,int rightPtr)
{
printArray(inputArray);
int pivot = inputArray[leftPtr];
while (leftPtr<rightPtr){
while (inputArray[leftPtr]<pivot)
leftPtr++;
while (inputArray[rightPtr]>pivot)
rightPtr--;
if (leftPtr<rightPtr)
{
exchange(inputArray,leftPtr,rightPtr);
//Cases which have repeated numbers...
if (inputArray[leftPtr] == inputArray[rightPtr])
leftPtr++;
}
}
return leftPtr;//return any one
}
