算法基础之十大基础排序算法

算法基础之归并排序
归并排序是把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。先把待排序列分为两部分，然后各部分再分为两部分，一直分下去，直到不能再分为止，然后在两两合并两个有序数组，直到合并完为止。下面来看一下代码：

#include<iostream>
using namespace std;
void Merge(int data[],int left,int center,int right){
	int length = right-left+1;
	int tmpIndex = 0,*tmp;
	tmp = new int[length];
	int s_left = left;
	int s_right = center+1;
	while(s_left <= center && s_right <= right){
		if(data[s_left] <= data[s_right])
			tmp[tmpIndex++] = data[s_left++];
		else
			tmp[tmpIndex++] = data[s_right++];
	}
	while(s_right <= right){
		tmp[tmpIndex++] = data[s_right++];
	}
	while(s_left <= center){
		tmp[tmpIndex++] = data[s_left++];
	}
	tmpIndex = 0;
	while(tmpIndex<length){
		data[left+tmpIndex] = tmp[tmpIndex++];
	}
}
void MergeSort(int data[],int left,int right){
	if(left<right){
		int center = (left+right) >> 1;
		MergeSort(data,left,center);
		MergeSort(data,center+1,right);
		Merge(data,left,center,right);
	}	
}

int main(){
	int *num,n;
	cin>>n;
	num = new int[n];
	for(int i=0;i<n;i++)
		cin>>num[i];
	MergeSort(num,0,n-1); 
	for(int i=0;i<n;i++)
		cout<<num[i]<<"  ";
	return 0;
} 
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

下面来一张图片演示一下归并排序：