#include<stdio.h>
void mergesort(int *num,int start,int end)
// 这个函数用来将两个排好序的数组进行合并
void merge(int *num,int start,int middle,int end)
int main()
{
// 测试数组
int num[10]= {12,54,23,67,86,45,97,32,14,65}
int i
// 排序之前
printf("Before sorting:\n")
for (i=0i<10i++)
{
printf("%3d",num[i])
}
printf("\n")
// 进行合并排序
mergesort(num,0,9)
printf("After sorting:\n")
// 排序之后
for (i=0i<10i++)
{
printf("%3d",num[i])
}
printf("\n")
return 0
}
//这个函数用来将问题细分
void mergesort(int *num,int start,int end)
{
int middle
if(start<end)
{
middle=(start+end)/2
// 归并的基本思想
// 排左边
mergesort(num,start,middle)
// 排右边
mergesort(num,middle+1,end)
// 合并
merge(num,start,middle,end)
}
}
//这个函数用于将两个已排好序的子序列合并
void merge(int *num,int start,int middle,int end)
{
int n1=middle-start+1
int n2=end-middle
// 动态分配内存，声明两个数组容纳左右两边的数组
int *L=new int[n1+1]
int *R=new int[n2+1]
int i,j=0,k
//将新建的两个数组赋值
for (i=0i<n1i++)
{
*(L+i)=*(num+start+i)
}
// 哨兵元素
*(L+n1)=1000000
for (i=0i<n2i++)
{
*(R+i)=*(num+middle+i+1)
}
*(R+n2)=1000000
i=0
// 进行合并
for (k=startk<=endk++)
{
if(L[i]<=R[j])
{
num[k]=L[i]
i++
}
else
{
num[k]=R[j]
j++
}
}
delete [] L
delete [] R
}
#include <stdio.h>void merge(int r[], int s[], int x1, int x2, int x3) /*实现一次归并排序函数*/
{
int i, j, k
i = x1 /*第一部分的开始位置*/
j = x2 + 1 /*第二部分的开始位置*/
k = x1
while ((i <= x2) &&(j <= x3))
/*当i和j都在两个要合并的部分中*/
if (r[i] <= r[j])
/*筛选两部分中较小的元素放到数组s中*/
{
s[k] = r[i]
i++
k++
}
else
{
s[k] = r[j]
j++
k++
}
while (i <= x2)
/*将x1~x2范围内的未比较的数顺次加到数组r中*/
s[k++] = r[i++]
while (j <= x3)
/*将x2+1~x3范围内的未比较的数顺次加到数组r中*/
s[k++] = r[j++]
}
void merge_sort(int r[], int s[], int m, int n)
{
int p
int t[20]
if (m == n)
s[m] = r[m]
else
{
p = (m + n) / 2
merge_sort(r, t, m, p)
/*递归调用merge_sort函数将r[m]~r[p]归并成有序的t[m]~t[p]*/
merge_sort(r, t, p + 1, n) /*递归调用merge_sort函数将r[p
+1]~r[n]归并成有序的t[p+1]~t[n]*/
merge(t, s, m, p, n) /*调用函数将前两部分归并到s[m]~s[n]*/
}
}
main()
{
int a[11]
int i
printf("please input 10 numbers:\n")
for (i = 1i <= 10i++)
scanf("%d", &a[i])
/*从键盘中输入10个数*/
merge_sort(a, a, 1, 10) /*调用merge_sort函数进行归并排序*/
printf("the sorted numbers:\n")
for (i = 1i <= 10i++)
printf("%5d", a[i])
/*将排序后的结构输出*/
}
