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

zhangjinxuan

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

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

代码：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int st[10001][2], top, n, a[10001];
   
5. 
   
6. int main() {
   
7.         scanf("%d", &n);
   
8.         for (int i = 1; i <= n; ++i)
   
9.                 scanf("%d", &a[i]);
   
10.         st[++top][0] = 1;
    
11.         st[top][1] = n;
    
12.         while (top) {
    
13.                 int l = st[top][0], r = st[top--][1];
    
14.                 if (l >= r) continue;
    
15.                 int t = a[l], i = l, j = r;
    
16.                 while (i <= j) {
    
17.                         while (i <= j && a[i] < t) ++i;
    
18.                         while (i <= j && a[j] > t) --j;
    
19.                         if (i <= j) swap(a[i++], a[j--]);
    
20.                 }
    
21.                 st[++top][0] = l, st[top][1] = j;
    
22.                 st[++top][0] = i, st[top][1] = r;
    
23.         }
    
24.         for (int i = 1; i <= n; ++i)
    
25.                 printf("%d ", a[i]);
    
26. }

复制代码

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

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

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

zhangjinxuan

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

zhangjinxuan

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

zhangjinxuan

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