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

Question

如果我有一个从0到n-1的整数排列，我想对这个排列进行升序排序，是不是不管swap -based 排序方法，parity 在所有 swap-based排序方式?

例如，考虑我在下面提供的基于交换的排序方法，用 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 .完全排序的数组具有零反转。交换任意两个元素都会将反转的总数更改为奇数（对此的证明留作 reader 的练习）。因此，如果数组最初有奇数次反转，则必须执行奇数次交换才能对其进行排序；如果它以偶数次反转开始，则需要偶数次交换。

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

Parity of the Number of Swaps of Swap-Based Sorting Algorithms

c++

sorting

swap

permutation

c++11