arrays - 非优化排序算法，使用哪一种？

Question

排序数组的最后一个元素被替换为数组中不存在的随机值。应该使用哪个经典的（即非优化的）排序算法版本来尽可能有效地对该数组进行排序？

标签： arraysalgorithmsorting

Answer 1

由于除了最后一个元素之外，数组已排序，因此不需要排序。

只需从数组中删除最后一个元素，并将其插入到正确的位置。花费O(log n)时间来找到插入它的位置。

---

Ps
正如@Henry 所指出的，实际插入数组（至少在大多数编程语言中）将花费另一个O(n)时间，因为它很可能意味着将所有元素向右移动一个以释放我们想要的位置插入我们的元素。