Merge Sort



//遞迴函數
// sort_s 為每次遞迴函數所知道的最前指標位址 
// sort_e 為每次遞迴函數所知道的最後指標位址 
int Sort_Merge(int sort_s,int sort_e){

    //宣告 
    int i,j,k=0,tmp_sort[ sort_e-sort_s ];

    //判定是否需要繼續分為二等分 
    if (sort_e-sort_s > 1){
        Sort_Merge(sort_s,(sort_s+sort_e)/2);
        Sort_Merge((sort_s+sort_e)/2,sort_e);
    }

    //設定 i 一開始為最前指標位址
    i=sort_s;

    //設定 j 一開始為最前與最後之中間指標位址
    j=(sort_s+sort_e)/2;

    //利用迴圈先將數列大小放置於暫存陣列 
    while(k < ( sort_e - sort_s) ){
     
     //判定 i 和 j 標地物是否超過分界 
     //判定皆尚未過界 
 if ( (i < (sort_s + sort_e)/2) && (j < sort_e) ){
   
     //判定 i 和 j 指標之數字何者較小
     //判定 i 較小 
     if( *(data+i) < *(data+j) ){
    
         //放置暫存陣列 
  tmp_sort[k] = *(data+i);
    
  // i 指標移動 
  i++;
     }

     //判定 j 較小或 j 和 i 相同大小 
     else{
    
  //放置暫存陣列 
  tmp_sort[k] = *(data+j);
    
  // j 指標移動 
  j++;
            }
 }

 //判定僅 i 過界 
 else if ( (i >= (sort_s+sort_e)/2) && (j < sort_e) ){
   
     //放置暫存陣列 
     tmp_sort[k] = *(data+j);

     // j 指標移動
     j++;

 }

 //判定僅 j 過界 
 else if ( (i < (sort_s+sort_e)/2) && (j >= sort_e) ){
   
     //放置暫存陣列 
     tmp_sort[k] = *(data+i);
   
     // i 指標移動
     i++;
 }

 //增加陣列位址 
 k++;
    }
 
    //將暫存陣列複寫至原指標 
    for(k=0;k < (sort_e - sort_s );k++){
 *(data+(sort_s+k))=tmp_sort[k];
    }
} 

Merge Sort 最大的特色在於,不管處理 Increase 、 Decrease 和 Random 排列的狀況底下,差異性不大且處理速度快,但是與 Insertion Sort(Code-2) 比較 Increase 的狀況下,還是會相較於 Insertion Sort 慢。

0 件のコメント:

コメントを投稿