归并排序的递归实现与非递归实现

归并排序

• 归并排序图

归并排序图.png

• 递归实现简介

  • 代码示例

     mergesort(left,right,**a){
         if(left<right){
             int mid = 1/2(left+right);
             mergesort(left,mid,**a);
             mergesort(mid+1,right,**a);
             merge(a,b,left,right);
             copy(a,b,left,right);
         }
     }
    

  • 代码解释

    • mergesort方法是向下分裂的方法
    • merge是一个排序方法,对a中的元素用两个指针移动进行比较存入b中
    • copy是一个赋值方法,把b中排序好的值给a
• 非递归实现简介

  • 代码示例

     void merge_sort(int *list, int length){
         int i, left_min, left_max, right_min, right_max, next;
     
         int *tmp = (int*)malloc(sizeof(int) * length);
     
         for(i=1;i<length;i*=2){
             right_min = left_max = left_min+i;
             right_max = left_max+i;
         
             if(right_max>length){
                 right_max = length;
             }
         
             next = 0;
             while(left_min<left_max&&right_min<right_max){
                 tmp[next++] = list[left_min]>list[right_min]?list[right_min++]:list[left_min++];
             }
             while(left_min < left_max){
                 list[--right_min] = list[--left_max];
             }
             while(next>0){
                 list[--right_min] = tmp[--next];
             }
         }
     }
    

  • 算法实现解释

    • 代码实现步骤(按照i=1,2,4依次进行,都是相同的,所以只列出i=1的情况)

      • i=1:

         left[10],right[4]  
         left_min=0,left_max=1,right_min=1,right_max=2
         right_max<length
         双指针移动逐步比较直到有一边到达尾部
         点睛之笔是最后的两个while,
         第一个while是判断当left未移动到尾部时,将当前指针指向的值及之后的移动到队尾
         如果是right未移动到尾部,直接将tmp中的值按序赋值到list中即可