首页 > 代码库 > Iterative (non-recursive) Quick Sort
Iterative (non-recursive) Quick Sort
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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。