merge sort演算法使用Divide & conquer概念,

是將一個數列用二分法不斷拆分成更小的子數列直到無法在拆分,

接著將最小的子序列排序好後merge回高一層的子數列排列直到全部排序完成.

此排序演算法可以達到O(nlogn)的時間複雜度以及O(n)的複雜度.

 

概念讓就像玩撲克牌時拿到了一手牌,

先把全部打散之後先隨意拿兩張兩張排序,

再把一對一對排序好的牌合成四張四張排序好的牌,

重複此動作直到所有手牌排序完成.

 

以下是使用遞回的實現

 23 int merge_sort(int *arr_src, int *arr_dst, int start, int end)
 24 {   
 25     int mid;
 26     if (end <= start)
 27         return 0;
 28     mid = (end+start)/2;
 29     merge_sort(arr_src, arr_dst, start, mid);
 30     merge_sort(arr_src, arr_dst, mid+1, end);
 31     
 32     int a_id = start;
 33     int b_id = mid+1;
 34     int tar = start;
 35     // ascending order
 36     while(a_id <= mid && b_id <= end)
 37     {   
 38         arr_dst[tar++] = arr_src[a_id] < arr_src[b_id] ? arr_src[a_id++] : arr_src[b_id++];
 39     }
 40     while(a_id <= mid)
 41     {   
 42         arr_dst[tar++] = arr_src[a_id++];
 43     }
 44     while(b_id <= end)
 45     {   
 46         arr_dst[tar++] = arr_src[b_id++];
 47     }
 48     for (tar=start;tar<=end;tar++)
 49         arr_src[tar] = arr_dst[tar];
 50     return 0;
 51 }

 

 

arrow
arrow
    文章標籤
    algorithm computers sort 排序演算法 merge sort
    全站熱搜

    Mk 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄