排序算法以交换整数的和的大小为衡量标准，哪一种代价最小？

问题：排序算法以交换整数的和的大小为衡量标准，哪一种代价最小？
描述:

有一个整数序列需要按升序排序。我们知道排序的基本操作是交换两个数的位置，定义被交换的两个数的和为本次交换的代价。那么所有交换次数代价的和为总代价。
请问哪一种排序方法代价最小？

---

解决方案1:

这个是最小逆序对吗？归并排序吧。

解决方案2:

正常的排序是不会这么计算代价的，因此只能把楼主的问题看成是一道算法题了。

先把序列排序，然后从大到小依次检查每个元素，假设新序列中第i位的元素在原序列中是第j位，那么就相当于交换原序列中的（i，j），代价为a[i]+a[j]。如果i==j则不交换。这样，总交换次数是n-1次，而且大数被交换的概率可能会更小一些。

毕竟是基于贪心思想，所以不能保证这个代价之和是最小的，但是应该比大部分算法的代价要小一点。

解决方案3:

计数排序不存在数据位置的交换，可以在O(n)内排序。
交换数据位置的排序算法中，快排的交换数据次数可能会多于归并排序这种稳定的排序算法。