import java.util.ArrayList;
public class MyQuickSort {
/**
* @param args
*/
public static void main(String[] args) {
//int[] a = { 1, 23, 45, 2, 8, 134, 9, 4, 2000 };
int a[]={23,44,1,2009,2,88,123,7,999,1040,88};
quickSort(a, 0, a.length - 1);
System.out.println(a);
ArrayList al = new ArrayList();
}
public static void quickSort(int[] a, int p, int r)
{
if(p<r)
{
int q=partition(a,p,r);
quickSort(a,p,q);
quickSort(a,q+1,r);
}
}
private static int partition(int[] a, int p, int r) {
int x = a[p];
int i = p-1 ;
int j = r+1 ;
while (true) {
i++;
while ( i< r && a[i] < x)
i++;
j--;
while (j>p && a[j] > x)
j--;
if (i < j)
swap(a, i, j);
else
return j;
}
}
private static void swap(int[] a, int i, int j) {
// TODO Auto-generated method stub
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
#1 楼
如果该算法取自一本书，那么它可能会尽可能地好。因此，只要您遵循这封信，那么在您的实现中就不应该存在任何问题。但是我认为可以改进的一件事是启动排序的接口。当我考虑对集合进行排序时，我希望提供一些东西，当然是集合，可能还有比较器。需要传递实现特定值的任何其他内容对我来说都是“错误的”。如果这些索引代表要排序的值的起始和终止范围可能没问题，但是我还是将其作为单独的重载。
另一方面，您的实现需要收集和索引所需的该算法起作用。这不是一个理想的接口，因为您必须记住要传递某些值来执行排序，而实际上可以为我计算它们。我将公开一个仅接受要进行排序的集合的重载，该重载将使用正确的参数调用实际的实现。
此外，即使这是众所周知的快速排序算法，我仍然会提供更好的方法变量名。个人喜好在这里不是问题。
// this overload is the public interface to do the sort
public static void quickSort(int[] collection)
{
quickSort(collection, 0, collection.length - 1);
}
// note: method is now private
private static void quickSort(int[] collection, int pivotIndex, int rangeIndex)
{
// etc...
}
评论
\ $ \ begingroup \ $
+1为变量名，这将使代码更清晰。代码被很好地分成函数，而不是我们经常看到的混乱（特别是没有人针对）。
\ $ \ endgroup \ $
–埃里克·卡尔
2011年8月10日23:05
#2 楼
我看到一个小改进。代替...i++;
while ( i< r && a[i] < x)
i++;
j--;
while (j>p && a[j] > x)
j--;
...你可以这样写：
do {
i++;
} while (i < r && a[i] < x);
do {
j--;
} while (j > p && a[j] > x);
杰夫是对的关于公共接口。
#3 楼
如果您尝试对已排序的大于20000的数组大小进行排序，则会导致堆栈溢出。遇到大型排序数组时，分区存在问题。#4 楼
看起来确实不错，但是当有人不得不再次对快速排序进行编码时，我总是建议您遵循以下准则：随机化：当数据几乎排序时，随机排列键可以避免O（n²）。树的中位数：使用第一个，中间和最后一个元素的中位数来选择枢轴。数据越大，样本越多。
保留小的子数组用于插入排序：完成Quicksort递归并在少于20个元素时切换到插入排序：
// Insertion sort on smallest arrays
if (rangeIndex < 20) {
for (int i=pivotIndex; i < rangeIndex + pivotIndex; i++)
for (int j=i; j > pivotIndex && x[j-1]>x[j]; j--)
swap(x, j, j-1);
return;
}
先进行较小的分区：递归只需要O（logn）空间
所有这些技巧都来自史蒂文·斯基埃纳（Steven Skiena）的一本精妙的算法设计手册。 br />
#5 楼
我看到另一个改进。我认为更合理的做法是认为标记（i和j）应在交换完成后移动。它清除了几行代码，更有意义。private static int partition(int[] a, int p, int r) {
int x = a[p];
int i = p;
int j = r;
while (true) {
while (i < r && a[i] < x)
i++;
while (j > p && a[j] > x)
j--;
if (i < j) {
swap(a, i, j);
i++;
j--;
} else {
return j;
}
}
}
评论
这是O（n log n）而不是log n它不会因递归而扩展：JVM没有尾部调用优化，它只会将方法调用堆栈增长到与要排序的数组成比例的大小，并且对于太大的数组将失败。 （甚至对于确实具有尾部调用优化功能的语言/平台，我认为他们也无法将其实际应用到此代码中）
我认为值得一提的是，分区方法并未使数据透视表最终到达目的地，这与可以在维基百科上查看的经典QuickSort不同。