1 題目
功能：歸并排序
描述：利用歸并排序進(jìn)行將數(shù)組序列從小到大排序
2 思路
歸并排序兩個(gè)或多個(gè)有序記錄序列合并成一個(gè)有序序列一次對(duì)兩個(gè)有序記錄序的歸并稱為二路歸并排序，也有三路歸并排序及多路歸并排序下面代碼給出的是二路歸并排序，基本方法 (1)將n個(gè)記錄看成是n介長(zhǎng)度為1的有序子表 (2)將兩兩相鄰的有序壬莓4行歸并 (3)垂復(fù)軌行步驟(2)直至歸并成一個(gè)長(zhǎng)度為 L 的有序表
3 代碼
#include <stdio.h>
#include <stdlib.h>
/**
功能：歸并排序
描述：利用歸并排序進(jìn)行將數(shù)組序列從小到大排序
**/
voidmerge(intr[],ints[],intx1,intx2,intx3) {// 實(shí)現(xiàn)一次歸并排序函數(shù)
inti,j,k;
i=x1;? ? ? ? ? ? ? ? ? ? // 第一部分的開(kāi)始位置
j=x2+1;? ? ? ? ? ? ? ? ? ? // 第二部分的開(kāi)始位置
k=x1;
while((i<=x2)&&(j<=x3))? ? ? ? // 當(dāng)i和j都在兩個(gè)要合并的部分中
if(r[i]<=r[j]){? ? ? ? ? ? // 篩選兩部分中較小的元素放到數(shù)組s中
s[k]=r[i];
i++;
k++;
}else{
s[k]=r[j];
j++;
k++;
?? }
while(i<=x2)? ? ? ? ? ? ? // 將x1~x2范圍內(nèi)的未比較的數(shù)順次加到數(shù)組r中
s[k++]=r[i++];
while(j<=x3)? ? ? ? ? ? ? // 將x2+1~x3范圍內(nèi)的未比較的數(shù)順次加到數(shù)組r中
s[k++]=r[j++];
}
voidmerge_sort(intr[],ints[],intm,intn) {
intp;
intt[20];
if(m==n)
s[m]=r[m];
else
?? {
p=(m+n)/2;
merge_sort(r,t,m,p);
? ? ? ? ? ? ? ? ? // 遞歸調(diào)用merge_sort函數(shù)將r[m]~r[p]歸并成有序的t[m]~t[p]
merge_sort(r,t,p+1,n);? ? ? // 遞歸調(diào)用merge_sort函數(shù)將r[n+1]~r[n]歸并成有序的t[p+1]~t[n]*/
merge(t,s,m,p,n);? ? ? ? ? // 調(diào)用函數(shù)將前兩部分歸并到s[m]~s[n]
?? }
}
intmain(intargc,charconst*argv[]) {
inta[11];
inti;
printf("請(qǐng)輸入10個(gè)數(shù):\n");
for(i=1;i<=10;i++)
scanf("%d",&a[i]);
merge_sort(a,a,1,10);? ? ? ? ? // 調(diào)用merge_sort函數(shù)進(jìn)行歸并排序
printf("排序后的順序是:\n");
for(i=1;i<=10;i++)
printf("%5d",a[i]);
? printf("\n");
}
示例結(jié)果：
$ gccex063.c-odemo
$ ./demo
請(qǐng)輸入10個(gè)數(shù):
34
12
64
23
98
45
18
52
1
7
排序后的順序是:
171218233445526498
