算法作业4——二分归并排序

1.问题

二分归并排序：对n个不同的数构成的数组A[1..n]进行排序，其中n=2^k

2.解析

3.设计

 1 //归并
 2 void Merge(int left, int mid, int right) {
 3     int i = left, j = mid + 1;
 4     int k = left;
 5 
 6     //在A(left,mid)和A(mid+1,right)两部分中取较小数加到B数组中，下标+1
 7     while (i <= mid && j <= right) {
 8         if (A[i] <= A[j]) B[k++] = A[i++];
 9         else B[k++] = A[j++];
10     }
11     //若A(left,mid)中还有元素剩余，则依次加到B数组中，下标+1
12     while (i <= mid) 
13         B <-  A;
14     
15     //若A(mid+1，right)中还有元素剩余，则依次加到B数组中，下标+1
16     while (j <= right) 
17         B <- A;
18     
19     //B数组整体赋值给A数组
20     for (int x = left; x <= right; x++)
21         A <- B;
22 }
23 
24 
25 //二分
26 void Binary(int left,int right) {
27     int mid = (left + right) / 2;    //mid取left、right中
28     if (left < right) {
29         Binary(left, mid);        //左半部分一直递归
30         Binary(mid + 1, right);    //右半部分一直递归
31         Merge(left,mid,right);    //归并左右部分
32     }
33 }

4.分析

T(n)=O(nlogn)

5.源码

https://github.com/2579081436/algorithm.github.io