n****n
发帖数: 101 | 1 请问，有若干个（比如3个）已经按升序排序好了的数组（数组长度可以一样，但也可
能不一样），那么现如何用最简洁、快速方法，将这3个数组合并到一起，仍然按升序？
注意，数组之间可能有想等的数据。
以前学过一个合并排序，但忘记如何操作了。 |
s***e
发帖数: 793 | 2 u can use heap if you have a mediate number of array. for 3, just write a
merge is ok.
序？
【在 n****n 的大作中提到】
: 请问，有若干个（比如3个）已经按升序排序好了的数组（数组长度可以一样，但也可
: 能不一样），那么现如何用最简洁、快速方法，将这3个数组合并到一起，仍然按升序？
: 注意，数组之间可能有想等的数据。
: 以前学过一个合并排序，但忘记如何操作了。
|
n****n
发帖数: 101 | 3 每个数组都有上千数据，我是用heap进行归并，但是，考虑到各个数组都已经是升序排
好了的，那么能否利用这个特点，进一步减小归并的时间、提高效率呢？ |
s***e
发帖数: 793 | 4 可以呀,
assume u have m sorted arrays with n total elements.
1: make a heap of size(m), and first put all the first of the m array in it.
2: then remove the smallest from the heap,and u need to know where the
smallest come from. so the heap element need to be a pair of value and array
index. Then add the next element in the sorted array of the removed element
if there is one.
doing step 2 until the heap is empty.
the key is that for sorted arrays, u only need to compare the smallest
element of all
【在 n****n 的大作中提到】
: 每个数组都有上千数据，我是用heap进行归并，但是，考虑到各个数组都已经是升序排
: 好了的，那么能否利用这个特点，进一步减小归并的时间、提高效率呢？
|
