欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

归并排序(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;
}