归并排序分析与实现

发表于 | 分类于
字数统计: 654 word | 阅读时长 ≈ 2 min
归并排序

归并排序的基本思想是首先将 a[0···n-1] 看成n个长度为1的有序表，将相邻的k(k>=2)个有序子表成对归并，得到n/k个长度为k的有序子表；然后再将这些有序子表继续归并，得到n/k^2个长度为k^2的有序子表，如此反复进行下去，最后得到一个长度为n的有序表。若k=2，即归并是在相邻的两个有序子表中进行的，称为二路归并排序。若k>2，即归并操作在相邻的多个有序子表中进行，则叫多路归并排序。我们仅讨论二路归并排序。

分解—>子问题求解—>合并

代码实现
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 #include<iostream>
using namespace std;
void display(int a[],int n){    //输出数组元素
	for (int i = 0; i < n; i++){
		cout << a[i] << " ";
	}
}
//合并
void Merge(int a[], int left, int mid, int right){
	int *temp = new int[right - left + 1]; //定义并初始化临时数组
	int i = left;       //左边序列指针
	int j = mid + 1;    //右边序列指针
	int t = 0;          //临时数组指针
	while (i <= mid&&j <= right){ //第一个子表（左）和第二个子表（右）均没有扫描完时循环，左边子表和右边子表均从自己的第1个元素开始向右扫描
		if (a[i] <= a[j]){		  
			temp[t++] = a[i++];	  //如果第一个子表的当前元素值小，放入temp中
		}
		else{
			temp[t++] = a[j++];	  //如果第二个子表的当前元素值小，放入temp中
		}
	}
	while (i <= mid){             //如果第一个子表有剩余元素，则直接将剩余的元素填入temp中
		temp[t++] = a[i++];
	}
	while (j <= right){			  //如果第二个子表有剩余元素，则直接将剩余的元素填入temp中
		temp[t++] = a[j++];
	}
	t = 0;
	while (left <= right){		  //将temp中的元素全部复制到原数组中
		a[left++] = temp[t++];
	}
	delete[]temp;				  //释放临时空间
}
//归并排序
void MergeSort(int a[],int left,int right){
	if (left < right){                 //子序列有两个或两个以上元素
		int mid = (left + right) / 2;
		MergeSort(a, left, mid);	   //左边归并排序，使得左子序列有序
		MergeSort(a, mid + 1, right);  //右边归并排序，使得右子序列有序
		Merge(a, left, mid, right);	   //将两个有序子序列合并
	}
}
int main(){
	int a[9] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
	cout << "排序前： ";
	display(a,9);
	cout << endl;
	cout <<"排序后： ";
	MergeSort(a,0,8);
	display(a, 9);
}
0%