C++实现合并排序算法 |21xrx.com

C++实现合并排序算法

2023-07-05 10:25:25 深夜i -- --

C++ 合并排序算法

合并排序算法是一种基于分治策略的有效排序算法。它将待排序的序列分成两个子序列，对这两个子序列分别进行递归排序，然后将它们合并成一个有序序列。

C++是一种广泛使用的编程语言，它提供了许多内置函数和特性，使合并排序算法的实现变得简单和高效。

下面是一个简单的C++代码实现，它演示了如何使用递归的思想来实现合并排序算法。


#include <iostream>
using namespace std;
void mergeSort(int arr[], int leftIndex, int rightIndex)
{
  if (leftIndex < rightIndex)
  {
    int middleIndex = (leftIndex + rightIndex) / 2;
    // 递归地排序左子序列
    mergeSort(arr, leftIndex, middleIndex);
    // 递归地排序右子序列
    mergeSort(arr, middleIndex + 1, rightIndex);
    // 合并左右子序列
    int leftArray[middleIndex - leftIndex + 1];
    int rightArray[rightIndex - middleIndex];
    for (int i = 0; i < middleIndex - leftIndex + 1; i++)
      leftArray[i] = arr[leftIndex + i];
    for (int j = 0; j < rightIndex - middleIndex; j++)
      rightArray[j] = arr[middleIndex + j + 1];
    int i = 0, j = 0, k = leftIndex;
    while (i < middleIndex - leftIndex + 1 && j < rightIndex - middleIndex)
    {
      if (leftArray[i] <= rightArray[j])
      {
        arr[k] = leftArray[i];
        i++;
      }
      else
      {
        arr[k] = rightArray[j];
        j++;
      }
      k++;
    }
    while (i < middleIndex - leftIndex + 1)
    {
      arr[k] = leftArray[i];
      i++;
      k++;
    }
    while (j < rightIndex - middleIndex)
    {
      arr[k] = rightArray[j];
      j++;
      k++;
    }
  }
}
int main()
{
  int arr[] = 4;
  int n = sizeof(arr) / sizeof(arr[0]);
  mergeSort(arr, 0, n - 1);
  for (int i = 0; i < n; i++)
    cout << arr[i] << " ";
  return 0;
}

在这个例子中，我们首先通过计算得到序列的中间索引，然后递归地将左子序列和右子序列排序，然后将它们合并成一个有序序列。在合并过程中，我们使用了额外的数组来保存左右子序列，然后按照大小顺序向原始数组中填充数据。

这个实现的时间复杂度为O(n log n)，空间复杂度为O(n)。

总之，C++提供了许多内置函数和工具，使合并排序算法的实现变得简单和高效。了解和掌握这种方法将有助于您提高对C++编程的理解和技能。

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

下一篇: 从问题分析到程序设计：C++基础教程

评论区

()

相似文章