【C++板块提升计划】C++快排【非递归形式】
本帖最后由 zhangjinxuan 于 2023-3-3 21:25 编辑最近闲来无事，写了一个非递归形式的快排{:10_256:}
思路很简单，递归使用栈的，对吧，那么我们模拟一下栈就可以啦~
代码：
#include <bits/stdc++.h>
using namespace std;
int st, top, n, a;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &a);
st[++top] = 1;
st = n;
while (top) {
int l = st, r = st;
if (l >= r) continue;
int t = a, i = l, j = r;
while (i <= j) {
while (i <= j && a < t) ++i;
while (i <= j && a > t) --j;
if (i <= j) swap(a, a);
}
st[++top] = l, st = j;
st[++top] = i, st = r;
}
for (int i = 1; i <= n; ++i)
printf("%d ", a);
}
这个故事告诉我们：递归真的全都可以写为栈（非递归，循环）的形式，循环时只要把递归所用到的参数加到栈里面就行了~
归根到底，递归其实就是用到了栈{:10_256:}
但是，大家觉得 非递归形式的快排 是比 递归形式的快排 快了，还是慢了？欢迎大家投票~
我觉得非递归形式要快，因为一个函数的开销很大，可能几十字节，不如我记两个int一共8字节 本文原创啊，如果有雷同那真的是巧合，巧合 最终，非递归的快排比stl的快排还要快{:10_256:}
页:
[1]