我们应该对这两个列表进行排序然后进行组合，或以其他方式进行组合？

如果我有两个数字列表，为了能够得到一个单独的排序列表，我应该先对各个列表进行排序，然后进行合并排序，或者我应该将这两个列表合并成一个列表，然后应用一个有效的排序算法？我们应该对这两个列表进行排序然后进行组合，或以其他方式进行组合？

2012-08-04 London guy

为什么这个标签机器学习？ – irrelephant 2012-08-04 06:53:21

拆分成两个列表是最有效的排序算法的工作原理;-) – phs 2012-08-04 07:00:20

你可以用任何一种方式来表达观点;这取决于很多因素：

的列表A和B的选项有：

排序（A CONCAT B）
合并（排序（A），排序（B））

如果A和B的大小都接近排序并且类似，那么可以在两者上完成对几乎排序的列表（如插入排序）快速运行的内容。然后你做合并，这需要线性时间，使选项（2）接近线性。但是在这种情况下，如果每个列表中的值的范围相似，则选项（1）根本不会很好，假设您的值不适用于基数或计数，则可能为O（n log n）分类。也就是说，对于许多排序算法，由于数据移动距离较远，因此较长的列表会受到伤害。

现在我们可以想出选项（1）更好的情况。如果您发现该选项

但（2）始终在您的情况更好，但这并不意味着你应该申请一个递归拆分和合并的方式天真，由于开销这样做。

但是，与约“的排序方式更好”的所有问题，你真的要看看：

值列表的大小
范围（最小值，最大值）名单内（因为O（n）的各种可在某些情况下使用）
无论他们是近排序，几乎反向排序，完全随机的或任何
Wheter外部存储器被允许，禁止等
W¯¯无论你是在内存中排序还是整理文件
列表大小是否相同，或者比另一个大得多。

总之，“它取决于”，但如果列表已经拆分并且排序算法对列表长度敏感，那么您可以从选项（2）中获得一些好处。

来源

2012-08-04 07:04:51

我能想到在哪里（1）更好的唯一情况是几乎所有A元素都比B几乎所有元素都少，并且您使用了插入排序等算法，对近乎排序的输入做得很好。但是在这种情况下，InsertionSortTime（A concat B）将花费与InsertionSortTime（A）+ InsertionSortTime（B）相同的时间，所以改进只会是一个常数因素：合并2个列表和连接2个列表之间的区别O（n）操作，但合并也需要O（n）比较）。 – 2012-08-05 01:42:16

+1我也认为（2）“几乎总是”更好。合并对元素排序不敏感，所以当排序不像计数和基数那样O（n）时，一般来说，小列表的排序首先应该有帮助。 – 2012-08-05 02:59:37

如果他们还没有排序，我只是将他们合并，并做一个单一的排序。如果单独对它们进行排序然后进行合并排序更有效，那么将以这种方式构建最高效的排序算法：将您的列表任意分成两部分，分别排序并合并。但事实并非如此，因为......

来源

2012-08-04 06:49:51 seancarmody

最有效的排序算法（mergesort，quicksort）* *是以这种方式构建的。例外是堆排序。你在想什么算法？插入排序？对于近似排序的数据，这可能很快，但其最坏情况效率很差（O（n^2））。 – 2012-08-05 01:33:59

我们应该对这两个列表进行排序然后进行组合，或以其他方式进行组合？

回答

相关问题