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

目录😋

任务描述

测试说明

我的通关代码:

测试结果：

---

任务描述

本关任务：实现二路归并算法。

测试说明

平台会对你编写的代码进行测试：

测试输入示例：
11
18 2 20 34 12 32 6 16 5 8 1 
(说明：第一行是元素个数，第二行是待排序的原始关键字数据。）

输出示例：
排序前:18 2 20 34 12 32 6 16 5 8 1 
第1趟归并:2 18 20 34 12 32 6 16 5 8 1 
第2趟归并:2 18 20 34 6 12 16 32 1 5 8 
第3趟归并:2 6 12 16 18 20 32 34 1 5 8 
第4趟归并:1 2 5 6 8 12 16 18 20 32 34 
排序后:1 2 5 6 8 12 16 18 20 32 34 

开始你的任务吧，祝你成功！

---

我的通关代码:

#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++];elseR1[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;
}

测试结果：