计算交换次数以插入以递增顺序对整数数组进行排序的有效方法

Question

给定一个长度为 n 的值数组，有没有办法计算插入排序将执行的交换次数，以便比 O(n 2 ) 在时间上更好地对该数组进行排序？

例如 ：

 arr[]={2 ,1, 3, 1, 2};  // Answer is 4.

算法：

 for i <- 2 to N

    j <- i

 while j > 1 and a[j] < a[j - 1]

       swap a[j] and a[j - 1]  //I want to count this   swaps?

       j <- j - 1

原文由 Anil Arya 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

如果你想计算插入排序中需要交换的次数，那么你想找到以下数字：对于每个元素，数组中有多少先前的元素小于它？这些值的总和就是执行的交换总数。

要找到数字，您可以使用顺序统计树，这是一种平衡的二叉搜索树，可以有效地告诉您树中有多少元素小于某个给定元素。具体来说，Orde 统计树支持 O(log n) 插入、删除、查找和计算树中有多少元素小于某个值。然后，您可以计算将执行多少次交换，如下所示：

1. 初始化一个新的空订单统计树。
2. 设置计数 = 0
3. 对于每个数组元素，按顺序：
   1. 将元素添加到订单统计树。
   2. 添加以计算树中小于添加值的元素数。
4. 返回计数，

这会花费 O(log n) 时间进行 O(n) 次循环迭代，因此完成的总工作量为 O(n log n)，这比蛮力方法更快。

---

如果要计算选择排序中的交换次数，则可以使用插入排序仅在第 k 次执行交换的事实，如果在处理列表的前 k-1 个元素后，位置 k 的元素不是第 k 个最小的元素。如果你能有效地做到这一点，那么我们有以下算法的基本草图：

1. 设置总计 = 0
2. 对于 k = 1 到 n：
   1. 如果索引 k 处的元素不是第 k 个最大元素：
      1. 将其与第 k 个最大的元素交换。
      2. 增量总计
3. 退货总额

那么我们如何有效地实现这一点呢？我们需要能够有效地检查给定索引处的元素是否是正确的元素，并且还需要有效地找到真正属于给定索引处的元素的位置。为此，首先创建一个平衡的二叉搜索树，将每个元素映射到其在原始数组中的位置。这需要时间 O(n log n)。现在您已经有了平衡树，我们可以通过为树中的每个元素分配该元素所属的排序序列中的位置来扩充结构。一种方法是使用顺序统计树，另一种方法是使用中序遍历遍历树，用位置注释树中的每个值。

使用这种结构，我们可以在 O(log n) 时间内检查一个元素是否在正确的位置，方法是在树中向上查找元素（时间 O(log n)），然后查看排序序列中的位置它应该在哪个位置以及它当前位于哪个位置（请记住，我们在创建树时设置了它）。如果它与我们预期的位置不一致，那么它在错误的位置，否则它在正确的位置。此外，我们可以通过在树中查找这两个元素（总共 O(log n) 时间）然后在 O(1) 中交换它们的位置来有效地模拟两个元素的交换。

因此，我们可以在 O(n log n) - O(n log n) 时间内实现上述算法来构建树，然后进行 n 次迭代 O(log n) 来确定是否交换。

希望这可以帮助！

原文由 templatetypedef 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

我不确定，但我怀疑找到最小数量是一个难题。除非有捷径，否则您只会搜索最佳 _排序网络_，您应该能够使用您最喜欢的搜索引擎（或维基百科）找到好的资源。

如果您只关心 big-O 复杂性，答案是 O(n log n) ，如果您查看一些有效的就地排序的分析，您可能可以获得更具体的界限（其中的一些实际常量）堆排序或平滑排序等算法。

原文由 R.. GitHub STOP HELPING ICE 发布，翻译遵循 CC BY-SA 3.0 许可协议