已知大小为 n 的数组 A 除了前 k 个元素和最后 k 个元素（其中 k 是常数）外都已排序。以下哪种算法最适合对数组进行排序？
A) Quicksort
B) Bubble sort
C) Selection Sort
D) Insertion Sort
给出的答案是 D。
无法理解这是如何工作的，如果还给出了合并排序，那么答案是什么？
让我们看一下算法的复杂度：
\n\nA) 快速排序：最坏情况为O(n\xc2\xb2)平均O(n log n)
\n B) 冒泡排序：将花费O(n\xc2\xb2)
\n C) 选择排序：将花费O (n\xc2\xb2) \n D) 插入排序：如果 k 是常数 = O(n)
，则需要O(k* n )
所以D的性能最好。\n（对于 k 个元素中的每一个：O(log n) 查找要插入的位置 + O(n) 插入）
\n\n但由于已知快速排序具有较小的常数因子并且平均为 O(n log n)，因此对于“较大”的 k 值来说，它很可能会更快。
\n\n额外的：
\n\nE) 合并排序：需要2 * O(k log k) + O(n)
\n\n总而言之，k O(n)为常数，因此基于与插入排序相同的复杂性。
\n\n但如果你用 k 不恒定来看待它：
\n合并排序： O(k log k) + O(n)
\n插入排序： O(k* n)
所以插入排序会更快。
\n\n反对合并排序的论点：
\n一般来说，合并排序不是就地排序（插入排序是），因此您需要额外的空间或非常聪明的实现变体，设法就地进行排序，而不会增加太多的复杂性开销。