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

C++归并排序代码实现

2023-06-30 20:20:37 深夜i -- --

C++ 归并排序代码实现

C++归并排序是一种基于分治策略的排序算法，其核心思想是将一个大问题拆分成小的子问题进行求解，然后将子问题的解合并起来得到大问题的解。这种算法的时间复杂度为O(nlogn)，具有稳定性，适用于大规模数据的排序。

下面给出C++归并排序的代码实现：

void merge(int arr[], int left, int mid, int right) {
  int* temp = new int[right - left + 1];
  int i = left;
  int j = mid + 1;
  int k = 0;
  while (i <= mid && j <= right) {
    if (arr[i] < arr[j]) {
      temp[k] = arr[i];
      k++;
      i++;
    }
    else {
      temp[k] = arr[j];
      k++;
      j++;
    }
  }
  while (i <= mid) {
    temp[k] = arr[i];
    k++;
    i++;
  }
  while (j <= right) {
    temp[k] = arr[j];
    k++;
    j++;
  }
  for (int i = left; i <= right; i++) {
    arr[i] = temp[i - left];
  }
  delete[] temp;
}
void mergeSort(int arr[], int left, int right) {
  if (left < right) {
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
  }
}

在以上代码中，`merge()`函数实现的是归并的过程，它将两个有序的子数组合并成一个有序的数组。`mergeSort()`函数则是整个归并排序的核心算法，它将原始数组递归地拆分成较小的子数组进行排序，然后再将子数组合并得到有序的数组。

使用C++归并排序可以实现非常高效的排序，并且代码实现也较为简单，值得程序员们深入学习和掌握。

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

下一篇: "VC++2010中的有趣代码"

评论区

相似文章