归并排序(C)
程序员文章站
2022-05-31 08:12:20
...
归并排序也是典型的分治算法
#include"../init.h"
void Merge(RedType *old_node, RedType *new_node, int start, int mid, int end){
int i,j,k;
for(k=i=start,j=mid+1; i<=mid&&j<=end; k++){
if(old_node[i].key > old_node[j].key){
new_node[k] = old_node[j++];
}else{
new_node[k] = old_node[i++];
}
}
while(i <= mid){
new_node[k++] = old_node[i++];
}
while(j <= end){
new_node[k++] = old_node[j++];
}
}
void MSort(RedType *old_node, RedType *new_node, int start, int end){
if(start == end){
new_node[start] = old_node[start];
}else{
RedType S[MAXSIZE];
int mid = (start + end) / 2;
MSort(old_node,S,start,mid);
MSort(old_node,S,mid+1,end);
Merge(S,new_node,start,mid,end);
}
}
void MergeSort(Sqlist *p){
MSort((*p).r, (*p).r, 0,MAXSIZE-1);
}
int main(){
Sqlist L;
init(L.r);
MergeSort(&L);
show(L.r);
return 0;
}