C语言归并排序 | Eternal_zttz

C语言归并排序

归并排序:归并排序采用了分治的思想,在排好n个数之前,先将前n/2个数和后n/2的数排好,利用递归以此类推,然后将已排好序的两个n/2数组合并为一个长度为n的有序数组。

该算法需要一个作为中间传递已排好序数值的数组

归并排序时间复杂度为O(nlogn),空间复杂度为O(n)

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
#include <stdio.h>
#define N 10000
int k[N];
void merge(int a[],int left,int right){
if(left == right)//递归的终止条件,当left==right时,只有一个元素,此时已是默认排好序的了
return ;
int mid = (left+right)/2;//二分
merge(a,left,mid);//排序前半部分
merge(a,mid+1,right);//排序后半部分
int i = left,j =mid+1,p= left;//合并已经排好序的数组
while(i<=mid&&j<=right){
if(a[i]<a[j])
k[p++] = a[i++];
else
k[p++] = a[j++];
}
while(i<=mid)//如果有数组没有全部合并完,则直接放在合并数组后面
k[p++] = a[i++];
while(j<=right)
k[p++] = a[j++];
for (i = left;i<=right;i++)//将k[]返回a[]数组中
a[i] = k[i];
}
int main(){
int n;
scanf("%d",&n);
int a[n];
for (int i = 0;i<n;i++)
scanf("%d",&a[i]);
merge(a,0,n-1);
for (int i = 0;i<n;i++)
printf("%d ",a[i]);
return 0;
}

程序输入:

1
2
9
1 5 6 8 4 3 2 9 15

程序输出:

1
1 2 3 4 5 6 8 9 15


-------------The End-------------