21xrx.com
2024-05-20 13:00:59 Monday
登录
文章检索 我的文章 写文章
C++归并排序代码
2023-07-08 07:39:06 深夜i     --     --
C++ 归并排序 代码

C++归并排序代码是一种非常流行的排序算法,由于其高效率和稳定性,被广泛应用于各种数据处理场景,特别是在大数据量的情况下更是表现出其强大的优势。下面是C++归并排序代码的详细介绍。

1.归并排序的基本思想

归并排序的基本思想是将待排序的数列拆分成较小的子序列,然后进行排序,最后再合并拍好序的子序列,最终变成有序的数列。

2.归并排序的代码实现

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


#include <iostream>

using namespace std;

void merge_sort(int arr[],int left,int right)

{

  if(left>=right) return;

  int mid=(left+right)/2;

  int p1=left,p2=mid+1;

  int k=0;

  int *tem=new int[right-left+1];

  merge_sort(arr,left,mid);

  merge_sort(arr,mid+1,right);

  while(p1<=mid&&p2<=right)

  {

    if(arr[p1]>arr[p2])tem[k++]=arr[p2++];

    else tem[k++]=arr[p1++];

  }

  while(p1<=mid) tem[k++]=arr[p1++];

  while(p2<=right) tem[k++]=arr[p2++];

  for(int i=0;i<right-left+1;i++) arr[left+i]=tem[i];

  delete []tem;

}

int main() {

  int arr[10]=10;

  merge_sort(arr,0,9);

  for(int i=0;i<10;i++) cout<<arr[i]<<" ";

  cout<<endl;

  return 0;

}

3.代码实现解析

(1)merge_sort 函数

这个函数中主要是实现归并排序的核心逻辑,首先判断序列是否可以继续拆分,如果不能,直接返回。如果可以继续拆分,则需要将原序列拆分成两个子序列,mid 是拆分的中间位置,p1,p2 是两个子序列的指针。定义一个新的临时数组 tem,用于存放排序后的两个子序列的合并结果。

递归调用 merge_sort 函数进行排序,然后使用 while 循环将排好序的子序列进行合并,并存入临时数组 tem 中。最后将排序完成的临时数组 tem 复制回原先的序列中。

(2)main 函数

在 main 函数中,定义了一个数组 arr 作为待排序的数组,将其传入 merge_sort 函数中进行排序。最后输出排好序的数组。

4.总结

归并排序是一种非常实用的算法,其稳定性和高效率使其在各种数据处理场景中有着广泛的应用。本文提供的C++归并排序代码实现可以帮助读者更好的理解归并排序的实现原理,为读者提供了一个很好的样例,可以供大家参考借鉴。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复