23-数据结构-内部排序-归并排序

目录

归并排序

一、简介：

二、思路

三、代码

---

归并排序

一、简介：

        归并，也叫合并，合二为一嘛，归并排序实际上相当于二叉树递归，先左右拆分，最后给数组拆分为每个数据为独立个体，再执行合并操作。

时间复杂度：O()-----口令：快（快速排序）以归（归并排序）队（堆排序）

空间复杂度：O(n)因为需要临时数组几个数据，临时数组大小就是几个。口令--饿鬼（归并）炸鸡（基数排序）块

稳定性：稳定，因为归并的时候，优先归并前面那个范围的，相对位置不贵发生改变，

口令--稳稳的幸福，鸡（基数排序）毛（冒泡排序）插（直接插入和折半插入排序）龟（归并排序）壳

排序趟数：对N个元素进行K路归并，排序排序趟数t等于t=向上取整。

移动次数：N个元素，进行k路归并，移动元素个数为：N*

二、思路

归并排序主要分为两步：第一步，给数组左右拆分；第二步两两合并

第一步，给数组左右拆分：

1. 给数组传进两个标记，表示数组范围，分别为low和high
2. 当low
3. 然后进入递归，左边递归数组范围时low和mid右边递归范围时mid+1和high。
4. 就这样层层递归，递归到最后，每个数据都成叶子结点了，再执行归并操作，但一个元素时肯定有序，所以返回倒数第二层，执行归并操作，依次往上返。
5. 步骤如图所示，但是，原理是图中从最下层开始递归，然后递归到最后，都递归成叶子结点了，返回倒数第二层开始第一次归并操作，开始两两合并，选大小。
6. 

第二步两两合并：

1. 叶子结点时，归并操作没用，因为只有一个元素，肯定有序，因此往倒数第二层返回，执行倒数第二层的归并操作。
2. 归并时，我们是传了三个坐标，low，mid和high。
3. 先创建个临时数组，给原数组的数值复制进去，用来对比最大或最小值，
4. 再定义一个实际坐标，指向实际数组中要存放的位置，
5. 就这个要存放的位置，来个循环，每次循环的时候，进行low到mid这个范围和mid+1到high这个范围进行比对，然后二选一存放值。
6. 如果最后两两没法对比了，再给剩下的都放进实际数组即可

三、代码

#include <stdio.h>
#include <malloc.h>
void PrintSort(int *a,int len)
{
	int i=0;
	for(i=0;i<len;i++)
	{
		printf("%d ",a[i]);
	}
	printf("\n");
} 
void Merge(int *a,int low,int mid,int high)
{
	int *b=(int*)malloc((high+1)*sizeof(int));
	int i;
	for(i=low;i<=high;i++)
	{
		b[i]=a[i];//临时数组，存进去值，用来取值比较。	
	}
	//k为a数组实际指向的箭头 
	int k=low;
	//用p，q两个箭头分别指向b数组中两个紧挨着的有序数组，然后判断谁打谁小，随后给a[k]重新赋值 
	int p,q;
	//两数组对比，然后选出一个，赋值到a中，随后k++，a数组换下一个坐标接着重复 步骤 
	for(p=low,q=mid+1,k=low;p<=mid&&q<=high;k++)
	{
		//在临时数组b中进行对比选择，最后赋值到实际数组a中 
		if(b[p]<=b[q]) 
		{
			a[k]=b[p];
			p++;
		}
		else
		{
			a[k]=b[q];
			q++;
		}
	}
	//如果对比完，还有一个数组没有对比完，接着往后赋值即可。 
	while(p<=mid)
	{
		a[k]=b[p];
		k++;
		p++;	
	}	
	while(q<=high)
	{
		a[k]=b[q];
		k++;
		q++;
	}
}
void MergeSort(int *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()
{
	int a[7]={49,38,65,97,76,13,27};
	
	MergeSort(a,0,6);
	
	
	PrintSort(a,7);
	return 0;
}