C++ 归并排序代码 |21xrx.com

C++ 归并排序代码

2023-07-05 06:32:39 深夜i -- --

C++ 归并排序代码分治算法时间复杂度

C++归并排序代码

归并排序是一种基于“分治”思想的排序算法。通过将一个大问题分成若干小问题，对每个小问题分别求解，然后将小问题的解合并成原问题的解来完成排序。

以下是C++归并排序的代码实现：


#include<iostream>
using namespace std;
void Merge(int a[],int l1,int r1,int l2,int r2)
{
  int i=l1,j=l2;//i,j表示两个有序序列的当前元素的位置
  int temp[100],index=0;
  while(i<=r1&&j<=r2)//两个序列合并
  {
    if(a[i]<=a[j])
      temp[index++]=a[i++];
    else
      temp[index++]=a[j++];
  }
  while(i<=r1)//如果第一个序列还有剩余元素
    temp[index++]=a[i++];
  while(j<=r2)//如果第二个序列还有剩余元素
    temp[index++]=a[j++];
  for(int k=0;k<index;k++)//将结果复制到原序列中
    a[l1+k]=temp[k];
}
void MergeSort(int a[],int left,int right)
{
  if(left<right)
  {
    int mid=(left+right)/2;//分治
    MergeSort(a,left,mid);//递归左半部分
    MergeSort(a,mid+1,right);//递归右半部分
    Merge(a,left,mid,mid+1,right);//归并
  }
}
int main()
{
  int a[10]=9;
  MergeSort(a,0,9);
  for(int i=0;i<10;i++)
    cout<<a[i]<<" ";
  return 0;
}

在上面的代码中，Merge()函数用于合并两个有序序列，MergeSort()函数用于递归地进行分治和归并操作。最后，在main()函数中，我们初始化一个整型数组，并使用MergeSort()进行排序，最终输出排好序的结果。

因此，C++归并排序代码就这样实现了！这是一种高效、稳定、并且易于实现的排序算法，很多程序员喜欢使用归并排序算法来对数据进行排序。

上一篇: idea打包java可执行jar包

下一篇: C++中的继承——理解和应用

评论区

()

相似文章