蓝桥杯算法基础（14）：十大排序算法（归并排序）c语言版

归并排序

基于分而治之的思想，拿两个已经有序的序列重新组合成一个新的有序序列.

这是一个简单的合并函数，需要两个序列都有序

//默认a和b数组都是有序的
//temp为一个数组的首地址
void mergeSort(int a[],int,alen,int b[],int blen,int* temp){
    int i=0;
    int j=0;
    int k=0;
    while(i<alenj<blen){
        if(a[i]<b[j])//比大小，谁小先放谁在前
        {temp[k]=a[i];
        k++;
        i++;}
        else{
        temp[k]=b[j];
        k++;
        j++;}
      }
        while(i<alen){
        temp[k]=a[i];
        k++;
        //若是一方走完，还有一方剩下了，并且有序，那就意味着剩下的有序序列都比已经合并的最大的大，依次将剩余的数放到其中就行
        i++;}
        while(j<blen){
        temp[k]=b[j];
        k++;
        j++;}


}

简洁一下代码

void mergeSort(int a[],int,alen,int b[],int blen,int* temp){
    int i=0;
    int j=0;
    int k=0;
    while(i<alenj<blen)
        temp[k++]=a[i]<b[j]?a[i++]:b[j++];
        while(i<alen)
        temp[k++]=a[i++];
        while(j<blen)
        temp[k++]=b[j++];

}

最终版

//合并函数
//merge用于合并
void merge(int arr[],int low.int mid,int height,int* temp){
    //low~mid，mid+1~height分别为合并的两组
    int i=low;
    int j=mid+1;
    int k=low;
    while(i<=mid&&j<=height)
    temp[k++]=arr[i]<arr[j]?arr[i++]:arr[j++];
    while(i<=mid)
    temp[k++]=arr[i++];
    
    while(j<=height)
    temp[k++]=arr[j++];
    
    for(i=low;i<=height;i++)
    arr[i]=temp[i];
}


//归并法，用的是分治思想，先分后治
//merge_sort用于分割
void merge_sort(int arr[],int low,int height,int *temp){
        //取中间位置，设为mid
        //low~mid为一组，mid+1~height为一组
        //依次以每组边界带入递归，继续分割，
        //直到每组只剩一个数，然后递归开始返回，
        //从底层开始，最终到两个有序的序列，
        //再将两个有序的序列合并，即得到最终排好序的序列
        if(low>=height)
        return;
        int mid=low+(height-low)>>1;
        merge_sort(arr,low,mid,temp);
        merge_sort(arr,mid+1,height,temp);
        merge(arr,low,mid,height,temp);
        
}



//mergeSort会和merge_sort和merge,并开辟temp空间
void mergeSort(int arr[],int length){
    int *temp=(int *)malloc(sizeof(int)*length);
    //向内存开辟一个length长度，sizeof(int)*length大小的空间
    assert(temp);//断言assert，是一个调试程序时经常使用得宏，在程序运行时，计算括号内的表达式，如果为false(0),程序将报告错误，并终止执行，若不为零，继续执行后面的语句。
//主要用于判断，是否出现了非法数据
    merge_sort(arr,0.length-1,temp);
    free(temp);//free与malloc搭配使用，一个用于开辟空间，一个用于释放空间
}