#include<stdio.h>
void merge_sort(int *A,int p,int r);
void merge(int *A,int p,int q,int r);
int main(){
int array[5];
int num;
printf("请输入数组长度:\n");
scanf("%d",&num);
printf("请输入元素:\n");
for(int i=0;i<num;i++)
scanf("%d",&array[i]);
merge_sort(array,0,num-1);
for(int i=0;i<num;i++)
printf("%d",array[i]);
return 0;
}
void merge_sort(int *A,int p,int r){
if(p<r){
int q=(p+r)/2;
merge_sort(A,p,q);
merge_sort(A,q+1,r);
merge(A,p,q,r);
}
}
void merge(int *A,int p,int q,int r){
int n1=q-p+1;
int n2=r-q;
int L[n1-1],R[n2-1];
for(int i=0;i<n1-1;i++)
L[i]=A[p+i];
for(int j=0;j<n2-1;j++)
R[j]=A[q-1+j];
int key=0;
L[n1]=key;
R[n2]=key;
int i=0,j=0;
for(int k=0;k<r-p;k++){
if(L[i]<=R[j]){
A[k]=L[i];
i++;
}
else{
A[k]=R[j];
j++;
}
}
}
归并排序这段代码有错吗?
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
2条回答 默认 最新
- devmiao 2015-07-28 15:32关注
归并排序,它采取分而治之的策略,将两个已经排序的序列合并成一个序列的操作。
时间复杂度是Θ(nlgn),优于插入排序算法。算法描述
1) 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
2) 设定两个指针,最初位置分别为两个已经排序序列的起始位置
3) 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
4) 重复步骤3直到某一指针达到序列尾
5) 将另一序列剩下的所有元素直接复制到合并序列尾
特点:归并排序是稳定的排序.即相等的元素的顺序不会改变, 速度仅次于快速排序,但较稳定。解决 无用评论 打赏 举报
悬赏问题
- ¥15 shape_predictor_68_face_landmarks.dat
- ¥15 slam rangenet++配置
- ¥15 有没有研究水声通信方面的帮我改俩matlab代码
- ¥15 对于相关问题的求解与代码
- ¥15 ubuntu子系统密码忘记
- ¥15 信号傅里叶变换在matlab上遇到的小问题请求帮助
- ¥15 保护模式-系统加载-段寄存器
- ¥15 电脑桌面设定一个区域禁止鼠标操作
- ¥15 求NPF226060磁芯的详细资料
- ¥15 使用R语言marginaleffects包进行边际效应图绘制