An iterative way of writing quick sort:
#include <iostream>
#include <stack>
#include <utility>
using namespace std;
void quickSort(int A[], int n) {
stack<pair<int, int>> stk;
stk.push(make_pair(0, n-1));
while (!stk.empty()) {
pair<int, int> p = stk.top();
stk.pop();
int r = rand() % (p.second-p.first+1) + p.first;
swap(A[r], A[p.first]);
int j = p.first;
for (int i=p.first+1; i<=p.second; ++i) {
if (A[i] < A[p.first]) swap(A[++j], A[i]);
}
swap(A[p.first], A[j]);
if (j-1 > p.first) stk.push(make_pair(p.first, j-1));
if (j+1 < p.second) stk.push(make_pair(j+1, p.second));
}
}
int main() {
int A[8] = {4, 3, 5, 2, 1, 3, 2, 3};
quickSort(A, 8);
for (int i=0; i<8; ++i) cout<<A[i]<<" ";
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/119221.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...
