个人中心
gpt4 book ai didi

c++实现二路归并排序的示例代码

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

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

这篇CFSDN的博客文章c++实现二路归并排序的示例代码由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

二路归并排序 。

基本思想 。

二路归并排序就是将两个有序子表归并成一个有序表。首先我们得有一个算法用于归并：两个有序表放在同一数组的相邻位置上，arr[left]到arr[center-1]为第一个有序表，arr[center]到arr[right]是第二个有序表。每次从两端中取出一个进行比较，小的先放在一个temp数组，最后将比较剩下的直接放到temp中去，最后将temp又复制回arr。这是“治”。 所谓“分”，就是递归地将前半部分和后半部分的数据各自归并排序即可.

算法分析 。

每一趟归并的时间复杂度为O(n)，共需要进行⌈log2n⌉趟。对应的算法的时间复杂度为O(nlog2n)。归并排序的空间复杂度O(n)。另外，归并排序中归并的算法并不会将相同关键字的元素改变相对次序，所以归并排序是稳定的。 二路归并排序的前提是两个序列本身有序.

?
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
69
70
71
72
73
74
void Merger( int *arr, int len, int width)
{
  int *temp =( int *) malloc ( sizeof ( int ) * (len));
  //首先对两路下标分别进行初始化
  int l1 = 0;
  int h1 = l1 + width - 1;
  int l2 = h1 + 1;
  int h2 = l2 + width - 1 < len - 1 ? l2 + width - 1 : len - 1;
  int temppos = 0;
  //判断所在下标位置的值
  while (l1 < len && l2 < len)
  {
  while (l1 <= h1 && l2 <= h2)
  {
   if (arr[l1] < arr[l2])
   {
   temp[temppos++] = arr[l1++];
   }
   else
   {
   temp[temppos++] = arr[l2++];
   }
  }
  //l1有剩余
  while (l1 <= h1)
  {
   temp[temppos++] = arr[l1++];
  }
  //l2有剩余
  while (l2 <= h2)
  {
   temp[temppos++] = arr[l2++];
  }
  //l1 l2向后移动
  l1 = h2 + 1;
  h1 = (l1 + width - 1) < (len - 1) ? (l1 + width - 1) : (len - 1);
  l2 = h1 + 1;
  h2 = (l2 + width - 1) < (len - 1) ? (l2 + width - 1) : (len - 1);
  }
  //奇数归并块 剩下的一个单都块操作
  while (l1 <len)
  {
  temp[temppos++] = arr[l1++];
  }
  //用temp覆盖arr
  for ( int i = 0; i < len ; ++i)
  {
  arr[i] = temp[i];
  }
// free(temp);
}
void MergeSort( int *arr, int len)
{
  for ( int i = 1; i < len; i *= 2)
  {
  Merger(arr, len, i);
  }
}
void show( int *arr, int len)
{
  for ( int i = 0; i < len; ++i)
  {
  cout << arr[i] << " " ;
  }
}
int main()
{
  int array[] = { 12, 51, 1, 36, 98, 21, 38, 47 };
  int len = sizeof (array) / sizeof (array[0]);
  MergeSort(array, len);
  show(array, len);
  system ( "pause" );
  return 0;
}

PS:二路合并排序算法 。

?
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
69
70
71
72
73
#include<iostream>
using namespace std;
class SortableList
{
public :
     SortableList( int mSize)
     {
         maxSize = mSize;
       l= new int [maxSize];
         n = 0;
     }
     ~SortableList()
     {
         delete []l;
     }
     void Merge( int , int , int );
     void MergeSort( int , int );
     void Input();
     void Output();
    
    private :
          int * l;
          int maxSize;
          int n;
 
};
void SortableList::Input()
{
     cout << "请输入要排序的数：" ;
     for ( int i = 0; i <= maxSize - 1; i++)
         cin >> l[i];
}
void SortableList::Output()
{
     cout << "排序后的数是：" ;
     for ( int i = 0; i <= maxSize - 1; i++)
         cout << l[i]<< ' ' ;
}
void SortableList::MergeSort( int left, int right)
{
     if (left < right) //如果序列长度大于1则划分
     {
         int mid = (left + right) / 2;
         MergeSort(left, mid); //对左序列进行排序
         MergeSort(mid + 1, right); //对右序列进行排序
         Merge(left, mid, right); //合并
     }
}
void SortableList::Merge( int left, int mid, int right)
{
     int * temp= new int [right - left + 1];
     int i = left, j = mid + 1, k = 0;
     while ((i <= mid) && (j <= right)) //判断序列是否为空
         if (l[i] <= l[j])
             temp[k++] = l[i++];
         else temp[k++] = l[j++];
     while (i <= mid)
         temp[k++] = l[i++]; //右序列空了左序列依次写入
     while (j <= right)
         temp[k++] = l[j++]; //左序列空了右序列依次写入
     for (i = 0, k = left; k <= right;)
         l[k++] = temp[i++]; //临时在数组temp中的排列好的数据放入数组l
}
int main()
{
     int m;
     cout << "请输入要排序的数的数目：" ;
     cin >> m;
     SortableList a1(m);
     a1.Input();
     a1.MergeSort(0, m-1);
     a1.Output();
}

到此这篇关于c++实现二路归并排序的示例代码的文章就介绍到这了,更多相关c++ 二路归并排序内容请搜索我以前的文章或继续浏览下面的相关文章希望大家以后多多支持我！ 。

原文链接：https://blog.csdn.net/qq_21230831/article/details/95733815 。

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

24 4 0
文章推荐： 浅谈Qt QGraphics体系及刷新机制介绍
文章推荐： 我喜欢你 抖音表白程序python版
文章推荐： SQL实战演练之网上商城数据库商品类别数据操作
文章推荐： Vscode Remote Development远程开发调试的实现思路
qq735679552
个人简介

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

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