1.什么是归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子
序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。
2.算法步骤
1.把长度为n的输入序列分成两个长度为n/2的子序列;
2.对这两个子序列分别采用归并排序;
3.将两个排序好的子序列合并成一个最终的排序序列(此步骤需要开辟另外的内存空间).
3. 实例说明算法思想
4.动图说明归并排序的过程
5.代码演示
/*
文件名:MergeSort.c
作者:Muten
编码时间:20201027
编码目的:归并排序
测试环境:Mircosoft Visual Studio Professional 2015 版本14.0.25431.01 Update3
版本信息:VER1.0
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <sys/timeb.h>
#define MAX 5000000
long getSystemtime()
{
struct timeb tb;
ftime(&tb);
return tb.time * 1000 + tb.millitm;
}
// 创建数组
int *CreateArray()
{
srand((unsigned int)time(NULL));
int* arr = (int*)malloc(sizeof(int)*MAX);
for (int i = 0; i < MAX; i++)
{
arr[i] = rand()%MAX;
}
return arr;
}
void PrintArr(int arr[], int length)
{
for (int i = 0; i < length; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
// 合并算法
void Merge(int arr[], int start, int end, int mid, int* tmp)
{
int i_start = start;
int i_end = mid;
int j_start = mid + 1;
int j_end = end;
// 表示辅助空间有多少个元素
int length = 0;
// 合并两个有序序列
while (i_start <= i_end && j_start <= j_end)
{
if (arr[i_start] < arr[j_start])
{
tmp[length] = arr[i_start];
length++;
i_start++;
}
else {
tmp[length] = arr[j_start];
length++;
j_start++;
}
}
// i这个序列还有剩余元素
while (i_start <= i_end)
{
tmp[length] = arr[i_start];
i_start++;
length++;
}
// j这个序列还有剩余元素
while (j_start <= j_end)
{
tmp[length] = arr[j_start];
j_start++;
length++;
}
// 辅助空间的数据覆盖到原来空间
for (int i = 0; i < length; i++)
{
arr[start + i] = tmp[i];
}
}
// 归并排序
void MergeSort(int arr[],int start,int end,int* temp)
{
if (start >= end)
return;
int mid = (start + end) / 2;
// 左半边
MergeSort(arr,start,mid,temp);
// 右半边
MergeSort(arr, mid+1, end, temp);
Merge(arr,start,end,mid,temp);
}
int main()
{
int* myArr = CreateArray();
//PrintArr(myArr,MAX);
int* temp = (int*)malloc(sizeof(int)*MAX);
long t_merge_start_1 = getSystemtime();
MergeSort(myArr,0,MAX-1, temp);
long t_merge_end_1 = getSystemtime();
printf("归并排序%d个元素,所需时间:%ld 毫秒\n", MAX, t_merge_end_1 - t_merge_start_1);
//PrintArr(myArr, MAX);
free(temp);
free(myArr);
}
6.代码测试结果