您当前的位置： 首页 > 慢生活 > 程序人生 网站首页程序人生

c语言实现歸并排序遞歸法

发布时间：2021-04-27 20:59:33编辑：雪饮阅读（）

 上次了解了归并排序的迭代法，那么接下来再来看看归并排序的递归法。

递归法的思路和迭代法相反。递归法首先会把arr拆分成S1,S2两段，然后再把S1和S2继续再拆一次。一直拆成零散的几段，然后进行比较，然后排序。
原理可以参考这个图

那么接下来就看下具体的实现了
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void printfArray(int arr[],int len){
    for(int x=0;x<len;x++){
        if(x==len-1){
            printf("%d",arr[x]);
        }
        else{
            printf("%d,",arr[x]);
        }
    }
}
void merge_sort_recursive(int arr[], int reg[], int start, int end) {
    static char str[]="";
       strcat(str,"   ");
       if (start >= end){
        return;
    }
      
    //len >> 1:二進制右移1位相當于除以2
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
 
       merge_sort_recursive(arr, reg, start1, end1);
 
    merge_sort_recursive(arr, reg, start2, end2);
 
    int k = start;
    while (start1 <= end1 && start2 <= end2){
        if(arr[start1] < arr[start2]){
            reg[k++]=arr[start1++];
        }
        else{
            reg[k++]=arr[start2++];
        }
    }
    //左組剩餘的沒有數可以與其參加比較的，則移動到左組的末尾   
    while (start1 <= end1){
        reg[k++] = arr[start1++];
    }
    //右組剩餘的沒有數可以與其參加比較的，則移動到右組的末尾    
    while (start2 <= end2){
        reg[k++] = arr[start2++];
    }
    //更新arr數組為reg中已排序數組
       printf("\n數組arr與數組reg交換前:\n");   
       printf("數組arr:");
       for (k = start; k <= end; k++){
        if(k==end){
                     printf("%d",arr[k]);
              }
              else{
                     printf("%d,",arr[k]);
              }
    }
       printf("\n");
       printf("數組reg:");
       for (k = start; k <= end; k++){
        if(k==end){
                     printf("%d",reg[k]);
              }
              else{
                     printf("%d,",reg[k]);
              }
    }
       printf("\n");
       /*
       同步reg的數據到arr中
       這步看似多餘，實際上這裏reg相當於一個中間變量，類似冒泡排序時候每次用的那個temp
       不過這裏因爲每次要交換的是一個左組和一個右組，所以不能單純用一個單值的中間變量，而應該用數組形式的中間變量用來存儲已經交換的
       如果不用這個中間變量，則内部左組和右組在進行内部比較的時候就有可能出現每次比較的兩個數都有可能是已經交換更新了的，所以就沒有意義了
       */
    for (k = start; k <= end; k++){
        arr[k] = reg[k];
    }
      
       printf("\n數組arr與數組reg交換后:\n");   
       printf("數組arr:");
       for (k = start; k <= end; k++){
        if(k==end){
                     printf("%d",arr[k]);
              }
              else{
                     printf("%d,",arr[k]);
              }
    }
       printf("\n");
       printf("數組reg:");
       for (k = start; k <= end; k++){
        if(k==end){
                     printf("%d",reg[k]);
              }
              else{
                     printf("%d,",reg[k]);
              }
    }
       printf("\n");
       
}
void merge_sort(int arr[], const int len) {
    int reg[len];
    merge_sort_recursive(arr, reg, 0, len - 1);
 
    //輸出
    for(int s=0;s<len;s++){
        printf("%d\n",arr[s]);
    }
}
void main(){
    int arr[]={8,4,5,7,1,3,6,2};
    int len=8;
    merge_sort(arr,len);
}
其实只要对之前迭代法弄懂了，这个递归法就相对来说比较简单了。