计算插入次数的有效方法是按递增顺序排序整数数组

Question

给定长度为n的值的数组,是否有一种方法可以计算插入排序执行的交换次数,以便在时间上优于O(n ²)对该数组进行排序？

例如 :

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

Answer 1

如果要计算插入排序所需的交换次数,那么您希望找到以下数字:对于每个元素,数组中先前元素的数量是否小于它？然后,这些值的总和是执行的交换总数.

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

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

这样做O(n)迭代的循环需要O(log 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).现在您已经拥有了平衡树,我们可以通过为树中的每个元素分配此元素所属的排序序列中的位置来扩充结构.一种方法是使用订单统计树,另一种方法是使用inorder遍历迭代树,用树的位置注释树中的每个值.

使用这个结构,我们可以通过查看树中的元素(时间O(log n)),然后查看排序序列中的位置来检查O(log n)时间元素是否在正确的位置它应该在哪个位置以及它当前所处的位置(记住我们在创建树时设置它).如果它不同意我们的预期立场,那么它就在错误的地方,否则它就在正确的位置.此外,我们可以通过在树中查找这两个元素(O(log n)时间总计)然后在O(1)中交换它们的位置来有效地模拟两个元素的交换.

因此,我们可以在时间O(n log n) - O(n log n)时间内实现上述算法来构建树,然后n次迭代做O(log n)工作以确定是否要交换.

希望这可以帮助!

Answer 2

以自然顺序排列它们所需的连续元素的互换次数等于给定排列中的反转次数.

所以这个问题的解决方案是找到给定数组中的反转次数.

这可以使用合并排序在O(n log n)中求解.

在合并步骤中,如果从右侧数组复制元素,则按左数组中剩余的项目数递增全局计数器(计算反转).这样做是因为刚刚复制的右数组中的元素参与了一个反转,其中所有元素都存在于左数组中.

希望这可以帮助