c++归并排序详解

说一说归并排序

归并排序:归并排序(英语:Merge sort,或mergesort),是创建在归并操作上的一种有效的排序算法,效率为O(n log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。

归并排序的核心思想是将两个有序的数列合并成一个大的有序的序列。通过递归,层层合并,即为归并。

如图,从下到上,每一步都需要将两个已经有序的子数组合并成一个大的有序数组,如下是实现合并的具体代码,请读者细细体会

 void merge(int arr[],int l,int mid,int r)
 {
   int aux[r-l+1];//开辟一个新的数组,将原数组映射进去
   for(int m=l;m<=r;m++)
   {
     aux[m-l]=arr[m];
   }

   int i=l,j=mid+1;//i和j分别指向两个子数组开头部分

   for(int k=l;k<=r;k++)
   {
     if(i>mid)
     {
       arr[k]=aux[j-l];
       j++;
     }
     else if(j>r)
     {
       arr[k]=aux[i-l];
       i++;
     }
         else if(aux[i-l]<aux[j-l])
         {
           arr[k]=aux[i-l];
           i++;
         }
         else
         {
           arr[k]=aux[j-l];
           j++;
         }
   }
 }

上图代码已经完成了归并中的“并”这一部分,归并归并,有并必有归,如下实现“归”的部分

 void merge_sort(int arr[],int l,int r)
{
  if(l >=r)
    return ;
  int mid=(l+r)/2;
  merge_sort(arr,l,mid);
  merge_sort(arr,mid+1,r);
  merge(arr,l,mid,r);
}

由于上图中的l,r不方便使用者调用,于是我们创建一个方便自己调用的my_merge_sort函数

 void my_merge_sort(int arr[],int n)
{
  merge_sort(arr,0,n-1);
}

以上我们便实现了归并排序中的归和并,归并排序是利用二分法实现的排序算法,时间复杂度为nlogn,是一种比较快速的排序算法。如下是笔者自己写的归并排序的全部代码,

 #include <iostream>
 using namespace std;

 void merge(int arr[],int l,int mid,int r)
 {
   int aux[r-l+1];//开辟一个新的数组,将原数组映射进去
   for(int m=l;m<=r;m++)
   {
     aux[m-l]=arr[m];
   }

   int i=l,j=mid+1;//i和j分别指向两个子数组开头部分

   for(int k=l;k<=r;k++)
   {
     if(i>mid)
     {
       arr[k]=aux[j-l];
       j++;
     }
     else if(j>r)
     {
       arr[k]=aux[i-l];
       i++;
     }
         else if(aux[i-l]<aux[j-l])
         {
           arr[k]=aux[i-l];
           i++;
         }
         else
         {
           arr[k]=aux[j-l];
           j++;
         }
   }
 }
 //递归的使用归并排序,对arr[l....r]排序
 void merge_sort(int arr[],int l,int r)
 {
   if(l >=r)
     return ;
   int mid=(l+r)/2;
   merge_sort(arr,l,mid);
   merge_sort(arr,mid+1,r);
   merge(arr,l,mid,r);
 }

 void my_merge_sort(int arr[],int n)
 {
   merge_sort(arr,0,n-1);
 } 

 int main()
 {
   int a[6];
   for(int i=0;i<6;i++)
   {
     cin>>a[i];
   }
   my_merge_sort(a,6);
   for(int i=0;i<6;i++)
   {
     cout<<a[i]<<" ";
   }
   return 0;
 }

上面实现的归并排序是自顶向下的,我们可以以另外一种方向来实现归并,改递归为迭代。如下实现

 #include <iostream>
 #include <math.h>
 using namespace std;

 void merge(int arr[],int l,int mid,int r)
 {
   int aux[r-l+1];//开辟一个新的数组,将原数组映射进去
   for(int m=l;m<=r;m++)
   {
     aux[m-l]=arr[m];
   }

   int i=l,j=mid+1;//i和j分别指向两个子数组开头部分

   for(int k=l;k<=r;k++)
   {
     if(i>mid)
     {
       arr[k]=aux[j-l];
       j++;
     }
     else if(j>r)
     {
       arr[k]=aux[i-l];
       i++;
     }
         else if(aux[i-l]<aux[j-l])
         {
           arr[k]=aux[i-l];
           i++;
         }
         else
         {
           arr[k]=aux[j-l];
           j++;
         }
   }
 }

 void mergesort(int arr[],int n)
 {
   for(int sz=1;sz<=n;sz+=sz)
   {
     for(int i=0;i+sz<n;i+=sz+sz)//i+sz防止越界
     {//对arr[i...sz-1]和arr[i+sz.....i+2*sz-1]进行排序
       merge(arr,i,i+sz-1,min(i+sz+sz-1,n-1));  //min函数防止越界
     }
   } 

 } 

 int main()
 {
   int a[5];
   for(int i=0;i<5;i++)
   {
     cin>>a[i];
   }
   mergesort(a,5);
   for(int i=0;i<5;i++)
   {
     cout<<a[i]<<" ";
   }
   return 0;
 }
(0)

相关推荐

  • C++归并排序算法实例

    归并排序 归并排序算法是采用分治法的一个非常典型的应用.归并排序的思想是将一个数组中的数都分成单个的:对于单独的一个数,它肯定是有序的,然后,我们将这些有序的单个数在合并起来,组成一个有序的数列.这就是归并排序的思想.它的时间复杂度为O(N*logN). 代码实现 复制代码 代码如下: #include <iostream> using namespace std;   //将有二个有序数列a[first...mid]和a[mid...last]合并. void mergearray(int

  • C++实现的归并排序算法详解

    本文实例讲述了C++实现的归并排序算法.分享给大家供大家参考,具体如下: 归并排序 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法. 该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列: 即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 归并过程 1.比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到temp[k]中,并令i

  • C++实现自顶向下的归并排序算法

    本文实例讲述了C++实现自顶向下的归并排序算法.分享给大家供大家参考,具体如下: 一. 算法描述 自顶向下的归并排序:采用分治法进行自顶向下的程序设计方式,分治法的核心思想就是分解.求解.合并. 1. 先将长度为N的无序序列分割平均分割为两段 2. 然后分别对前半段进行归并排序.后半段进行归并排序 3. 最后再将排序好的前半段和后半段归并 过程(2)中进行递归求解,最终下图详细的分解了自顶向下的合并算法的实现过程: 二. 算法实现 /*==============================

  • C++实现自底向上的归并排序算法

    本文实例讲述了C++实现自底向上的归并排序算法.分享给大家供大家参考,具体如下: 一. 算法描述 自底向上的归并排序:归并排序主要是完成将若干个有序子序列合并成一个完整的有序子序列:自底向上的排序是归并排序的一种实现方式,将一个无序的N长数组切个成N个有序子序列,然后再两两合并,然后再将合并后的N/2(或者N/2 + 1)个子序列继续进行两两合并,以此类推得到一个完整的有序数组.下图详细的分解了自底向上的合并算法的实现过程: 二. 算法实现 /*=========================

  • java 算法之归并排序详解及实现代码

    java 算法之归并排序详解 一.思想 归并排序:将一个数组排序,可以先(递归地)将它分成两半部份分别排序,然后将结果归并起来: 二.概念 归并:将两个有序的数组归并成一个更大的有序数组: 三.特点 优点:能够保证将任意长度为N的数组排序所需要的时间和NlogN成正比: 缺点:需要额外的空间和N成正比: 四.实现方法 将两个不同的有序数组归并到第三个数组中: 先将前半部分排序,在将后半部分排序,然后在数组中移动元素而不需要使用额外的空间: 五.代码 /** * 归并排序 * * @author

  • java数据结构排序算法之归并排序详解

    本文实例讲述了java数据结构排序算法之归并排序.分享给大家供大家参考,具体如下: 在前面说的那几种排序都是将一组记录按关键字大小排成一个有序的序列,而归并排序的思想是:基于合并,将两个或两个以上有序表合并成一个新的有序表 归并排序算法:假设初始序列含有n个记录,首先将这n个记录看成n个有序的子序列,每个子序列长度为1,然后两两归并,得到n/2个长度为2(n为奇数的时候,最后一个序列的长度为1)的有序子序列.在此基础上,再对长度为2的有序子序列进行亮亮归并,得到若干个长度为4的有序子序列.如此重

  • Java经典排序算法之归并排序详解

    一.归并排序 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 归并过程为:比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1:否则将第二个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上1,如此循环下去,直

  • C语言实现排序算法之归并排序详解

    排序算法中的归并排序(Merge Sort)是利用"归并"技术来进行排序.归并是指将若干个已排序的子文件合并成一个有序的文件. 一.实现原理: 1.算法基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中. (1)合并过程 合并过程中,设置i,j和p三个指针,其初值分别指向这三个记录区的起始位置.合并时依次比较R[i

  • c++归并排序详解

    说一说归并排序 归并排序:归并排序(英语:Merge sort,或mergesort),是创建在归并操作上的一种有效的排序算法,效率为O(n log n).1945年由约翰·冯·诺伊曼首次提出.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行. 归并排序的核心思想是将两个有序的数列合并成一个大的有序的序列.通过递归,层层合并,即为归并. 如图,从下到上,每一步都需要将两个已经有序的子数组合并成一个大的有序数组,如下是实现合并的具体代码,请

  • C语言开发之归并排序详解及实例

     C语言归并排序 即将两个都升序(或降序)排列的数据序列合并成一个仍按原序排列的序列. 上代码: #include <stdio.h> #include <stdlib.h> #define m 6 #define n 4 int main() { int a[m]={-3,6,19,26,68,100} ,b[n]={8,10,12,22}; int i,j,k,c[m+n]; int l ; i=j=k=0; printf("a数组的元素:\n"); for

  • PHP排序算法系列之归并排序详解

    归并排序 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 归并过程 归并排序的核心就是如何将两个有序序列进行合并,假定有两个有序数组,比较两个有序数组的首个元素,谁小就取谁,并将该元素放入第三个数组中,取了之后在相应的数组中将删除此元素,依次类推,当取到一个数组已

  • JAVA十大排序算法之归并排序详解

    目录 归并排序 怎么分 怎么治 代码实现 时间复杂度 算法稳定性 总结 归并排序 归并,指合并,合在一起.归并排序(Merge Sort)是建立在归并操作上的一种排序算法.其主要思想是分而治之.什么是分而治之?分而治之就是将一个复杂的计算,按照设定的阈值进行分解成多个计算,然后将各个计算结果进行汇总.即"分"就是把一个大的通过递归拆成若干个小的,"治"就是将分后的结果在合在一起. 若将两个有序集合并成一个有序表,称为2-路归并,与之对应的还有多路归并. 怎么分 对于

  • C++STL函数和排序算法的快排以及归并排序详解

    目录 一.队列是什么? 二.排序算法 1.快速排序 2.归并排序 总结 一.队列是什么? 头文件queue主要包括循环队列queue和优先队列priority_queue两个容器. 像栈一样,队列(queue)也是一种线性表,它的特性是先进先出,插入在一端,删除在另一端.就像排队一样,刚来的人入队(push)要排在队尾(rear),每次出队(pop)的都是队首(front)的人. 就像管道一样先进先出. 队列的相关概念: 1.队头与队尾: 允许元素插入的一端称为队尾,允许元素删除的一端称为队头.

  • C语言递归实现归并排序详解

    归并排序递归实现还是比较难理解的,感觉涉及递归一般理解起来都会比较有难度吧,但是看了b站视频,然后照着打下来,然后自己写了点注释,就发现不知不觉都大概懂了. 这里的归并讲的是升序排序 归并排序思路大概就是:先划分数组,将数组划分为左右半区,分成的左右半区,各自再划分左右半区,一直划分,直到最后左右半区的元素都为一个时,开始合并,因为都划分为一个元素了,那么此时两个元素的排序就非常简单了,只需要比较大小就可以排序了,那么回溯上去会发现每组都是两两有序了,那么直接再依次比较两组之间的排头元素即可,取

随机推荐