问题
二分归并排序:对个不同的数构成的数组
进行排序,其中
解析
归并
将任意的两个升序序列和
合并为一个升序序列
主要步骤
比较序列中的首元素
和
序列中的首元素
若则将
加到
序列末尾,否则将
加到
序列末尾
重复以上操作直到序列或
序列为空
将非空序列直接加到序列末尾
正确性证明
对于升序序列和
,将两个序列的首元素分别记为
和
因为和
是升序序列,所以有
若则
,此时
就是两个序列中最小的,将
放入
序列末尾中即可
此时序列中最小的数变为了
同理,当只需将
放入
末尾即可
因为每次放入序列末尾的元素总小于
中其他元素,也就是
也就说
也是一个升序序列
复杂度
每个元素会被放入序列一次,若
序列长度分别为
,则总操作次数为
,归并操作的复杂度为
归并排序
我们已经得到了一个在线性时间复杂度内合并两个有序序列的算法,只要事先得到两个有序序列,就可以合并得到一个完整的有序序列了
对于这个序列,我们可以从序列中间分开,先排序好前一半,再排序好后一半,最后归并整个序列
对于前一半序列,同样可以用归并排序的方法,分别排序好前后,在归并,后一半同理
显然只有一个元素的序列本身就是有序的,所以如果序列中只有一个元素,就可以直接结束了
设计
void merge(int A[], int T[], int S[], int len1, int len2)//将长度为len1的序列S和长度为len2的序列T进行归并,结果储存在A中 { int p = 0; int i = 0, j = 0; while (i < len1 && j < len2) { if(T[i]<S[j]) A[p++] = T[i++]; else A[p++] = S[j++]; } while (i < len1) A[p++] = T[i++]; while (j < len2) A[p++] = S[j++]; } void mergeSort(int A[], int T[], int len)//递归排序 { if (len == 1) return; int mid = len / 2; mergeSort(A, T, mid);//先处理前半 mergeSort(A + mid, T + mid, len - mid);//处理后半 merge(T, A, A + mid, mid, len - mid);//对序列进行归并 for (int i = 0; i < len; ++i) A[i] = T[i]; }
分析
显然对于长度为的序列,归并前后两半需要的操作次数为
对于长度为次的序列,所需的操作次数为
,对于长度为
的序列,直接结束递归,所以操作次数为
可以列出如下等式
于是我们可以得出方程组
累加所有式子
消去相同项
将用
替代,则
,总操作次数为
最终算法复杂度为