【C++板块提升计划】C++快排【非递归形式】

zhangjinxuan

最近闲来无事，写了一个非递归形式的快排

思路很简单，递归使用栈的，对吧，那么我们模拟一下栈就可以啦~

代码：

#include <bits/stdc++.h>
using namespace std;

int st[10001][2], top, n, a[10001];

int main() {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
                scanf("%d", &a[i]); 
        st[++top][0] = 1;
        st[top][1] = n;
        while (top) {
                int l = st[top][0], r = st[top--][1];
                if (l >= r) continue;
                int t = a[l], i = l, j = r;
                while (i <= j) {
                        while (i <= j && a[i] < t) ++i;
                        while (i <= j && a[j] > t) --j;
                        if (i <= j) swap(a[i++], a[j--]);
                }
                st[++top][0] = l, st[top][1] = j;
                st[++top][0] = i, st[top][1] = r;
        }
        for (int i = 1; i <= n; ++i)
                printf("%d ", a[i]);
}

这个故事告诉我们：递归真的全都可以写为栈（非递归，循环）的形式，循环时只要把递归所用到的参数加到栈里面就行了~

归根到底，递归其实就是用到了栈

但是，大家觉得 非递归形式的快排 是比 递归形式的快排 快了，还是慢了？欢迎大家投票~

zhangjinxuan

我觉得非递归形式要快，因为一个函数的开销很大，可能几十字节，不如我记两个int一共8字节

zhangjinxuan

本文原创啊，如果有雷同那真的是巧合，巧合

zhangjinxuan

最终，非递归的快排比stl的快排还要快