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

c语言归并排序迭代法的实现

发布时间：2021-04-26 21:36:56编辑：雪饮阅读（）

 首先这里借用下这个博客的一张图用来说明归并排序的实现原理

https://www.cnblogs.com/chengxiao/p/6194356.html

归并排序分为迭代法和递归法，这里主要实现迭代法，迭代法，即图中从治的部分的最底层开始，即步长为1开始。
那么首先来看看一个带有超级详细注释的版本，这对于新人来说更容易上手：
#include <stdio.h>
#include <stdlib.h>
int min(int x, int y) {
    return x < y ? x : y;
}
void merge_sort(int arr[], int len) {
    int* a = arr;
    int* b = (int*) malloc(len * sizeof(int));
    int seg, start;
    printf("len=%d",len);
       /*
       seg = seg+seg:
       相當于seg=2*seg
       seg间隔成幂次增长
       例如间隔会从1到2到4这样增长
       */
    for (seg = 1; seg < len; seg = seg+seg) {
        printf("\n seg=%d",seg);
              /*
              start = start+seg + seg:
              每次劃分子序列（多個子組）的時候，每次左組的左邊界即開始位置是start，而左組的右邊界是start+seg(不考慮超過len的情況下),
              所以下一個左組的開始位置就是靠在右邊界右邊那個 一組，即再加一個seg（也不考慮leng的情況下），即就是start = start+seg + seg
              */
        for (start = 0; start < len; start = start+seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            /*
            按照算法的實現原理，下一組所有數都比必須比當前組的所有數大。
            爲了實現此目標，首先要保證下一組的第一個數比當前組最後一個數字大，所以需要這個僞中間值，也可理解為上一個組的邊界值
            一個組最小單位為2，則至少3個數進行比較才能形成一個組
            */
            printf("\n %-4s low=%d,mid=%d,high=%d","",low,mid,high);
            printf("\n %-4s low_v=%d,mid_v=%d,high_v=%d","",a[low],a[mid],a[high]);
           
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            /*
            左組左邊界的下一個數的排序
            這裏while看似不用循環是固定的，但其實循環躰裏面的start1++影響了，所以有必要循環
            結合圖中例如：48,57,13這一行，這裏循環條件是爲了防止到達邊界
            */
                    
                      printf("\n %-8s arr目前的數列情況:","");
            for(int ai=0;ai<len;ai++){
                if(ai==len-1){
                       printf("%d",arr[ai]); 
                }
                else{
                    printf("%d,",arr[ai]);
                } 
            }
            printf("\n");
                    
            printf("\n %-8s 本輪要進行排序的數字隊列(本次要排序数列a)","");
            for(int ai=0;ai<len;ai++){
                if(ai==len-1){
                       printf("%d",a[ai]); 
                }
                else{
                    printf("%d,",a[ai]);
                } 
            }
            printf("\n");
                    
                    
                     printf("\n %-8s 本輪要操作的组:","");
                     for(int z=start1;z<end1;z++){
                            printf("%d",a[z]);
                     }
                     printf(",");
                     for(int z=start2;z<end2;z++){
                            printf("%d",a[z]);
                     }
                     printf("\n");
                    
                    
            printf("\n %-8s 已存儲的b數組數字隊列(上次待排序数列):","");
            for(int bi=0;bi<len;bi++){
                if(bi==len-1){
                       printf("%d",b[bi]); 
                }
                else{
                    printf("%d,",b[bi]);
                } 
            }
                    
            printf("\n %-8s start=%d","",start);
            while (start1 < end1 && start2 < end2){
                printf("\n %-12s start1=%d,end1=%d,start2=%d,end2=%d,k=%d","",start1,end1,start2,end2,k);
                /*
                左右組開始值對比，並將結果存儲在新的數組
                start1或start2指針移動
                            实现往右移动一位的效果（虽然向右移动一个位，内部实现却是看谁大谁小，总之小的都放左边）
                */
                            int leftv=a[start1];
                            int rightv=a[start2];
                if(a[start1] < a[start2]){
                    printf("\n %-12s %d與%d比結果：%d放到b[%d]\n","",a[start1],a[start2],a[start1],k);
                                   b[k++] =a[start1++];
                }
                else{
                                   printf("\n %-12s %d與%d比結果：%d放到b[%d]\n","",a[start1],a[start2],a[start2],k);
                    b[k++] =a[start2++];
                }
 
 
                printf("\n %-12s b中的队列改变为:","",leftv,rightv);
                for(int bi=0;bi<len;bi++){
                    if(bi==len-1){
                           printf("%d",b[bi]); 
                    }
                   else{
                        printf("%d,",b[bi]);
                    } 
                }
                printf("\n");
            }
            printf("\n");
            printf("\n");
                    
            while (start1 < end1){
                printf("\n %-8s左組剩餘的%d填充到b[%d]\n","",a[start1],k);
                            b[k++] = a[start1++];
            }
            while (start2 < end2){
                            printf("\n %-8s右組剩餘的%d填充到b[%d]\n","",a[start2],k);
                b[k++] = a[start2++];
            }
        }
        printf("\n");
              /*
              遍历结束后会得到一个整理后的数组，但是存储在b的地址中。而我们需要它返回到a的地址当中
              然後b=temp，相當於b又被賦予上次的a，這裏不衝突，因爲a一直保持最新，而b每次只落後一個組
              */
        int* temp = a;
        a = b;
        b = temp;
             
              if(a!=arr){
                     printf("\n %-8s a在這裏和arr不相等了:","");
              }
              else{
                     printf("\n %-8s a在這裏和arr又相等了:","");
              }
             
               printf("\n %-8s 本輪存儲到b之後arr目前的數列情況:","");
              for(int ai=0;ai<len;ai++){
                     if(ai==len-1){
                               printf("%d",arr[ai]); 
                     }
                     else{
                            printf("%d,",arr[ai]);
                     } 
              }
              printf("\n");
             
              printf("\n %-8s 本輪存儲到b之後a目前的數列情況","");
              for(int ai=0;ai<len;ai++){
                     if(ai==len-1){
                               printf("%d",a[ai]); 
                     }
                     else{
                            printf("%d,",a[ai]);
                     } 
              }
              printf("\n");
             
              printf("\n %-8s 本輪存儲到b之後b目前的數列情況:","");
              for(int bi=0;bi<len;bi++){
                     if(bi==len-1){
                               printf("%d",b[bi]); 
                     }
                     else{
                            printf("%d,",b[bi]);
                     } 
              }
                    
              printf("\n %-8s a的地址%p,arr的地址%p\n","",a,arr);
             
    }
       printf("\n");
       printf("全结束后未最后处理的a序列:");
       for(int wc=0;wc<len;wc++){
              if(wc==len-1){
                     printf("%d",a[wc]);
              }
              else{
                     printf("%d,",a[wc]);
              }
             
       }
       printf("\n");
      
              printf("\n");
       printf("全结束后未最后处理的b序列:");
       for(int wc=0;wc<len;wc++){
              if(wc==len-1){
                     printf("%d",b[wc]);
              }
              else{
                     printf("%d,",b[wc]);
              }
             
       }
       printf("\n");
       //free只能使用在动态分配的内存上，不能用在堆栈或静态数据上。
       /*
      
       對於
       int* temp = a;
                     a = b;
                     b = temp;
 
       我總算是明白了
       其實因爲這裏在循環中不斷的交換，每次b比a慢1波。
       由於不斷的交換，那麽就是說a有時候回到了原來arr的地址，到下一輪的時候有可能又回到了b的地址
 
       所以并不一定是奇數時候才出現b拿到了arr的地址，這個取決于排序的過程所產生的交換次數。
       */
       if (a != arr) {
              printf("\n");
              printf("a不等于arr,arr序列:");
              for(int wc=0;wc<len;wc++){
                     if(wc==len-1){
                            printf("%d",arr[wc]);
                     }
                     else{
                            printf("%d,",arr[wc]);
                     }
                    
              }
              printf("\n");
              printf("\n");
              /*
              上面进行存储到每两组数据排序后的数据到b中时，使用了指针交换，有可能会导致会造成最终b拿到了arr的地址，a拿到了动态分配的地址
              这里a和arr进行条件判断，判断的是指针即地址是否相同，而不是值是否相同，所以通过这个来确保a是否还和开头一样，是与arr在一个地址上的
              下面这个for循环不僅僅是爲了同步數據，此時的b可能因爲上面的交換，導致這裏的b實際上可能是最初的arr，而b則有可能是上面的a
              */
             
              for (int i = 0; i < len; i++){
                     b[i] = a[i];
              }
             
              //上面的for循環把arr整理結束后，接下來就是將b也調整到它原本該在的地址，這裏a實際上才是原來的b的地址，這樣在下面釋放b的時候才能夠正常釋放
              b = a;
              /*
              a!=arr則表示a已經指向了動態棧，而不是原來的arr的靜態棧，所以這裏遍歷a的值挨個填充b，最後將b的地址也同步到a上，就達成了b又恢復到它原本定義的動態棧，這樣才能被free釋放
              */
       }
      
    //输出
    for(int x=0;x<len;x++){
        printf("%d\n",arr[x]);
    }
       //自己申請的要自己釋放，否则就内存释放不及时
    free(b);
}
void main(){
    int arr[]={8,4,5,7,1,3,6,2};
    int len=8;
    merge_sort(arr,len);
}
逻辑整理
​ 在本程序中用到了两个存储空间，一个是arr数组本身，用指针a指向了这个数组。另外使用stdlib头文件中的malloc函数分配一块和arr数组等大的空间，用指针b指向了这个地址。这里要注意的是，a指针和b指针指向不同的地址。
 
​ 接着通过定义seg变量来设置a中两个数据段的间隔。然后使用两个变量，这里简写为S1和S2去分别遍历这两个数据段。low,mid,high可以成一个遍历区间：
[ l o w , m i d ) ∪ [ m i d ， h i g h ) [low,mid)∪[mid，high)
[low,mid)∪[mid，high)
 
​ 左边的区间由S1去遍历，右边S2遍历。然后比较这两个位置中数的大小。使用复合公式，如果S1>S2，返回S1的值，直接写入到b的地址中去。同时本次比较有返回数的这个区间(这里为S1)的数组下标自加1，实现往右移动一位的效果。而另一边的语句则不会执行。这样反复计算最终会有一个值无数比较，通过下面两个while语句来直接填入数据段后。然后接着一直循环直到第一组遍历结束。
 
​ 第一组遍历结束后会得到一个整理后的数组，但是存储在b的地址中。而我们需要它返回到a的地址当中，就进行两个指针指向的地址进行交换。但是这样交换指针指向地址，如果在数组成员为奇数个的时候则会造成最终b拿到了arr的地址，a拿到了动态分配的地址。导致最后释放b的时候会出错。这时候最外层的if语句判断指针指向地址就起到了作用。
 
​ 第一个周期结束后紧接着开始第二个周期，seg间隔成幂次增长。间隔会从1到2到4这样增长，而每个周期中arr数组中数据段的遍历长度就是：seg/2。
 
​ 最终就能够得到一个排序后的序列。
迭代法模拟图：

 
那么你也可以选择看下原版，比较精简：
int min(int x, int y) {
    return x < y ? x : y;
}
void merge_sort(int arr[], int len) {
    int* a = arr;
    int* b = (int*) malloc(len * sizeof(int));
    int seg, start;
    for (seg = 1; seg < len; seg += seg) {
        for (start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int* temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}