algorithm - 快速排序：迭代或递归

Question

我了解了快速排序以及如何在递归和迭代方法中实现它。
在迭代方法中：

1. 将范围 (0...n) 推入堆栈
2. 使用枢轴对给定数组进行分区
3. 弹出顶部元素。
4. 如果范围有多个元素，则将分区（索引范围）推入堆栈
5. 做以上3步，直到栈为空

递归版本是wiki中定义的正常版本。

我了解到递归算法总是比迭代算法慢。
那么，就时间复杂度而言，哪种方法更受欢迎（内存不是问题）？
哪一个速度足够快，可以在编程比赛中使用？
c++ STL sort() 是否使用递归方法？

Answer 1

就（渐近）时间复杂度而言 - 它们都是相同的。

“递归比迭代要慢”——这句话背后的原因是递归堆栈的开销（保存和恢复调用之间的环境）。
但是 - 这些是固定数量的操作，而不改变“迭代”的数量。

递归和迭代快速排序都是O(nlogn) 平均情况和O(n^2) 最坏情况。

---

编辑：

只是为了好玩，我运行了一个带有附加到帖子的（java）代码的基准测试，然后我运行了wilcoxon 统计测试，以检查运行时间确实不同的概率是多少

结果可能是决定性的（P_VALUE=2.6e-34, https://en.wikipedia.org/wiki/P-value。请记住，P_VALUE 是 P(T >= t | H) 其中 T 是检验统计量， H 是原假设）。但答案不是你所期望的。
迭代求解的平均值为 408.86 ms，递归求解的平均值为 236.81 ms

（注意 - 我使用Integer而不是int作为参数recursiveQsort()- 否则递归会取得更好的效果，因为它不必将很多整数装箱，这也很耗时 - 我这样做是因为迭代解决方案别无选择，但这样做。

因此 - 您的假设不正确，递归解决方案比 P_VALUE=2.6e-34 的迭代解决方案更快（对于我的机器和 java 来说）。

public static void recursiveQsort(int[] arr,Integer start, Integer end) { 
    if (end - start < 2) return; //stop clause
    int p = start + ((end-start)/2);
    p = partition(arr,p,start,end);
    recursiveQsort(arr, start, p);
    recursiveQsort(arr, p+1, end);

}

public static void iterativeQsort(int[] arr) { 
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(0);
    stack.push(arr.length);
    while (!stack.isEmpty()) {
        int end = stack.pop();
        int start = stack.pop();
        if (end - start < 2) continue;
        int p = start + ((end-start)/2);
        p = partition(arr,p,start,end);

        stack.push(p+1);
        stack.push(end);

        stack.push(start);
        stack.push(p);

    }
}

private static int partition(int[] arr, int p, int start, int end) {
    int l = start;
    int h = end - 2;
    int piv = arr[p];
    swap(arr,p,end-1);

    while (l < h) {
        if (arr[l] < piv) {
            l++;
        } else if (arr[h] >= piv) { 
            h--;
        } else { 
            swap(arr,l,h);
        }
    }
    int idx = h;
    if (arr[h] < piv) idx++;
    swap(arr,end-1,idx);
    return idx;
}
private static void swap(int[] arr, int i, int j) { 
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

public static void main(String... args) throws Exception {
    Random r = new Random(1);
    int SIZE = 1000000;
    int N = 100;
    int[] arr = new int[SIZE];
    int[] millisRecursive = new int[N];
    int[] millisIterative = new int[N];
    for (int t = 0; t < N; t++) { 
        for (int i = 0; i < SIZE; i++) { 
            arr[i] = r.nextInt(SIZE);
        }
        int[] tempArr = Arrays.copyOf(arr, arr.length);
        
        long start = System.currentTimeMillis();
        iterativeQsort(tempArr);
        millisIterative[t] = (int)(System.currentTimeMillis()-start);
        
        tempArr = Arrays.copyOf(arr, arr.length);
        
        start = System.currentTimeMillis();
        recursvieQsort(tempArr,0,arr.length);
        millisRecursive[t] = (int)(System.currentTimeMillis()-start);
    }
    int sum = 0;
    for (int x : millisRecursive) {
        System.out.println(x);
        sum += x;
    }
    System.out.println("end of recursive. AVG = " + ((double)sum)/millisRecursive.length);
    sum = 0;
    for (int x : millisIterative) {
        System.out.println(x);
        sum += x;
    }
    System.out.println("end of iterative. AVG = " + ((double)sum)/millisIterative.length);
}

Answer 2

递归并不总是比迭代慢。快速排序就是一个很好的例子。以迭代方式执行此操作的唯一方法是创建堆栈结构。因此，如果我们使用递归，则以其他方式与编译器执行相同的操作，并且您可能会比编译器做得更糟。如果您不使用递归（将值弹出并将值推送到堆栈），也会有更多的跳转。

Answer 3

这就是我在 Javascript 中提出的解决方案。我认为它有效。

function qs_iter(items) {
    if (!items || items.length <= 1) {
        return items
    }
    var stack = []
    var low = 0
    var high = items.length - 1
    stack.push([low, high])
    while (stack.length) {
        var range = stack.pop()
        low = range[0]
        high = range[1]
        if (low < high) {
            var pivot = Math.floor((low + high) / 2)
            stack.push([low, pivot])
            stack.push([pivot+1, high])
            while (low < high) {
                while (low < pivot && items[low] <= items[pivot]) low++
                while (high > pivot && items[high] > items[pivot]) high--
                if (low < high) {
                    var tmp = items[low]
                    items[low] = items[high]
                    items[high] = tmp
                }
            }
        }
    }
    return items
}

如果您发现错误，请告诉我:)