21xrx.com
2025-04-01 00:15:29 Tuesday
文章检索 我的文章 写文章
C++顺序表实现归并排序算法代码
2023-07-05 11:54:02 深夜i     12     0
C++ 顺序表 归并排序 算法 代码

C++顺序表实现归并排序算法是一种常见的排序算法，它可以在O(n log n)的时间复杂度下对数组进行排序。通过将数组拆分成几个小部分，归并排序算法将这些部分分别排序并合并成一个更大的数组，最终得到完全有序的数组。

以下是使用C++顺序表实现归并排序算法的示例代码：

#include<iostream>
using namespace std;
const int MAXSIZE = 10;  // 顺序表最大长度
typedef struct {
  int r[MAXSIZE+1];  // 存储表中元素，下标从1开始
  int length;     // 顺序表长度
} SqList;
void merge(int SR[], int TR[], int i, int m, int n) {
  int j, k, l;      // j和k是TR的起始下标，l是SR的起始下标
  for (j = m+1, k = i; i <= m && j <= n; k++) {  // 将SR中记录归并到TR中
    if (SR[i] < SR[j])
      TR[k] = SR[i++];
    else
      TR[k] = SR[j++];
  }
  if (i <= m) {
    for (l = 0; l <= m-i; l++)
      TR[k+l] = SR[i+l];  // 将剩余的SR中记录复制到TR中
  }
  if (j <= n) {
    for (l = 0; l <= n-j; l++)
      TR[k+l] = SR[j+l];  // 将剩余的SR中记录复制到TR中
  }
}
void mergePass(int SR[], int TR[], int s, int n) {
  int i = 1;
  int j;
  while (i <= n-2*s+1) {
    merge(SR, TR, i, i+s-1, i+2*s-1);  // 两两归并
    i += 2*s;
  }
  if (i < n-s+1) {
    merge(SR, TR, i, i+s-1, n);  // 归并最后两个序列
  } else {
    for (j = i; j <= n; j++)
      TR[j] = SR[j];  // 将剩余的SR中记录复制到TR中
  }
}
void mergeSort(SqList &L) {
  int *TR = new int[L.length+1];  // 备份数组
  for (int i = 1; i < L.length+1; i++)
    TR[i] = L.r[i];  // 复制待排序数组到备份数组
  for (int s = 1; s < L.length; s *= 2)
    mergePass(TR, L.r, s, L.length);
  delete[] TR;  // 释放备份数组
}
int main() {
  SqList L;
  int a[10] = {2,3,6,1,6,4,8,9,5,7};
  for (int i = 0; i < 10; i++) {  // 初始化待排序数组
    L.r[i+1] = a[i];
  }
  L.length = 10;
  mergeSort(L);  // 排序
  // 输出排序后的数组
  for (int i = 1; i < L.length+1; i++) {
    cout << L.r[i] << ' ';
  }
  return 0;
}

在上述代码中，`merge`函数用于将两个有序序列归并成一个有序序列，`mergePass`函数用于对每一对有序序列进行一次归并操作，`mergeSort`函数是归并排序的主要函数，它先将待排序数组复制到备份数组中，再进行归并排序，在排序完成后将排序后的结果复制回原数组中。最后，在`main`函数中，我们初始化了一个长度为10的待排序数组并进行了排序，输出排序结果。

总之，C++顺序表实现归并排序算法可以方便地对数组进行排序，是一种非常实用的算法。

  
  

评论区