排序與插入部分排序的數組排序

Question

我哈瓦陣列與所述第一，直到N個元素被分選和N + 1，直到elemnt N + M未排序（陣列包括N + M個元素的）。使用插入排序對這個數組進行排序的複雜性是什麼？我認爲它是（N + M）^ 2，是嗎？

Answer 1

如果你想使用插入排序，你將需要O（M *（M + N））操作。然而，更好的方法，可以分選在O未分類的部分（M * lgM抗體），然後在O（N + M）合併兩個排序部分。