0

假设我得到这些整数 6,1,4,2,1,5,9,6,3,4 并且运行的大小是 2 所以我们从每次运行的插入排序开始，我得到这些子数组：

1-6、2-4、1-5、6-9、3-4

我的问题是如何合并它们以获得排序数组？我的意思是我是否合并每两个数组，然后合并其余的等等？

4

1 回答 1

0

创建初始运行后，然后合并运行。Timsort 使用堆栈来跟踪运行边界，并使用堆栈上的前 3 个条目来决定要合并哪些运行以“平衡”合并，同时保持“稳定性”。可以使用队列（FIFO）而不是堆栈（LIFO）（尽管我不确定这在技术上是否仍然是 timsort）。对于 10 个元素，运行大小为 3 将减少一次合并通道。Timsort 通常使用更大的最小运行大小，32 到 64（含），如果自然运行小于计算的理想最小运行大小，则使用插入排序强制最小运行大小。维基文章链接：

https://en.wikipedia.org/wiki/Timsort

于 2018-05-21T13:19:37.587 回答