Question

求算法设计高手帮忙解答！！（急用）

设子数组a[0:k-1]和a[k:n-1]已排好序（0≤k≤n-1）。
任务：试设计一个合并这2个子数组为排好序的数组a[0:n-1]的算法。要求算法在最坏情况下所用的计算时间为O(n)，且只用到O(1)的辅助空间，要求写出算法的思路。

Answer 1

叫做归并排序(MergeSort)可以搜一下。

排序的思路是T(n)=T(n/2)+O(n)=O(nlogn)这样一个事实。

O(n)是要解决的合并问题

为了方便我的说明，把下标变为1<=i<=m为第一个数组
1<=j<=n为第二个数组

因为两个是有序的

把a(i)和b(j)进行比较，较小的加入新的队列中（假设为a(i))然后i++

这步一直执行，直到i>m或j>n
剩下的元素一定比当前己入新队列的大，直接加入队列。

这样就完成了合并操作

自己写的没查。您要思路，我就不写代码了。