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;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/119221.html原文链接：https://javaforall.net
