合并2个排序的列表 [英] Merge 2 sorted lists

问题描述

有人要求我为以下问题提供尽可能多的解决方案:

I've been asked to come up with as many solutions as possible to the following problem:

编写一个包含两个数字列表的函数(均假定为 并以升序排列)并将它们合并到一个列表中(也在 升序).

Write a function which takes two lists of numbers (both assumed to be in ascending order) and merges them into a single list (also in ascending order).

我的第一个解决方案是将append list1移至list2上，然后重新执行sort.

My first solutions was to append list1 onto list2 and then re-sort.

然后我找到了一个内置的merge.

Then I found a built-in merge.

然后，我决定自己实际实现一个解决方案，然后我想到了一个尾部递归函数，该函数目前仅适用于列表的子集.

Then I decided to actually implement a solution myself, and I came up with a tail recursive function that, at the moment, only works for a subset of lists.

问题本身似乎似乎终于使我有理由阅读Knuth了，但是可惜Unis和图书馆由于下雪而关闭.

The problem itself seems like maybe I finally have a reason to read Knuth, but alas Uni and the Library are closed due to snow.

那么，我求助您，有什么有趣的，有效的或反模式的方法可以解决这个问题?

So I turn to you SO, what are some interesting, or efficient, or anti-pattern approaches to this problem?

P.S我不是在寻找实现方式，除非那是证明这个想法的最佳方法.我只是想看看人们是如何解决这类问题的.

P.S I'm not looking for implementations, unless thats the best way to demonstrate the idea. I'm just looking to see how people have approached this type of problem.

推荐答案

在算法上合并两个排序的列表是微不足道的.

Merging two sorted lists is algorithmically trivial.

从每个列表的第一个元素开始，进行比较，编写下一个元素以输出并在找到下一个元素的位置前进.继续前进，直到到达一个列表的末尾，然后将另一列表的其余部分放掉.

Start with the first element of each list, compare, write the lower one to output and advance the list where you found the lower one. Keep going until you reach the end of one list, then put out the remainder of the other list.

这只需要在每个列表上循环一次，最多可以循环一次.每个输出元素一个比较.

This requires just one loop over each list and max. one comparison per output element.

这与获取两个列表一样有效.当您有大量要合并的列表时，它会(有点)棘手.

This is as efficient as it gets for two lists. It gets (a little bit) trickier when you have a large number of lists to merge.

这篇关于合并2个排序的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！