归并排序
2021-03-20 09:25
标签:loading bit nbsp 有序表 ref code int alt style 归并排序 我终于看了归并排序了!!!其实我很久之前就准备把瑞士轮给做了,但是,我发现用STL里的sort过不了过后我就没再管它了,今天又看到了这道题,我还是决定看一看神奇的归并排序。 由于不喜欢看好多好多字,我们先放一张图(简单易懂) 我当时看到这图过后就恍pang然ran大da悟wu了,突然就懂了它的基本思想:归并排序是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。(感谢百度百科)(说人话就是采用一个分治的思想,然后在分成的每一小段内进行排序,因为每一段都是有序的,在后来的每一步合并操作之中就都很方便了,只需要考虑四种情况,最后的最后,将它们合并成一个整体的操作) 所以代码怎么实现?因为我没想出来,就去网上看了看其他大神写的模版,然后我又突然就懂了(什么,又懂了?) 首先我们从main函数开始倒着往回推 就是一个很简单的输入输出,加一个mergesort操作,由于输入的时候数组只有0~n-1有真正的值,我们就又要需要一个来解决这个简单的问题lalala 所以这个真正的merge_sort()函数是在干什么呢?其实实质上就是个简单的二分(纯二分 看这个奇妙的二分函数我们又要引入一个函数merge()了,终于切入正题了。。。 这就是我刚刚提到的四种情况,因为在这里,整个l~r被分成了两个部分:l~mid&mid+1~r,所以我们就从l和mid+1开始比较,先考虑边界(l>mid和j>r),解决了这问题就是一个分类讨论,还只有两种情况,因为i和j是头,分别是现存的两个部分里最小的,所以只需要比较i和j在数组中的值就可以确定结果数组的后一位数了 瞎扯了认真分析了一大堆,完整代码如下: 全文完。。。所以我还写不写其他排序的分析呢?(手 动 问 号 ) 归并排序 标签:loading bit nbsp 有序表 ref code int alt style 原文地址:https://www.cnblogs.com/001A/p/13926467.html1 int main(){
2 int n,a[10005];
3 cin>>n;
4 for(int i=0;i
1 void mergesort(int a[],int l,int r){
2 merge_sort(a[],l,r-1);
3 }
1 void merge_sort(int a[],int l,int r){
2 if(l>=r) return;
3 int mid=(l+r)/2;
4 merge_sort(a,l,mid);
5 merge_sort(a,mid+1,r);
6 merge(a,l,r,mid);
7 }
1 void merge(int a[],int l,int r,int mid){
2 int b[r-l+1];
3 for(int k=l;ka[k];
4 int i=l,j=mid+1;
5 for(int k=l;k){
6 if(i>mid) a[k]=b[j-l],j++;
7 else if(j>r) a[k]=b[i-l],i++;
8 else if(b[i-l]>b[j-l]) a[k]=b[j-l],j++;
9 else a[k]=b[i-l],i++;
10 }
11 }
1 //归并排序模版
2 #include
上一篇:Python科学计算类库
下一篇:Springboot自动配置