归并排序
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and
Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。//取自百度百科
思想：
分组：将无序的序列从中间分割成两组，直到每组数都只有一个或者两个数。如果一组数只有一个数字，不用进行处理；如果一组数有两个数字，将它们排序。也就是说分组环节会出现三种情况，一组数超过两个数（继续分组）、一组数有两个数（排序）、一组数只有一个数（不用处理）。
合并：将这些数每两组每两组合并起来，直到全部合成一组。
也就是 分组，排序，合并。
代码实现如下
由于采用递归，第六、七行代码执行完后对应的组已经排好序，因此直接合并两组即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
void MergeSort(int a[],int left,int right)//归并排序
{
if(left<right-1)//如果该组数字个数大于2
{
int mid=(left+right)/2;
MergeSort(a,left,mid);
MergeSort(a,mid+1,right);//分割
Merge(a,left,right,mid);//合并
}
else if(left==right-1)//如果该组数字个数等于2
{
if(a[left]>a[right])//如果前一个数字比后一个数字大，交换
{
int z=a[left];
a[left]=a[right];
a[right]=z;
}
}
//如果该组数字只剩一个，不用处理
}
|
合并操作
举个例子
这里有两个被分割开的组 3 4 9 8 和 2 5 1
经过递归和排序以后它们变成了 3 4 8 9 和 1 2 5
用两个数one和two分别指向第一组和第二组的第一个数
也就是one指向3，two指向1
3 4 8 9 1 2 5
↑ ↑
one two
对比one和two所指的数的大小，将小的那个数排下来
此处是two所指比较小，所以将two所指的1移下来，并将two右移
以此类推
3 4 8 9 1 2 5
↑ ↑
one two
1
3 4 8 9 1 2 5
↑ ↑
one two
1 2
3 4 8 9 1 2 5
↑ ↑
one two
1 2 3
3 4 8 9 1 2 5
↑ ↑
one two
1 2 3 4
3 4 8 9 1 2 5
↑ ↑
one two
1 2 3 4 5
此时第二个数组的数已经全部排下去
而第一个数组却还有剩余
由于剩余的数有序且必定比此时排在下面的最大的数要大
因此直接把剩余的数全部排下去即可
3 4 8 9 1 2 5
↑ ↑
one two
1 2 3 4 5 8 9
合并的代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
void Merge(int a[],int left,int right,int mid)//合并两组数字
{
int j,i=0;//循环，计数用
int one=left;
int two=mid+1;//one two分别指向第一 第二组数的第一个数字
int temp[right-left+1];//用来存排序数的临时数组，长度为两组数字个数总和
while(one<=mid&&two<=right)//当两组数字都未全部移入临时数组
{
if(a[one]>a[two])//如果one所指数大于two所指的数
temp[i++]=a[two++];//将two所指的数移入临时数组，two右移
else
temp[i++]=a[one++];
}
while(one<=mid)//当第一个数组中还有数未移入临时数组
temp[i++]=a[one++];
while(two<=right)
temp[i++]=a[two++];
i=0;
for(j=left;j<=right;j++)//将临时数组的数移入原数组
a[j]=temp[i++];
}
|
以下是全部代码
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
52
53
54
55
56
57
58
59
60
61
62
|
#include <stdio.h>
void Merge(int a[],int left,int right,int mid)//合并两组数字
{
int j,i=0;//循环，计数用
int one=left;
int two=mid+1;//one two分别指向第一 第二组数的第一个数字
int temp[right-left+1];//用来存排序数的临时数组，长度为两组数字个数总和
while(one<=mid&&two<=right)//当两组数字都未全部移入临时数组
{
if(a[one]>a[two])//如果one所指数大于two所指的数
temp[i++]=a[two++];//将two所指的数移入临时数组，two右移
else
temp[i++]=a[one++];
}
while(one<=mid)//当第一个数组中还有数未移入临时数组
temp[i++]=a[one++];
while(two<=right)
temp[i++]=a[two++];
i=0;
for(j=left;j<=right;j++)//将临时数组的数移入原数组
a[j]=temp[i++];
}
void MergeSort(int a[],int left,int right)//归并排序
{
if(left<right-1)//如果该组数字个数大于2
{
int mid=(left+right)/2;
MergeSort(a,left,mid);
MergeSort(a,mid+1,right);//分割
Merge(a,left,right,mid);//合并
}
else if(left==right-1)//如果该组数字个数等于2
{
if(a[left]>a[right])//如果前一个数字比后一个数字大，交换
{
int z=a[left];
a[left]=a[right];
a[right]=z;
}
}
//如果该组数字只剩一个，不用处理
}
int main()
{
int n;//序列长度/数的个数
int i;//循环用
while(~scanf("%d",&n))
{
if(n==0)
break;//输入0退出
int a[n];
for(i=0;i<n;i++)
scanf("%d",&a[i]);//输入序列
MergeSort(a,0,n-1);//归并排序
for(i=0;i<n;i++)//输出排序后序列
printf("%d ",a[i]);
printf("\n");
}
return 0;
}
|
//经过大佬的指点我做了一点修改
分组的那一块，可以分两种情况：只剩一个数和大于一个数
在合并的时候排序，这样就少了一种情况，代码也短一点
修改后：
1
2
3
4
5
6
7
8
9
10
11
|
void MergeSort(int a[],int left,int right)//归并排序
{
if(left<right)//如果该组数字个数大于1
{
int mid=(left+right)/2;
MergeSort(a,left,mid);
MergeSort(a,mid+1,right);//分割
Merge(a,left,right,mid);//合并
}
//如果该组数字只剩一个，不用处理
}
|