创建快速排序而无需递归和堆栈

Question

我有一个任务要用Java（仅在posivite编号上）编写quicksort（仅在posivite编号上）算法（除了Scanner，我不能使用任何导入），但是没有递归并且没有堆栈。
我有两个问题：

1. 我确实使用堆栈和递归版本进行迭代迭代快速排序，但是我无法想象没有它怎么做。我听说过一些“就地”实施，但是我真的不明白—它可以解决我的问题吗？
   如果有人可以向我展示一种实现方法（如果可以的话，请不要发布实现，我只是想让它不要复制别人的代码）或推荐我可以找到它的书（或类似问题），我将不胜感激。

2. 通过插入一些小的数组来实现排序是个好主意吗？如果是这样，则此代码中的N应该有多大：

   if (arraySize < N)
       insertionSort
   else 
       quickSort
   fi
   

Answer 1

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

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

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