#include <stdio.h>
#include <stdlib.h>
#include<time.h>
#include<string.h>
#define N 7
// 定义元素类型为整型
typedef int ElemType;
// 定义静态表结构体
typedef struct{
ElemType *elem; // 动态分配的数组指针
int TableLen; // 表长度
} SSTable;
// 初始化静态表
void STInit(SSTable &ST, int len) {
ST.TableLen = len; // 设置表长度
ST.elem = (ElemType *)malloc(sizeof(ElemType)*ST.TableLen); // 分配内存
int i;
srand(time(NULL)); // 使用当前时间作为随机数种子
for(i = 0; i < ST.TableLen; i++){ // 循环初始化数组元素
ST.elem[i] = rand()%100; // 随机填充元素（0-99）
}
}
// 打印静态表内容
void STPrint(SSTable ST){
for(int i = 0; i < ST.TableLen; i++){
printf("%3d",ST.elem[i]); // 打印元素，右对齐，总宽度为3个字符
}
printf("\n"); // 换行
}
// 合并两个已排序的子数组
void Merge(ElemType A[], int low, int mid, int high) {
// 创建临时数组B来存储原始数组A的数据
static ElemType B[N];
// 复制原始数组A的数据到临时数组B中
int i;
for (i = low; i <= high; i++) {
B[i] = A[i];
}
// 初始化指针
int k = low; // 指向最终排序数组的位置
int j = mid + 1; // 指向右半部分数组的起始位置
// 比较左右两部分数据，并将较小者放入数组A中
for (i = low; i <= mid && j <= high;) {
if (B[i] < B[j]) {
A[k] = B[i];
i++;
k++;
} else {
A[k] = B[j];
j++;
k++;
}
}
// 如果左半部分还有剩余元素，则将其复制到数组A中
while (i <= mid) {
A[k] = B[i];
i++;
k++;
}
// 如果右半部分还有剩余元素，则将其复制到数组A中
while (j <= high) {
A[k] = B[j];
j++;
k++;
}
}
// 归并排序主函数
void MergeSort(ElemType *A, int low, int high) {
if (low < high) {
// 计算中间点来分割数组
int mid = (low + high) / 2;
// 对左半部分进行递归排序
MergeSort(A, low, mid);
// 对右半部分进行递归排序
MergeSort(A, mid + 1, high);
// 合并两个已排序的子数组
Merge(A, low, mid, high);
}
}
int main(){
SSTable ST;
STInit(ST,7); // 初始化静态表，设置长度为10
//ElemType A[10]={3,87,2,93,78,56,61,38,12,40};
//memcpy(ST.elem,A,sizeof(A));
STPrint(ST); // 打印未排序的静态表
MergeSort(ST.elem,0,6); // 调用归并排序函数，对静态表中的数据进行排序
STPrint(ST); // 再次打印静态表，这次是排序后的结果
scanf("%d"); // 防止程序立即退出
return 0;
}
