利用电脑做网站百度站长平台官网
（）标题：[数据结构] 归并排序&&快速排序 及非递归实现
@水墨不写bug
（图片来源于网络）
目录
(一)快速排序
类比递归谋划非递归
快速排序的非递归实现：
（二）归并排序
归并排序的递归实现：
归并排序的非递归
细节处理：
归并排序的非递归实现：
正文开始：
(一)快速排序
快速排序一般通过递归来实现，但是递归也有递归的劣势：当递归程度太深，会导致栈溢出的问题，我们在前面的分享中已经讲解了快速排序的递归实现，这里不再赘述，为了便于讲解，直接给出快速排序的递归实现：
int GetRandomKey(vector<int>& nums, int l, int r) {return nums[rand() % (r - l + 1) + l]; } void QuickSort(vector<int>& nums,int l,int r) {//递归出口if (l >= r)return;int key = GetRandomKey(nums,l,r);int left = l - 1, right = r + 1, cur = l;while (cur < right){if (nums[cur] < key)swap(nums[cur++], nums[++left]);else if (nums[cur] == key)cur++;elseswap(nums[--right],nums[cur]);}QuickSort(nums, l, left);QuickSort(nums, right, r); }这里给出的快速排序的递归实现是比较完备的优化过的快排，它解决了：
（1）、key选取不合适导致的分区不平衡的问题。
（2）、key在数据中重复大量出现的问题。
递归的过程：
其实通过观察快排的过程，我们会发现之所以在传入参数的时候必须传入左右区间，是因为我们在快排的内部过程中并不确定需要对哪一个区间的数据 进行排序。
随着递归的进行，函数栈帧逐层开辟，每一层函数栈帧中都存有需要排序的区间的边界值。
每一个函数栈帧都有一个
左区间端点值 ：l
右区间端点值 ：r
递归是在栈区进行的，我们既然需要避免计算机自己的栈区溢出，那么我们为什么不自己模拟一个栈呢？
递归原理：
通过模拟一个栈，来协助存储左右区间端点值，以此来达到让快排正常进行的目的。
因此，重要的是需要对自己实现的栈精确的控制。
类比递归谋划非递归
什么时候递归停止？
当所有递归都返回的时候递归停止——当模拟实现的栈为空的时候停止迭代；
递归出口的条件设置？
当递归区间不存在的时候，递归通过return返回到上一层——当递归区间不存在的时候，直接进入下一次迭代，这里就用到了continue；
如何准确的控制接收的左右区间的端点值？
通过栈来模拟，需要注意栈的后进先出的特点，push的顺序和pop的顺序是相反的，比如：先push左端点，再push右端点；在top的时候，先取得的是右端点值，pop后，top再取得的是左端点值。
快速排序的非递归实现：
void QuickSort_NoR(vector<int>& nums,int l1,int r1) {stack<int> st;st.push(l1);st.push(r1);while (!st.empty()){int r = st.top();st.pop();int l = st.top();st.pop();if (l >= r)continue;int left = l - 1, right = r + 1, cur = l;int key = GetRandomKey(nums, l, r);while (cur < right){if (nums[cur] < key)swap(nums[cur++], nums[++left]);else if (nums[cur] == key)cur++;elseswap(nums[--right], nums[cur]);}st.push(right);st.push(r);st.push(l);st.push(left);} }
（二）归并排序
归并是一种算法，当归并应用在排序中，实际上的操作就是将两个有序数组合并为一个有序数组的过程。
归并排序一般通过非递归实现，其核心思想是分治，但是递归的缺点明显，本文上半部分也说明了递归的缺点，因此非递归实现归并有很大意义。
时间复杂度：O(N*logN)
空间复杂度：O(N)
稳定性：稳定归并的缺点：需要O(N)的空间复杂度
我们在实现归并排序的时候，需要注意的是：
（1）、需要一个N个空间的数组辅助进行排序，由于递归次数很多，在递归过程中创建数组代价太大，所以我们在全局来创建一个数组tem，作为辅助，不仅在每一层递归中都可使用，也节省了资源。
（2）、归并的主要过程通过三目运算符处的逻辑实现。
（3）、三目运算符之后，需要再将没有遍历到末尾的数据继续添加到tem末尾即可，此时归并结束。
（4）、最终不要忘了将tem内的数据拷贝回原数组。
归并排序的递归实现：
vector<int> tem(0); void MergeSort(vector<int>& nums,int l,int r) {if (l >= r)return;int mid = (r - l) / 2 + l;int cur1 = l, cur2 = mid + 1;MergeSort(nums, l, mid);MergeSort(nums, mid + 1, r);int i = 0;while (cur1 <= mid && cur2 <= r){tem[i++] = nums[cur1] < nums[cur2] ?nums[cur1++] : nums[cur2++];}while (cur1 <= mid)tem[i++] = nums[cur1++];while (cur2 <= r)tem[i++] = nums[cur2++];for (int j = l; j <= r;++j){nums[j] = tem[j - l];} } int main() {vector<int> nums = { 99,0,7,5,44,3,78,653,90,81 };tem.resize(nums.size());Print(nums);MergeSort(nums,0,nums.size()-1);Print(nums);return 0; }
归并排序的非递归
想要实现归并的非递归，在整体上需要换一种思路。
在局部上，归并的逻辑仍然是与递归是一致的；
我们在思考的时候要将问题逐渐拆成一个一个的小问题：
（1）、归并过程：
将[begin1,end1],[begin2,end2]归并为一个有序的数组，算法本质和步骤和非递归的实现方法完全一致；
（2）、非递归省去了进入递归的过程，而是直接将数组分为多份，每一份有gap个：
gap开始取1，表示一个数字就是一个区间，这个步骤是数组本身就满足的；
gap每次*2，表示区间扩大的过程，这样一来gap逐渐扩大，就在思路上完成了归并；
通过分析，你也知道了最重要的是对区间的左右端点的控制，也就是需要控制好区间的偏移和越界问题。
细节处理：
（1）区间的偏移：
通过一个循环，循环变量为k，两个区间的开始位置是由k来决定的，用k来控制区间的偏移：由于每次是归并两个数组，所以每次归并完成后，k+=2*gap:
演示（以gap=2为例）：
偏移后：（k+=2*gap）
（2）区间的越界：
我们上图举的例子是一个特殊情况，数组元素个数刚好够归并需要的元素，如果元素有9个而不是8个，这就需要考虑区间的越界问题了。
当数组的长度更加一般时，会出现区间的越界问题，对于每一个区间端点：
begin1：由k决定（k< n,所以不可能越界）
end1：begin1+gap-1，有可能越界；如果越界，数组个数只有一个，则不再归并。
begin2：begin1+gap，可能越界；如果越界，数组个数只有一个，则不再归并。
end2：begin1+2*gap-1；可能越界；如果越界，数组个数有两个，修正end2的位置后再归并。
归并排序的非递归实现：
void MergeSort_NoR(vector<int>& nums, int l, int r) {int n = nums.size();int gap = 1;while (gap < n){for (int k = 0; k < n; k += 2*gap){// 对两组进行归并 [beign1,end1] [begin2,end2] // 组内宽度gap int begin1 = k, end1 = begin1 + gap - 1;int begin2 = end1 + 1, end2 = begin2 + gap - 1;if (end1 >= n || begin2 >= n)break;if (end2 >= n)end2 = n-1;int i = k;while (begin1 <= end1 && begin2 <= end2)tem[i++] = nums[begin1] < nums[begin2] ?nums[begin1++] : nums[begin2++];while (begin1 <= end1) tem[i++] = nums[begin1++];while (begin2 <= end2) tem[i++] = nums[begin2++];for (int j = k; j <= end2; ++j)nums[j] = tem[j];}gap *= 2;} }
完~
未经作者同意禁止转载