對(duì)一個(gè)無序序列進(jìn)行排序，要求一次只能交換相鄰的兩個(gè)數(shù)，那么最少需要交換多少次才可以完成排序呢？ 本問題假設(shè)序列所有數(shù)各不相同。

概念介紹： 1、逆序。一般認(rèn)為從左向右序列的數(shù)字增大認(rèn)為是正序的，那么從左到右序列的序列數(shù)字出現(xiàn)減小就認(rèn)為是逆序的。一個(gè)“逆序”的數(shù)學(xué)定義是這樣的，如果存在正整數(shù) i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，則 < A[i], A[j] > 這個(gè)有序?qū)ΨQ為 A 的一個(gè)逆序，又稱作一個(gè)逆序?qū)Α?2、逆序數(shù)。整個(gè)序列中的逆序?qū)Φ膫€(gè)數(shù)叫做序列的逆序數(shù)。 3、逆序列。逆序列是表示序列逆序?qū)傩缘囊粋€(gè)序列，其定義是這樣的，逆序列中的某一項(xiàng)aj表示原序列中的第二成分（左邊成分）為j的逆序?qū)Φ膫€(gè)數(shù)。逆序列中的j需要從小到大正序排列，這樣子組成的序列就叫作逆序列。顯然，逆序列各項(xiàng)之和也是序列的逆序數(shù)。

排序方法： 首先，根據(jù)待排序列，寫出其逆序列。 然后，根據(jù)逆序列中的每一項(xiàng)所代表的數(shù)j和逆序個(gè)數(shù)aj，將待排序列中對(duì)應(yīng)的數(shù)j向左鄰交換aj次。 那么，交換完成后，序列就排序完成。此時(shí)，交換的次數(shù)就是最少的次數(shù)，也是原序列的逆序數(shù)。

具體例子： 原序列： 4 8 2 7 5 6 1 3 逆序?qū)τ校?(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), 逆序數(shù)為18 逆序列為：6 2 5 0 2 2 1 0 解釋：1前面6個(gè)比它大的，2前面2個(gè)比它打的，3前面5個(gè)，4前面0個(gè)… 交換過程如下：