【C++数据结构——内排序】二路归并排序（头歌实践教学平台习题）【合集】

#include <iostream>
#include <vector>
using namespace std;
// 二路归并函数，将两个有序数组A和B合并为一个有序数组C
vector<int> merge(vector<int>& A, vector<int>& B) {
    vector<int> C;
    int i = 0, j = 0;
    // 循环比较A和B数组的元素，将较小的元素放入C数组
    while (i < A.size() && j < B.size()) {
        if (A[i] <= B[j]) {
            C.push_back(A[i]);
            i++;
        } else {
            C.push_back(B[j]);
            j++;
        }
    }
    // 将A数组剩余的元素放入C数组（如果有剩余）
    while (i < A.size()) {
        C.push_back(A[i]);
        i++;
    }
    // 将B数组剩余的元素放入C数组（如果有剩余）
    while (j < B.size()) {
        C.push_back(B[j]);
        j++;
    }
    return C;
}

#include <malloc.h>
#include <stdio.h>
#define MAXL 100     //最大长度
typedef int KeyType; //定义关键字类型为int
typedef char InfoType;
typedef struct {
  KeyType key;   //关键字项
  InfoType data; //其他数据项，类型为InfoType
} RecType;       //查找元素的类型
int count = 1; //全局变量，记录第几趟归并
void CreateList(RecType R[], KeyType keys[], int n) //创建顺序表
{
  for (int i = 0; i < n; i++) // R[0..n-1]存放排序记录
    R[i].key = keys[i];
}
void DispList(RecType R[], int n) //输出顺序表
{
  for (int i = 0; i < n; i++)
    printf("%d ", R[i].key);
  printf("\n");
}
//一次归并：将两个有序表R[low..mid]和R[mid+1..high]归并为一个有序表R[low..high]中
void Merge(RecType R[], int low, int mid, int high) {
  /********** Begin *********/
  RecType *R1 = (RecType *)malloc((high - low + 1) * sizeof(RecType));
  int i = low, j = mid + 1, k = 0;
  while (i <= mid && j <= high) {
    if (R[i].key <= R[j].key)
      R1[k++] = R[i++];
    else
      R1[k++] = R[j++];
  }
  while (i <= mid)
    R1[k++] = R[i++];
  while (j <= high)
    R1[k++] = R[j++];
  for (k = 0, i = low; i <= high; i++, k++)
    R[i] = R1[k];
  free(R1);
  /********** End **********/
}
void MergePass(RecType R[], int length, int n) //实现一趟归并
{
  /********** Begin *********/
  int i;
  for (i = 0; i + 2 * length - 1 < n; i += 2 * length)
    Merge(R, i, i + length - 1, i + 2 * length - 1);
  if (i + length - 1 < n)
    Merge(R, i, i + length - 1, n - 1);
  /********** End **********/
}
void MergeSort(RecType R[], int n) //二路归并排序算法
{
  /********** Begin *********/
  int length = 1;
  printf("排序前:");
  DispList(R, n);
  while (length < n) {
    MergePass(R, length, n);
    printf("第%d趟归并:", count++);
    DispList(R, n);
    length *= 2;
  }
  printf("排序后:");
  DispList(R, n);
  /********** End **********/
}
int main() {
  /********** Begin *********/
  int n;
  scanf("%d", &n);
  KeyType keys[MAXL];
  RecType R[MAXL];
  for (int i = 0; i < n; i++)
    scanf("%d", &keys[i]);
  CreateList(R, keys, n);
  MergeSort(R, n);
  /********** End **********/
  return 0;
}