排序算法：归并排序算法实现及分析

末蓝、 2022-05-31 12:36 280阅读 0赞

# 归并排序算法介绍 #

归并排序（Merging Sort）就是利用归并的思想实现排序的放。它的原理**是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并,.....，如此重复，直到得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。**

# 归并排序算法图解 #

![20180224235827721][]

# 归并排序算法代码 #

其实归并排序思路很好理解，**就是将2个有序的序列合并，整个序列都是无序的哪里去找有序的序列？我们可以无限递归，将其划分为1个元素的序列，这时肯定是有序的咯，然后一路归并排序 就ok呀**。主要是合并代码，仔细看 是不是应该这样去合并！

//归并排序的合并数组函数 升序
    void Merge_Up(int *arr, int start, int mid, int  end, int *temp)
    {
    	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])
    		{
    			temp[length] = arr[i_start];
    			length++;
    			i_start++;
    		}
    		else
    		{
    			temp[length] = arr[j_start];
    			length++;
    			j_start++;
    		}
    	}
    	//将剩余没有放完的放置到辅助空间中去
    	while (i_start <= i_end)
    	{
    		temp[length] = arr[i_start];
    		length++;
    		i_start++;
    	}
    	while (j_start <= j_end)
    	{
    		temp[length] = arr[j_start];
    		length++;
    		j_start++;
    	}
    
    	//将辅助空间的值复制到源数组
    	for (int i = 0; i < length; i++)
    	{
    		arr[start + i] = temp[i];
    	}
    	return;
    }
    
    /*
    归并排序
    	@param arr 归并排序的数组
    	@param start 开始下标
    	@param end 结束下标
    	@param temp 辅助空间
    */
    void MergeSort_Up(int *arr,int start,int end,int* temp)
    {
    	if (start >= end)
    	{
    		return;
    	}
    	int mid = (start + end )/ 2;
    	//分组
    	//左半部分 进行归并排序
    	MergeSort_Up(arr, start, mid, temp);
    	//右半部分 进行归并排序
    	MergeSort_Up(arr, mid + 1, end, temp);
    
    	//合并排序好的2个数组
    	Merge_Up(arr, start, mid, end, temp);
    
    }

# 完整代码 #

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <sys/timeb.h>
    #define MAXSIZE 1000000
    //交换值
    void Swap(int* a, int* b)
    {
    	int temp = *a;
    	*a = *b;
    	*b = temp;
    }
    //打印数组元素
    void PrintArr(int* arr, int length)
    {
    	for (int i = 0; i < length; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    	return;
    }
    long GetSysTime()
    {
    	struct timeb tb;
    	ftime(&tb);
    	return tb.time * 1000 + tb.millitm;
    }
    //归并排序的合并数组函数 降序
    void Merge_Down(int *arr, int start, int mid, int  end, int *temp)
    {
    	int i_start = start;
    	int i_end = mid;
    	int j_start = mid + 1;
    	int j_end = end;
    	int length = 0;
    	//只有 1个元素时肯定是有序的，做为递归函数的出口。
    	if (start >= end)
    	{
    		return;
    	}
    
    	while (i_start <= i_end && j_start <= j_end)
    	{
    		//降序 我大先放我
    		if (arr[i_start] > arr[j_start])
    		{
    			temp[length] = arr[i_start];
    			length++;
    			i_start++;
    		}
    		else
    		{
    			temp[length] = arr[j_start];
    			length++;
    			j_start++;
    		}
    	}
    
    	//将辅助空间的值复制到源数组
    	for (int i = 0; i < length; i++)
    	{
    		arr[start + i] = temp[i];
    	}
    
    }
    //归并排序的合并数组函数 升序
    void Merge_Up(int *arr, int start, int mid, int  end, int *temp)
    {
    	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])
    		{
    			temp[length] = arr[i_start];
    			length++;
    			i_start++;
    		}
    		else
    		{
    			temp[length] = arr[j_start];
    			length++;
    			j_start++;
    		}
    	}
    	//将剩余没有放完的放置到辅助空间中去
    	while (i_start <= i_end)
    	{
    		temp[length] = arr[i_start];
    		length++;
    		i_start++;
    	}
    	while (j_start <= j_end)
    	{
    		temp[length] = arr[j_start];
    		length++;
    		j_start++;
    	}
    
    	//将辅助空间的值复制到源数组
    	for (int i = 0; i < length; i++)
    	{
    		arr[start + i] = temp[i];
    	}
    	return;
    }
    
    /*
    归并排序
    	@param arr 归并排序的数组
    	@param start 开始下标
    	@param end 结束下标
    	@param temp 辅助空间
    */
    void MergeSort_Up(int *arr,int start,int end,int* temp)
    {
    	if (start >= end)
    	{
    		return;
    	}
    	int mid = (start + end )/ 2;
    	//分组
    	//左半部分 进行归并排序
    	MergeSort_Up(arr, start, mid, temp);
    	//右半部分 进行归并排序
    	MergeSort_Up(arr, mid + 1, end, temp);
    
    	//合并排序好的2个数组
    	Merge_Up(arr, start, mid, end, temp);
    
    }
    
    
    int main(int argc, char *argv[])
    {
    	srand((size_t)time(NULL));//设置随机种子
    	int arr[10] = { 6,8,2,3,9,7,4,1,5,10 };
    	int *arr2 = (int*)malloc(sizeof(int)*MAXSIZE);
    	//int *arr3 = (int*)malloc(sizeof(int)*MAXSIZE);
    	//给每个元素设置一个随机值
    	for (int i = 0; i < MAXSIZE; i++)
    	{
    		int num = rand() % MAXSIZE;
    		arr2[i] = num;
    		//arr3[i] = num;
    	}
    	int *temp = (int*)malloc(sizeof(int)*10);
    	int *temp1 = (int*)malloc(sizeof(int) * MAXSIZE);
    
    	printf("排序前：\n");
    	PrintArr(arr, 10);
    	MergeSort_Up(arr, 0, 9, temp);
    	printf("归并排序升序：\n");
    	PrintArr(arr, 10);
    	long start = GetSysTime();
    	MergeSort_Up(arr2, 0, MAXSIZE - 1, temp1);
    	long end = GetSysTime();
    	printf("%d个元素 归并排序耗费%d毫秒\n",MAXSIZE,end-start);
    	return 0;
    }

# 代码运行检测 #

![20180225001019773][]

[20180224235827721]: /images/20220531/ef2c2193cf584b0e9f786ff8231e67d3.png
[20180225001019773]: /images/20220531/67a9a829756e4a3c9873ff3cc32f5470.png