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

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

2023-07-05 13:10:09 深夜i 17 0

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

C++ 编程语言中，顺序表实现归并排序算法是一种常见的排序方式。归并排序算法的思想是将待排序的元素拆分为若干个子序列，对每个子序列进行排序后再合并成一个有序序列。

下面是 C++ 语言中使用顺序表实现归并排序算法的代码：

#include <iostream>
using namespace std;
#define MAXSIZE 50
typedef struct {
  int r[MAXSIZE + 1];
  int length;
} SqList;
void Merge(SqList &L, int low, int mid, int high) {
  int i, j, k;
  int *B = new int[MAXSIZE + 1];
  for (k = low; k <= high; k++)
    B[k] = L.r[k];
  for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
    if (B[i] <= B[j])
      L.r[k] = B[i++];
    else
      L.r[k] = B[j++];
  }
  while (i <= mid) L.r[k++] = B[i++];
  while (j <= high) L.r[k++] = B[j++];
  delete []B;
}
void MSort(SqList &L, int low, int high) {
  if (low < high) {
    int mid = (low + high) / 2;
    MSort(L, low, mid);
    MSort(L, mid + 1, high);
    Merge(L, low, mid, high);
  }
}
void MergeSort(SqList &L) {
  MSort(L, 1, L.length);
}
int main() {
  SqList L = { 80, 9};
  MergeSort(L);
  for (int i = 1; i <= L.length; i++)
    cout << L.r[i] << " ";
  cout << endl;
  return 0;
}

上述代码实现了归并排序算法的分治过程，通过将待排序序列不断拆分为两个子序列，分别对其进行排序并合并，最终得到一个有序序列。

具体实现中，使用了 `Merge` 函数对两个有序序列进行合并，并将结果存储在原序列中。 `MSort` 函数为归并排序算法的核心部分，通过递归调用对子序列进行排序。而 `MergeSort` 函数则将待排序序列作为参数传入，对其进行排序。

最后，使用示例程序将顺序表中的元素排序并输出结果。

总之，C++ 顺序表实现归并排序算法是一种高效的排序方式，通过代码实现，可以更好地掌握其思想和实现原理。

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

下一篇: C++如何保留两位小数

评论区

相似文章