C++合并排序算法详解 |21xrx.com

C++合并排序算法详解

2023-06-22 03:24:52 深夜i -- --

C++ 合并排序算法详解排序

合并排序是一种基于分治思想的高效排序算法，利用递归思想将待排序数组不断二分，直至只剩一个元素，然后将两个有序的序列归并为一个有序序列，最终得到一个排好序的数组。其中，归并部分是该算法的核心，也是实现的难点之一。

C++实现合并排序算法的代码如下：

void merge(vector<int> &arr, int left, int mid, int right) {
  int i = left, j = mid + 1, k = 0;
  vector<int> temp(right - left + 1); //定义临时数组
  while (i <= mid && j <= right) {
    if (arr[i] <= arr[j]) {
      temp[k++] = arr[i++];
    } else {
      temp[k++] = arr[j++];
    }
  }
  while (i <= mid) {
    temp[k++] = arr[i++];
  }
  while (j <= right) {
    temp[k++] = arr[j++];
  }
  for (i = left, k = 0; i <= right; i++, k++) {
    arr[i] = temp[k];
  }
}
void mergeSort(vector<int> &arr, int left, int right) {
  if (left >= right)
    return;
  
  int mid = (left + right) / 2;
  mergeSort(arr, left, mid);
  mergeSort(arr, mid + 1, right);
  merge(arr, left, mid, right);
}

以上代码中，函数merge() 实现了归并操作，它的参数arr是待排序数组，left、mid和right分别是左部分、右部分和右边界下标。在该函数里，定义了一个临时数组temp，大小为(right - left + 1)，然后将arr数组归并到temp数组中，最后将temp数组的元素复制回arr数组中。

函数mergeSort() 则是将arr数组分为左部分和右部分，再对左右部分分别递归调用mergeSort() 排序函数，最后调用merge()函数实现合并操作。函数的参数left和right分别表示数组的起始下标和结束下标。

合并排序算法的时间复杂度为O(nlogn)，空间复杂度为O(n)，因此，在处理大数据集时，合并排序算法具有更优性能的优点。

以上就是C++实现的合并排序算法详解，希望对大家有所帮助。

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

下一篇: C++组件异常对程序的影响分析

评论区

相似文章