c++归并排序详解

说一说归并排序

创新互联建站专注于企业全网整合营销推广、网站重做改版、沾化网站定制设计、自适应品牌网站建设、html5、商城开发、集团公司官网建设、外贸网站制作、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为沾化等各大城市提供网站开发制作服务。

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

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

c++归并排序详解

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

 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]

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

 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 
 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]=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<

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

 #include 
 #include  
 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]>a[i];
   }
   mergesort(a,5);
   for(int i=0;i<5;i++)
   {
     cout<

本文名称：c++归并排序详解
转载源于：http://njwzjz.com/article/phdcoo.html

NEWS

网站建设资讯

c++归并排序详解

其他资讯