這個「增量排序」

中採用相同的合併功能如合併排序，但輸入拆分不同，所以列表被以這種方式合併^

在最壞的情況下時間複雜度場景，該算法的比較數是多少？我知道合併排序是（n log n - n + 1），我假設這種排序比較慢

2013-10-15 Foxic

作爲一個提示：你有沒有看過這個算法嗎？它通過從n個已排序元素的列表開始，然後將第n個元素添加到最後並將其交換到適當的位置。

一旦你找出了算法，你應該能夠很容易地得到最好的，最壞的和平均情況下的運行時間。

希望這會有所幫助！

2013-10-15 21:47:32 templatetypedef

我想不出來 – Foxic

@ Foxic-想想插入排序。 – templatetypedef

非常感謝，插入排序使得它更清晰 – Foxic

這種類型是O（n^2）。對於添加的每個項目，您會比較現有列表中的每個項目。

所以在這裏你可以做出1 + 2 + 3 + 4 + 5 + 6 + 7 =（n^2 + n）/ 2的比較。

這是假設您正在使用標準合併。

你也可以這樣做，在這種情況下，它只是將東西插入排序列表中。那也是O（n^2）。您將進行log（n）比較以找到要插入項目的位置，但必須將項目向下移動以騰出空間。因此插入每個項目是n + log（n），進行排序O（n^2 + n log n）。

2013-10-15 21:49:49

它不是將它與第（n/2）個元素（或n/2 - 1，如果列表是偶數）進行比較並每次將列表減半？將它與列表中的每個項目進行比較將會非常低效 – Foxic

@Foxic：您說它使用與合併排序相同的合併函數。如果是這樣，並且您按照升序（最差的情況）添加東西，則添加的每個新項目將與現有列表中的每個項目進行比較。 –

回答