使用1个自由交换和相邻交换对N的排列进行排序

Question

问题：

给定一个由N个数字组成的数组包含N的排列。你有两种类型的交换：

• 交换数组的任意2个数字(您只能执行一次)
• 交换相邻号码(您可以多次这样做)

对数组排序的交换次数最少是多少？

示例：

arr[] = {5, 3, 4, 2, 1}
answer: 3
Explaination:
- Swap 5 and 1
- Swap 4 and 2
- Swap 3 and 2

p/S:

我认为我们需要使用"；自由交换；首先，然后使用merge排序。但我不知道如何使用"；自由交换；使得合并排序最小。

Answer 1

我认为您可以将最左边的数字与最右边的数字进行交换。

左边是索引i，其中arr[i]-i是最大值。右边是索引j，其中arr[j]-j是最小值。然后把元素i和j交换，这就是O(n)。

然后，你可以计算你为冒泡排序所做的交换次数。为此，你可以统计当前元素右侧较小的所有元素。您可以在O(n-logn)中从右向左执行此操作，然后将每个元素插入一个平衡排序树中，在该树中还存储每条边的子树中的节点数(例如，修改的AVL树)。这允许您计算O(logn)中当前元素右侧较小的元素数量。