个人中心
gpt4 book ai didi

c++归并排序详解

转载 作者：qq735679552 更新时间：2022-09-28 22:32:09 24 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章c++归并排序详解由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

说一说归并排序 。

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

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

  。

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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++;
         }
   }
}

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

?
1
2
3
4
5
6
7
8
9
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函数 。

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

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#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;
}

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#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; 
}

原文链接：http://www.cnblogs.com/agui521/p/6918229.html 。

最后此篇关于c++归并排序详解的文章就讲到这里了,如果你想了解更多关于c++归并排序详解的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

24 4 0
文章推荐： c++快速排序详解
文章推荐： rpm是什么意思
文章推荐： linux下制作安装rpm包
文章推荐： 阐述Linux操作系统之rpm五种基本操作
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com