algorithm - 除前 K 和后 K 个元素外的排序数组

Question

已知大小为 n 的数组 A 已排序，除了前 k 个元素和最后 k 个元素，其中 k 是常量。以下哪种算法最适合对数组进行排序？

 A) Quicksort
 B) Bubble sort
 C) Selection Sort
 D) Insertion Sort

答案是D

无法理解这是如何工作的，如果还给出了合并排序，答案会是什么？

Answer 1

让我们来看看算法的复杂度:

A) 快速排序:将采用更坏的情况 O(n²) 平均 O(n log n)
B) 冒泡排序:需要 O(n²)
C) 选择排序:需要 O(n²)
D) 插入排序:如果 k 是常量 = O(n)

，则需要 O(k* n)

所以D的性能最好。(对于k个元素中的每一个:O(log n)找到要插入的位置+O(n)要插入)

但由于已知 Quicksort 具有较小的常量因子并且平均为 O(n log n)，因此对于“较大”的 k 值，它很可能更快。

---

额外:

E) 合并排序:需要 2 * O(k log k) + O(n)

• 对前面的k个元素排序O(k log k)
• 对末尾的k个元素排序O(k log k)
• 合并 3 个列表 O(n)

总而言之，k O(n) 因此基于与插入排序相同的复杂性。

但是如果你用 k 不是常量来看它:
合并排序: O(k log k) + O(n)
插入排序: O(k* n)

所以插入排序会更快。

反对合并排序的论据:
一般来说，合并排序不是就地(插入排序是)，因此您需要额外的空间或非常聪明的实现变体，以设法就地完成它而不会产生太多复杂性开销。