归并排序的实现 C语言版

 

 

   代码如下（我的C语言比较丑陋，将就着看吧）。

  

   其实感觉挺惊讶的是，递归能让算法如此简洁。

 

   归并的思路也比较简单，就是不断merge有序的数组。当然了，数据的有序可不是天生就有的，这儿找到有序数组的法子就是不断地二分数组，直至有序，何时会达到这个状态呢？比较傻的一个答案：等分到数组只一个元素时，就OK了（汗...）,不过这只是初始阶段，之后的各个分支汇合时，有序的可就是一条条的数组了。

 

#include <stdio.h>
#include "tool.c"

int main(){
      void mergeSort(int array[],int left,int right);
    
      int array[11]={1,2,3,6,8,9,5,4,3,2,54};
      printf("Befor mergeSort:\n");
      printArray(array,11);
      
      mergeSort(array,0,10);    
      printf("After mergeSort:\n");
      printArray(array,11);
      
      getchar();
      return 0;
      /*Result:
      Befor mergeSort:
      1 2 3 6 8 9 5 4 3 2 54
      After mergeSort:
      1 2 2 3 3 4 5 6 8 9 54
      */
}

/*
  Recursively call the mergeSort method,and merge the sorted array.
*/
void mergeSort(int array[],int left,int right){
    void merge(int array[],int left,int right);
     
    if(right>left){
        mergeSort(array,left,(left+right)/2);
        mergeSort(array,(left+right)/2+1,right);
        merge(array,left,right);
    }
}

/*
  here,is the key point.
  merge the sorted array.
*/
void merge(int array[],int left,int right){  
    int rStartPoint=(right+left)/2+1;

    //Length of the left and right arrays. 
    int leftLen=rStartPoint-left;
    int rightLen=right-rStartPoint+1;
    //copy the data into leftArray and rightArray,quite stupid here.
    //and here is the shortage of mergeSort,it needs additional memory space.
    int leftArr[leftLen],rightArr[rightLen];
    int i,j;
    for(i=0;i<=leftLen-1;i++){
        leftArr[i]=array[left+i];
    }
    for(j=0;j<=rightLen-1;j++){
        rightArr[j]=array[rStartPoint+j];
    }
    
    //insert data into array from two arranged ones.
    i=0,j=0;
    int k=left;
    while(i<=leftLen-1&&j<=rightLen-1){
        if(leftArr[i]<rightArr[j]){
            array[k++]=leftArr[i++];
        }else{
            array[k++]=rightArr[j++];
        }
    }
    while(i<=leftLen-1){
        array[k++]=leftArr[i++];
    }
    while(j<=rightLen-1)
            array[k++]=rightArr[j++];
}

 

 

  另外，我之前一直觉得不断地Merge两个数组，是属于效率比较低的做法，不明白怎么这样了居然归并还能是高效排序，后来才注意到一点，这儿不断的连接的数组可都是有序的，有序数组的合并复杂度可以达到O（N）,相当理想了。

   

   再另外，传说单链表的排序可以用归并？不解，待解(已解,参看这里)。