亚洲成成品网站有线,网站内容发布平台源码,二手车网站建设,外贸神器算法思路
归并排序是一种分治算法#xff1a;首先将数组分成两半#xff0c;然后对每一半进行归并排序#xff0c;最后将两个有序的子数组合并#xff0c;以得到最终的排序数组。为了简洁下面代码中会调用 STL 的 i n p l a c e _ m e r g e inplace\_merge inplace_merg…算法思路
归并排序是一种分治算法首先将数组分成两半然后对每一半进行归并排序最后将两个有序的子数组合并以得到最终的排序数组。为了简洁下面代码中会调用 STL 的 i n p l a c e _ m e r g e inplace\_merge inplace_merge 方法这个方法的作用正是将两个连续的有序区间合并为一个有序区间当然也可以自己按合并有序链表的思路写一个 m e r g e merge merge 方法~ a. 递归
自顶向下的递归排序
void merge_sort(vectorint li, int s, int e) {//li[s,e)为待排序的子数组if (e - s 1)return;int mid (s e) / 2;merge_sort(li, s, mid);merge_sort(li, mid, e);inplace_merge(li.begin() s, li.begin() mid, li.begin() e);//合并有序区间[s,mid)和[mid,e)
}b. 栈模拟递归
用一个栈模拟递归排序中区间处理的过程注意一个区间可能会在栈中出现两次第一次其两个子区间还未排序第二次其两个子区间已经有序所以需要有一个额外的标志位来区分一个区间在栈中的这两种状态。
void merge_sort_stack(vectorint li, int s, int e) {//li[s,e)为待排序的子数组stacktupleint, int, int st;st.emplace(s, e, 0);while (!st.empty()) {auto [l, r, tag] st.top();//当前区间为[l,r) , 标志位为tagst.pop();if (tag 0) {//当前区间第一次出现if (r - l 1)continue;int mid (l r) / 2;st.emplace(l, r, 1);st.emplace(l, mid, 0);st.emplace(mid, r, 0);} else {//当前区间第二次出现int mid (l r) / 2;inplace_merge(li.begin() l, li.begin() mid, li.begin() r);//合并有序区间[l,mid)和[mid,r)}}
}c. 递推
自底向上的递推首先两两一组的合并长为 2 0 2^0 20 的子数组再两两一组的合并长为 2 1 2^1 21 的子数组 ⋯ \cdots ⋯ 直到 2 k 2^k 2k 不小于数组长度时递推结束。注意每一轮合并中最后一组的右边的子数组的长度可能小于 2 k 2^k 2k。
void merge_sort(vectorint li, int s, int e) {//li[s,e)为待排序的子数组int n e - s;for (int len 1; len n; len * 2)//合并的子数组的长度len不超过nfor (int i s; i len e; i len * 2)//逐对枚举两个相邻的子数组inplace_merge(li.begin() i, li.begin() i len, li.begin() min(e, i len * 2));//合并有序区间[i,ilen)和[ilen,min(e,ilen*2))
}
