题目描述
非递归快速排序
递归都可用出栈入栈实现。
概念:二分一次就将左右区间的左右边界入栈,从栈顶取左右边界进行处理,处理完出栈继续二分。处理方式:一边找小,一边找大,找到交换,继续。
边界:栈空就结束。
C++ 代码
#include <iostream>
#include <stack>
using namespace std;
#define x first
#define y second
stack<pair<int,int>> s;
void qsort(int a[],int l, int r){
s.push({l, r});
while(!s.empty()){
l = s.top().x, r = s.top().y, s.pop();
if(l >= r) continue;
int i = l - 1, j = r + 1, x = a[l + r >> 1];
while (i < j)
{
do i ++ ; while (a[i] < x);
do j -- ; while (a[j] > x);
if (i < j) swap(a[i], a[j]);
}
s.push({l, j}), s.push({j + 1, r});
}
}
int main()
{
int a[100001];
int n; cin >> n;
for (int i = 0; i < n; i ++ ) cin >> a[i];
qsort(a, 0, n - 1);
for (int i = 0; i < n; i ++ )
cout << a[i] << " ";
return 0;
}