【排序算法】----详解归并排序算法

1.归并排序

原理，首先将数组递归的分解，直到达到终止条件返回，然后将分成两段的数组，进行比较，按从小到大的顺序放在临时数组里，然后将这一段排好顺序的数组复制给原来的数组，继续返回上一层，进行排序。直到完全完成递归。 图解

2.代码展示

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void Print(int* arr, int n)
{
          
   
	for (int i = 0; i <n; i++)
	{
          
   
		printf("%d ", arr[i]);
	}
	printf("
");
}

void Merge(int* arr, int  begin, int end,int* tmp)
{
          
   
	if (begin >= end)
	{
          
   
		return;
	}
	int mid = (begin + end) >> 1;
	Merge(arr, begin, mid,tmp);
	Merge(arr, mid + 1, end,tmp);
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1,end2 = end;
	int index = begin;
	while (begin1 <=end1 && begin2 <= end2)
	{
          
   
		if (arr[begin1] > arr[begin2])
		{
          
   
			tmp[index++] = arr[begin2++];
		}
		else
		{
          
   
			tmp[index++] = arr[begin1++];
		}
	}
	//第二段结束了，第一段还有
	if (begin1 <= end1)
	{
          
   
		while (begin1<=end1)
		{
          
   
			tmp[index++] = arr[begin1++];
		}
	}
	//第一段结束了，第二段还有
	else
	{
          
   
		while (begin2 <= end2)
		{
          
   
			tmp[index++] = arr[begin2++];
		}
	}
	//每次都要拷贝回原数组，并且长度为为end-begin+1个
	memcpy(arr + begin, tmp + begin, sizeof(int)*(end - begin+1));
}

void MergeSort(int* arr,int n)
{
          
   
	int *tmp = (int *)malloc(sizeof(int)*n);
	Merge(arr, 0, n-1,tmp);
	free(tmp);
}

int main()
{
          
   
	int arr[] = {
          
    14,12,13,15,11,16};
	int n = sizeof(arr) / sizeof(arr[0]);
	MergeSort(arr, n );
	Print(arr, n);
	system("pause");
	return 0;
}

3.结果展示

4.复杂度分析

时间复杂度 O(nlogn) 空间复杂度 O(n)

5.心得体会

实现算法的时候，先分解然后在合并，一定要理清楚步骤。