【数据结构】内部排序小结- -归并排序

Merge：合并

为啥会突然拽个英文，可以发现很多的代码和英文拼写相关，在命名时，术语命名也显得更加专业。merge是归并、合并的意思。

1 思想

• 将两个或两个以上的有序表组合成新的有序表。可以看作是一棵倒着的二叉树。
• 过程如下(以二路归并排序为例)
  
• 二路归并：两组元素一路，进行排序。
  最初，单个元素自成一组，两两结合，比较，写下来结果，得到第一趟的结果。
  对第一趟结果继续上述操作，得到第二趟结果。。。。。。
• 有没有发现和希尔排序有点相似：
  希尔排序也是分组，不同的是希尔排序分组，组间的第一跟第一比，第二跟第二比···
  归并排序是分组，组内比较。
• 二路归并：二合一
  K路归并：K合一

2 算法分析

• 稳定性：稳定
• 空间复杂度：O（ n ）
• 与初态是否有关：无关
• 时间复杂度：
  最好时间复杂度：O（ n log n）
  最坏时间复杂度：O（ n log n）
  平均时间复杂度：O（ n log n）

3 代码

//这里是归并排序
//辅助数组Ｂ
ElemType *B = (ElemType *)malloc( (n+1)*sizeof(EleType));
void Merge(ElemType A[],int low,int high,int mid) 
{	//表A[low…mid]和A[mid+1…high]
	for(int k=low;k<=high;k++)
		B[k] = A[k];//将A数组中的所有元素(包括了两组元素) 给Ｂ也来一份
	for(i=low,j=mid+1,k=i;  i<=mid && j<=high;  k++)
	{
		//比较Ｂ左右两端的元素，较小的放入A中，形成一个升序序列
		if(B[i]<=B[j])
			A[k] = B[i++];
		else
			A[k] = B[j++;]
	}
	while(i<=mid)//	如果A[low…mid]这边还有元素，另一边已经完成排序，就把未检测完的，复制
		A[k] = B[i++];
	while(j<=high) //第二个表未检测完，复制		A[k] = B[j++];
}



void MergeSort(ElemType A[],int low,int high)
{
	if(low<high)
	{
		int mid=(low+high)/2;//从中间劈开，划分成两个子表
		MergeSort(A,low,mid);//mid属于前一个表中元素，
		MergeSort(A,mid+1;high);//与快排不同，基准元素在中间，不属于任何一个子表；此处mid属于前一个子表，后一个表从mid+1开始
		MergeSort(A,low,mid,high);//归并
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

归并排序也能和树那一章联动。。