排序与插入部分排序的数组排序

Question

我哈瓦阵列与所述第一，直到N个元素被分选和N + 1，直到elemnt N + M未排序（阵列包括N + M个元素的）。使用插入排序对这个数组进行排序的复杂性是什么？我认为它是（N + M）^ 2，是吗？

Answer 1

如果你想使用插入排序，你将需要O（M *（M + N））操作。然而，更好的方法，可以分选在O未分类的部分（M * lgM抗体），然后在O（N + M）合并两个排序部分。