超快速排序-逆序对

  • 初始有k个逆序对，就至少需要操作k次。为什么？
  • 因为每次相邻元素交换，只影响1对逆序对。

image.png
但结果是否恰好为逆序对的数量呢？
如果当前序列还不是升序，必然满足存在一对相邻的数，将他们交换，逆序对必然会减1。循环判断。