通过交换相邻数来完成排序所需要的最少交换次数

对一个无序序列进行排序，要求一次只能交换相邻的两个数，那么最少需要交换多少次才可以完成排序呢？
 
本问题假设序列所有数各不相同。
 
概念介绍：
 
1、逆序。一般认为从左向右序列的数字增大认为是正序的，那么从左到右序列的序列数字出现减小就认为是逆序的。一个“逆序”的数学定义是这样的，如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 <A[i], A[j]> 这个有序对称为 A 的一个逆序，又称作一个逆序对。
 
2、逆序数。整个序列中的逆序对的个数叫做序列的逆序数。
 
3、逆序列。逆序列是表示序列逆序属性的一个序列，其定义是这样的，逆序列中的某一项aj表示原序列中的第二成分（左边成分）为j的逆序对的个数。逆序列中的j需要从小到大正序排列，这样子组成的序列就叫作逆序列。显然，逆序列各项之和也是序列的逆序数。
 
排序方法：
 
首先，根据待排序列，写出其逆序列。
 
然后，根据逆序列中的每一项所代表的数j和逆序个数aj，将待排序列中对应的数j向左邻交换aj次。
 
那么，交换完成后，序列就排序完成。此时，交换的次数就是最少的次数，也是原序列的逆序数。
 
具体例子：
 
原序列： 4 8 2 7 5 6 1 3
 
逆序对有：
 
(4,2), (4,1), (4, 3),
(8,2), (8,7), (8,5), (8,6), (8,1), (8,3),
(2,1),
(7,5), (7,6), (7,1), (7,3),
(5,1), (5,3),
(6,1), (6,3),
 
逆序数为18
 
逆序列为：6 2 5 0 2 2 1 0
 
交换过程如下：

 4 8 2 7 5 6 1 3  
（1向左交换6次）  
 4 8 2 7 5 1 6 3  
 4 8 2 7 1 5 6 3  
 4 8 2 1 7 5 6 3  
 4 8 1 2 7 5 6 3  
 4 1 8 2 7 5 6 3  
 1 4 8 2 7 5 6 3  
（2向左交换2次）  
 1 4 2 8 7 5 6 3  
 1 2 4 8 7 5 6 3  
（3向左交换5次）  
 1 2 4 8 7 5 3 6  
 1 2 4 8 7 3 5 6  
 1 2 4 8 3 7 5 6  
 1 2 4 3 8 7 5 6  
 1 2 3 4 8 7 5 6  
（5向左交换2次）  
 1 2 3 4 8 5 7 6  
 1 2 3 4 5 8 7 6  
（6向左交换2次）  
 1 2 3 4 5 8 6 7  
 1 2 3 4 5 6 8 7  
（7向左交换1次）  
 1 2 3 4 5 6 7 8  

思考：
 
上面的过程，其实就是冒泡排序的过程，每一轮都能将最小的数冒到最左边。所区别的是，冒泡排序是直接两两比较、进行交换，而这里是先找逆序列，然后不比较、直接交换。两者在程序代码上的复杂度是差不多的。这里提供的一点是最少的交换次数-序列的逆序数。
 
原文：http://blog.csdn.net/ojshilu/article/details/17066737