C++顺序表实现归并排序算法代码 |21xrx.com

C++顺序表实现归并排序算法代码

2023-07-05 16:53:15 深夜i 12 0

C++ 顺序表归并排序算法代码

C++ 顺序表实现归并排序算法代码

归并排序是一种经典的排序算法，它的主要思想是将待排序的序列切割成多个子序列，然后将子序列两两合并，直到最后整个序列排好序为止。对于这个算法，我们可以使用顺序表来实现。

以下是 C++ 语言实现归并排序算法的完整代码：

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
void merge(vector<int>& arr, int left, int mid, int right) {
  vector<int> temp(right - left + 1);
  int i = left, j = mid + 1, 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 p = 0; p < k; p++) {
    arr[left + p] = temp[p];
  }
}
void mergeSort(vector<int>& arr, int left, int right) {
  if (left >= right)
    return;
  
  int mid = left + (right - left) / 2;
  mergeSort(arr, left, mid);
  mergeSort(arr, mid + 1, right);
  merge(arr, left, mid, right);
}
int main() {
  vector<int> arr 7;
  int length = arr.size();
  mergeSort(arr, 0, length - 1);
  for (int i = 0; i < length; i++) {
    cout << arr[i] << " ";
  }
  return 0;
}

在上面的代码中，我们首先定义了一个函数 `merge()`，这个函数用来合并两个已排序的子序列。然后我们定义了一个递归函数 `mergeSort()`，这个函数会将待排序序列不断切分，并在切分结束后调用 `merge()` 函数进行合并排序。最后我们在 `main()` 函数中调用排序函数并输出排序结果。

这里的 `mergeSort()` 函数使用了顺序表来保存整个序列。归并排序算法的时间复杂度为 O(nlogn)，其中 n 表示序列中元素的个数。虽然归并排序的时间复杂度相比快速排序略慢，但它可以保证在任何一种情况下都能达到 O(nlogn) 的时间复杂度，且不会退化成 O(n^2) 的时间复杂度。因此，在实际应用中，归并排序仍然是一种非常优秀的排序算法。

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

下一篇: 如何使用C++的debug调试功能

评论区

相似文章