基于互换的排序算法的互换次数的奇偶性。

Question

如果我有一个整数的排列组合，从 0 到 n-1我想按升序排列排列组合，是不是无论怎样的 掉期 使用排序方法，则 奇偶性 掉期的数量在所有的掉期中都是一样的。掉期 排序方法？

例如，考虑我下面提供的一种基于交换的排序方法，用C++编写。

(注意: pos[i] 存储列表中元素 "i "的当前索引（基于0）。

int cnt = 0; // stores the number of operations
  for (int i = 0; i < n; i++) {
    if (pos[i] != i) {
      cnt++;
      int temp = a[i];
      int temp_pos = pos[i];
      swap(a[i], a[pos[i]]);
      pos[i] = i;
      pos[temp] = temp_pos;
    }
  }

会 掉期 诸如上述的排序算法，与其他基于交换的排序方法相比，当对相同的整数排列方式进行排序时，所需的交换次数都具有相同的奇偶性，从 0 到 n-1?

Answer 1

是的，这是真的。证明的草图是这样的。

安 倒置 在元素序列中，是指任何一对元素不按适当的排序顺序排列：即。a[i] > a[j] 对于 i < j. 一个完全排序的数组的反转数为零。交换任何两个元素都会使反转的总次数改变一个奇数（这一点的证明留给读者去做）。因此，如果数组最初的反转数是奇数，那么必须执行奇数的交换才能对其进行排序；如果数组最初的反转数是偶数，则需要偶数的交换。