C++合并排序算法代码 |21xrx.com

C++合并排序算法代码

2023-07-07 01:11:00 深夜i -- --

C++ 合并排序算法代码

合并排序（Merge Sort）是一种基于分治思想的经典排序算法。它的最坏时间复杂度为 O(nlogn)，适用于任何数据类型，尤其适用于链表和树这种不易插入的数据结构中。

下面是C++的合并排序算法代码：


void merge(int arr[], int l, int m, int r) {
  int n1 = m - l + 1;
  int n2 = r - m;
  int L[n1], R[n2];
  for (int i = 0; i < n1; i++)
    L[i] = arr[l + i];
  for (int j = 0; j < n2; j++)
    R[j] = arr[m + 1 + j];
  int i = 0, j = 0, k = l;
  while (i < n1 && j < n2) {
    if (L[i] <= R[j]) {
      arr[k] = L[i];
      i++;
    }
    else {
      arr[k] = R[j];
      j++;
    }
    k++;
  }
  while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
  }
  while (j < n2) {
    arr[k] = R[j];
    j++;
    k++;
  }
}
void mergeSort(int arr[], int l, int r) {
  if (l < r) {
    int m = l + (r - l) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
  }
}

其中，`merge`函数实现了两个已经排好序的子数组的合并，`mergeSort`函数利用递归来对整个数组排序。

使用时，将需要排序的数组和其起始和终止下标传入`mergeSort`函数即可。例如：


int main() {
  int arr[] = 9;
  int arr_size = sizeof(arr) / sizeof(arr[0]);
  mergeSort(arr, 0, arr_size - 1);
  cout << "Sorted array: \n";
  printArray(arr, arr_size);
  return 0;
}

输出为：

Sorted array: 1 5 7 8 9 10

需要注意的是，在合并子数组时，我们使用了循环而不是递归来实现。这是因为使用递归，虽然会使代码更加简单，但也会增加额外的空间复杂度，从而影响算法效率。

总的来说，C++的合并排序算法是一种优秀的排序算法，适用于各种数据结构和应用场景。使用时只需要简单的调用即可，代码简单易懂，也方便使用者进行二次开发。

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

下一篇: Node.js WebSocket 身份认证实现

评论区

()

相似文章