sorting - 除最后一个元素外的排序数组

Question

给定一个已经排序的 n 个不同元素的数组，其中只有最后一个元素是乱序的，插入排序会是这里使用的最快算法吗？

Ex: [1, 3, 5, 6, 7, 9, 2]

标签： sortinginsertion-sort

Answer 1

如果它是一个数组，是的，插入排序。

最坏情况复杂度：O(n)

最坏的情况：未排序的元素是最小的元素。

如果它是任何类型的链表，其中插入成本是恒定时间，那么二分查找将是最快最有效的方法。

最坏情况复杂度：O(log(n))