C++实现合并排序的代码 |21xrx.com

C++实现合并排序的代码

2023-06-29 09:00:38 深夜i -- --

C++ 合并排序代码

C++是一种面向对象的编程语言，因为它具有良好的抽象概念、数据封装和模块化机制，因此很受程序员的喜爱。而合并排序是一种非常重要的算法，用于将一个未排序的数组或列表排列成一个按照升序或降序的有序数组或列表。下面我们来看一下如何在C++中实现合并排序。

首先我们需要定义一个名为merge_sort的函数，用于对一个整型数组进行排序。该函数的代码如下所示：


void merge_sort(int arr[], int len)
{
  if (len <= 1) return;
  int middle = len / 2;
  int left[middle], right[len - middle];
  for (int i = 0; i < middle; i++)
    left[i] = arr[i];
  for (int i = middle; i < len; i++)
    right[i - middle] = arr[i];
  merge_sort(left, middle);
  merge_sort(right, len - middle);
  merge(arr, left, middle, right, len - middle);
}

在上述代码中，我们先判断传入的数组长度是否为1或者更小，如果是，直接返回不做任何操作。接着我们计算出数组中间位置的索引值，将数组分为前后两个部分，并将它们分别存储到名为left和right的数组当中。然后我们对left和right分别调用merge_sort函数进行递归排序。最后我们通过调用merge函数将排序后的左右两部分合并到原数组中。

下面我们来看一下merge函数的实现代码，该函数用于将排列好序的left和right数组合并到原数组arr中。代码如下所示：


void merge(int arr[], int left[], int left_len, int right[], int right_len)
{
  int i = 0, j = 0, k = 0;
  while (i < left_len && j < right_len)
  {
    if (left[i] < right[j])
      arr[k++] = left[i++];
    else
      arr[k++] = right[j++];
  }
  while (i < left_len)
    arr[k++] = left[i++];
  while (j < right_len)
    arr[k++] = right[j++];
}

在上述代码中，我们使用了三个指针i、j和k，分别表示左部分数组、右部分数组和合并后的数组的下标。然后我们将left和right数组中元素按照升序的方式依次合并到arr数组当中。最后，我们将left和right中剩余的元素追加到arr数组的末尾。

在这里，我们使用了递归的方式来实现合并排序，这种方法可以非常容易地理解和实现，并且在实际生产环境中也具有很好的效率。总的来说，C++是一种非常适用于算法实现的编程语言，我们可以利用C++的特性和标准库来实现各种有用的算法和数据结构。

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

下一篇: C++中的define头文件

评论区

()

相似文章