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

Question

如果我有一个从0to的整数的排列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;
    }
  }

与其他基于交换的排序方法相比，当对从到的整数的相同排列执行时，基于交换的排序算法（如上述一种算法）是否具有相同的排序所需的交换数量的奇偶校验？0n-1

标签： c++sortingc++11permutationswap

Answer 1

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

元素序列中的反转是任何未按正确排序顺序的元素对：即a[i] > a[j]对于某些i < j. 完全排序的数组有零反转。交换任意两个元素会使反转的总计数改变奇数（这一点的证明留给读者练习）。因此，如果数组最初有奇数次反转，则必须执行奇数次交换才能对其进行排序；如果它以偶数次反转开始，则需要偶数次交换。