java 创建没有递归和堆栈的快速排序
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/29987995/
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
Creating quicksort without recursion and stack
提问by MaLiN2223
I have a task to write quicksort (on only posivite numbers) algorythm in Java (I can't use any imports but Scanner) but without recursion and without stack.
I have two question about it :
我有一项任务是在 Java 中编写快速排序（仅在正数上）算法（我不能使用任何导入，但扫描仪）但没有递归和堆栈。
我有两个问题：
- I do understeand iterative quicksort with stack and recursive version but i cannot imagine how to do it without it.
I have heard about some 'in place' implementation but i dont really get it - is it solution for my problem?
I would appreciate if anyone could show me a way to do it ( dont post implementation if you can, I just want to understeand it not copy someone's code) or recommend some book where I can find it ( or some similar problem ). Is implementing sort by insertion for some small arrays a good idea? If so how big should be N in this code :
if (arraySize < N) insertionSort else quickSort fi
- 我确实理解堆栈和递归版本的迭代快速排序，但我无法想象没有它怎么做。我听说过一些“就地”实施，但我真的不明白 - 它是我问题的解决方案吗？
如果有人能告诉我一种方法，我将不胜感激（如果可以，请不要发布实现，我只是想了解它而不是复制某人的代码）或推荐一些我可以找到它的书（或一些类似的问题）。 为一些小数组实现按插入排序是个好主意吗？如果是这样，这段代码中的 N 应该有多大：
if (arraySize < N) insertionSort else quickSort fi
采纳答案by MaLiN2223
Apparently my task was to find onlyposivite numbers, here is my solution:
显然我的任务是只找到正数，这是我的解决方案：
public static void quickSort(final int size) {
int l = 0;
int r = size - 1;
int q, i = 0;
int tmpr = r;
while (true) {
i--;
while (l < tmpr) {
q = partition(l, tmpr);
arr[tmpr] = -arr[tmpr];
tmpr = q - 1;
++i;
}
if (i < 0)
break;
l++;
tmpr = findNextR(l, size);
arr[tmpr] = -arr[tmpr];
}
}
private static int findNextR(final int l, final int size) {
for (int i = l; i < size; ++i) {
if (arr[i] < 0)
return i;
}
return size - 1;
}
private static int partition(int l, int r) {
long pivot = arr[(l + r) / 2];
while (l <= r) {
while (arr[r] > pivot)
r--;
while (arr[l] < pivot)
l++;
if (l <= r) {
long tmp = arr[r];
arr[r] = arr[l];
arr[l] = tmp;
l++;
r--;
}
}
return l;
}
My array to sort is an static array in my class. It is based on finding and creating negative numbers. Partition is created by using middle element in array but using median is also good (it depends on array). I hope someone will find this usefull.
我要排序的数组是我班级中的静态数组。它基于查找和创建负数。分区是通过使用数组中的中间元素创建的，但使用中位数也不错（这取决于数组）。我希望有人会发现这很有用。
回答by David Lilljegren
Just as a reference the Java8 implementation of Arrays.sort(int[]) uses a threshold of 47, anything less than that is sorted using insertion. Their quick sort implementation is however very complex with some initial overhead, so look upon 47 as an upper limit.
正如参考，Arrays.sort(int[]) 的 Java8 实现使用阈值 47，任何小于该阈值的都使用插入进行排序。然而，它们的快速排序实现非常复杂，有一些初始开销，因此将 47 作为上限。
回答by Mike Robinson
A Google of "non-recursive quicksort" produced a slew of answers ... including this one: Non recursive QuickSort"Your language may vary," but the basic principle won't.
谷歌的“非递归快速排序”产生了大量答案......包括这个： 非递归快速排序“你的语言可能会有所不同”，但基本原则不会。
I personally think that, if you're going to sort something, you might as well use Quicksort in all cases . . .
我个人认为，如果您要对某些内容进行排序，则最好在所有情况下都使用 Quicksort。. .
Unless, of course, you can simply use a sort()function in your favorite target-language and leave it to the language implementors to have chosen a clever algorithm (uhhhh, it's probably Quicksort...)for you. If you don't haveto specify an algorithm to do such a common task, "don't!" :-)
当然，除非您可以简单地使用sort()您最喜欢的目标语言中的函数并将其留给语言实现者来为您选择一个聪明的算法（呃，它可能是快速排序......）。如果不具备指定的算法做了这样一个共同的任务，“不！” :-)
