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 } |
|
|
|
|
|
|
|
|
|
Text-to-speech function is limited to 200 characters
留言列表
程式學習 (3)