题目描述
使用归并排序进行排序
输入样例
5
3 1 2 4 5
输入样例
1 2 3 4 5
C 代码
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
//归并
void Merge(int* arr, int low, int mid, int high, int len) {
int i, j, k;
int* tempArr = (int*)malloc(sizeof(int) * len);//辅助数组
//先将左右两个有序序列放到辅助数组中
for (k = low; k <= high; k++)
{
tempArr[k] = arr[k];
}
//开始合并
/*
i指针指向辅助数组中第一个序列的起始位置
j指针指向辅助数组中第二个序列的起始位置
k指针指向整个原数组的起始位置
*/
for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++)
{
if (tempArr[i] <= tempArr[j])
{
arr[k] = tempArr[i++];
}
else
{
arr[k] = tempArr[j++];
}
}
//以下代码只会执行一个
while (i <= mid)
{
arr[k++] = tempArr[i++];//表示第一个表未检测完,复制
}
while (j <= high)
{
arr[k++] = tempArr[j++];//表示第二个表未检测完,复制
}
free(tempArr);
}
//归并排序
void MergeSort(int* arr, int low, int high, int len) {
if (low < high)
{
int mid = (low + high) / 2;//从中间划分
MergeSort(arr, low, mid, len);//对左半部分归并排序
MergeSort(arr, mid + 1, high, len);//对右半部分归并排序
Merge(arr, low, mid, high, len);//归并
}
}
int main() {
int n;
scanf("%d", &n);
int* arr = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
MergeSort(arr, 0, n - 1, n);
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
return 0;
}