河北网站制作多少钱/html网页制作案例

快速排序法的递归和迭代两种实现。迭代实现基本复用了递归实现的代码，在递归基础上小小的改动即可。

递归版

#include <bits/stdc++.h>
using namespace std;/*
快速排序递归法与迭代法实现
*/
void quick_sort_recursive(vector<int> &arr, int start, int end)
{// 这里采用闭区间，下文迭代法也统一使用闭区间if (start >= end)return;int base = arr[start];int left = start, right = end;while (left < right){ // while结束条件while (left < right && arr[right] >= base){right--; // 从右往左找到第一个比base小的数}while (left < right && arr[left] <= base){left++; // 从左往右找到第一个比base大的数}swap(arr[left], arr[right]); // 交换}swap(arr[start], arr[left]); // 最后left==right，该位置的数一定是小于等于base的数quick_sort_recursive(arr, start, left - 1);quick_sort_recursive(arr, left + 1, end);
}

迭代版

struct param
{int low;int high;param(int l, int h) : low(l), high(h){};
};void quick_sort_iterative(vector<int> &arr)
{/*快速排序本质上是二叉树的前序遍历，可以使用栈来模拟*/stack<param> stk;int end = arr.size() - 1;stk.emplace(0, end);while (!stk.empty()){param cur = stk.top();stk.pop();// 下面就是直接复制递归的实现了int start = cur.low;int end = cur.high;if (start >= end)continue;int base = arr[start];int left = start, right = end;while (left < right){ // while结束条件while (left < right && arr[right] >= base){right--; // 从右往左找到第一个比base小的数}while (left < right && arr[left] <= base){left++; // 从左往右找到第一个比base大的数}swap(arr[left], arr[right]); // 交换}swap(arr[start], arr[left]); // 最后left==right，该位置的数一定是小于等于base的数// 模拟递归stk.emplace(left+1,end);stk.emplace(start,left-1);}
}