C++归并排序算法详解与代码修复

归并算法的核心逻辑

归并（Merge）是一种典型的分治策略应用。其基本意图是将两个已经排好序的线性表（数组），按照大小顺序逐一比较，将元素依次放入一个新的结果表中，从而形成一个全新的、整体有序的线性表。为了实现通用性，我们通常使用C++模板（Template）来定义函数，这样同一套代码可以同时处理整数、浮点数甚至字符数组。

准备工作与环境设置

在编写代码前，需要确保开发环境支持标准C++11或更高版本。主要依赖如下：

• <iostream>：用于标准输入输出流操作。
• system("pause")：Windows环境下防止控制台窗口闪退。

本示例中设定固定数据量为 n = 5，即每个输入数组包含5个元素，合并后结果为10个元素。

第1步：定义通用数据输出函数

为了观察合并后的结果，我们需要一个能够遍历并打印数组元素的模板函数。OutPut 接收一个大小为 2*n 的数组作为参数，通过循环逐个打印数据元素。

// 模版函数 输出线性表元素
template <class T1>
void OutPut(T1 out[(2*n)])
{ 
  for (int i=0; i<(2*n); i++)
  { 
    cout<<out[i]<<" ";
  }
  cout<<endl;
}

第2步：设计通用数据输入接口

使用模板函数 InPut 允许用户动态输入不同类型的数据（如 int, double, char）。该函数接受一个大小为 n 的数组引用，提示用户输入，并通过循环读取 cin 的值存入数组。

// 模版函数 输入线性表元素
template <class T2>
void InPut(T2 in[n])
{
  cout<<"请输入5个数据元素：";
  for (int i=0; i<n; i++)
  { 
    cin>>in[i];
  }
  cout<<endl;
}

第3步：实现内部排序功能

为了验证归并前的状态以及最终结果的准确性，代码中包含了一个基于冒泡排序的辅助模板函数 MySort。它接收一个数组，通过双重循环比较相邻元素并进行交换，直到数组有序。

// 模版函数 输入线性表元素并将其排序
template <class T3> 
void MySort(T3 a[2*n])
{
  int temp; //交换数据临时变量 
  //冒泡排序 
  for (int i=0; i<2*n-1; i++)
  {
   for (int j=0; j<2*n-1-i; j++)
   {
    if (a[j]>a[j+1]) 
    {
      temp = a[j];
      a[j] = a[j+1];
      a[j+1] = temp; 
    }
   }
  }
}

第4步：执行归并合并操作

这是核心部分 MergeList 函数。它接收两个源数组 La 和 Lb，以及目标数组 Lc。

1. 初始化指针：使用 i, j, k 分别指向 La, Lb 和 Lc 的起始位置。
2. 双路合并：当两个源数组都未遍历完时，比较当前元素。若 La[i] < Lb[j]，则将较小者放入 Lc，对应下标递增；否则放入另一个元素。
3. 处理剩余元素：当一个数组遍历完后，将另一个数组剩余的 all 元素直接追加到结果数组末尾。
4. 二次校验：合并结束后，再次调用 MySort 对合并后的长数组进行排序，以确保最终输出的绝对有序性（注：标准的归并排序应在此步骤前保证子数组有序且合并过程保持有序，此处代码逻辑为简化教学示例）。

// 模版函数 归并 
template <class T> 
void MergeList(T La[n], T Lb[n], T Lc[(2*n)]) 
{
  int i = 0; //作为La的下标 
  int j = 0; //Lb下标
  int k = 0; //Lc下标 
  
  while (i<n && j<n)
  {
   if (La[i] < Lb[j])
   {
     Lc[k++] = La[i++];
   }
   else if (La[i] > Lb[j])
   {
     Lc[k++] = Lb[j++];
   }
   else
   {
     Lc[k++] = La[i++];
     Lc[k++] = Lb[j++];
   }
  } 
  //如果La中的数据没有取完
  while (i<n)
  {
   Lc[k++] = La[i++];
  } 
  //如果Lb中的数据没有取完
  while (j<n)
  {
    Lc[k++] = Lb[j++];
  } 
  //对组合好的元素进行排序 
  MySort(Lc); 
}

第5步：主函数测试流程

在 main 函数中，我们定义了不同类型的测试用例：整型 (a1)、双精度浮点型 (b1) 和字符型 (m1)。以字符型为例，调用 InPut 输入两组数据，随后调用 MergeList 合并，最后通过 OutPut 显示结果。

int main()
{
 char m1[n], m2[n], m[(2*n)];
 
 InPut(m1);
 InPut(m2); 
 MergeList(m1,m2,m);
 OutPut(m); 
 
 system("pause");
 return 0;
}

常见问题与注意事项

在实际工程应用中，需注意以下几点以避免潜在错误： 1. 数组越界：原始草稿中的合并循环条件使用了 i<=n，这在严格意义上可能导致访问超出预分配长度的内存，建议修正为 i<n。 2. 逻辑冗余：真正的归并算法前提是输入数组本身已经有序，合并过程自然产生有序结果，通常不需要在合并后再次调用全量排序函数 MySort，这会降低算法效率至 O(N log N) 而非理想的 O(N)。

简要总结

本实例展示了如何利用C++模板机制封装通用的数据输入、排序及归并逻辑。通过理解数组下标的移动规则和数据比较方式，读者可以掌握线性表合并的基本算法思想。以上就是C++归并算法实例的详细内容，更多关于C++数据结构与算法优化的资料请关注本站其它相关文章！