创建没有递归和堆栈的快速排序

Question

我的任务是在 Java 中编写快速排序（仅在正数上）算法（我不能使用任何导入，但 Scanner）但没有递归和堆栈。
我有两个问题：

我了解堆栈和递归版本的迭代快速排序，但我无法想象没有它该怎么做。我听说过一些 'in place' 实施，但我不太明白 - 它能解决我的问题吗？
如果有人能告诉我一种方法，我将不胜感激（如果可以的话，不要 post 实现，我只是想理解它而不是复制某人的代码）或推荐一些我可以找到它的书（或一些类似的问题).
对一些小数组实施插入排序是个好主意吗？如果是这样，此代码中的 N 应该有多大：
```
if (arraySize < N)
    insertionSort
else 
    quickSort
fi
```

Answer 1

"non-recursive quicksort" 的 Google 产生了一系列答案......包括这个：Non recursive QuickSort "Your language may vary," 但基本原理不会。

我个人认为，如果您要对某些内容进行排序，您最好在所有情况下都使用快速排序。 . .

当然，除非你可以简单地使用你最喜欢的目标语言中的 sort() 函数，然后让语言实现者选择一个聪明的算法 （呃，这可能是Quicksort...) 给你。如果您没有指定算法来完成这种常见任务，"don't!" :-)

Answer 2

作为参考，Arrays.sort(int[]) 的 Java8 实现使用阈值 47，任何小于该阈值的都使用插入进行排序。然而，他们的快速排序实现非常复杂，有一些初始开销，因此将 47 视为上限。

Answer 3

显然我的任务是找到只有个正数，这是我的解决方案：

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;
}

我要排序的数组是 class 中的静态数组。它基于查找和创建负数。分区是通过使用数组中的中间元素创建的，但使用中位数也很好（它取决于数组）。我希望有人会发现这很有用。

创建没有递归和堆栈的快速排序

Creating quicksort without recursion and stack

java

quicksort