我们有一个由N个数字(1，2，3，4，…N)组成的未排序序列。我们可以通过按特定顺序交换相邻元素来对整个序列进行排序。给定一个序列，我如何计算排序该序列所需的最小可能交换。
例如，考虑序列{4，2，5，3，1}。
最好的排序方法是按以下顺序使用7个交换
- 交换3，1:｛4，2，5，1，3｝
- 交换5，1:｛4，2，1，5，3｝
- 交换4，2:｛2，4，1，5，3｝
- 交换4，1:｛2，1，4，5，3｝
- 交换2，1:｛1，2，4，5，3｝
- 交换5，3:｛1，2，4，3，5｝
- 交换3、4:｛1、2、3、4、5｝
贪婪算法没有被证明是富有成效的。反例很容易构造。下一个显而易见的解决方案选择是动态编程。
假设我们有一个未排序的序列：{A1，A2，…Ai，A(i+1)，…，an}。我们知道对序列{Ai，A(i+1)，…，An}进行排序所需的最小交换次数是Min[Ai，A(i+1)，..，An}。问题是找到Min[A(i-1)，Ai，…，An]。
好吧，我脑海中浮现的第一个想法是，在已经排序的序列{Ai，…，An}中，添加将A(i-1)放在正确位置所需的步骤数。这是有效的：问题中给出的例子已经用完全相同的方法解决了。
但我无法证明这个解决方案的有效性。我经常是这样。当我认为我已经解决了这个问题时，我能做的最好的事情就是获得一个"直观"的证明。我在上高中，没有受过正式的算法训练。我做这件事纯粹是出于兴趣。
有没有严格的数学符号可以将这个问题转化为形式化的证明？这个符号可以推广到其他问题吗？怎样如果能以高中生能理解的形式呈现，我将不胜感激。
这是一个经典的算法问题。交换的最小数量等于阵列中的反转数量。如果我们具有索引i和索引j，使得i>aj和i<CCD_ 4，则这被称为反转。让我们来证明这一说法！我需要一些狐猴在路上：
引理1:如果两个相邻元素没有反转，则对数组进行排序
证明：让我们假设没有两个相邻元素形成反转。这意味着i<=对于区间[0，n-1]中的所有i，ai+1。由于<=是可传递的，这将意味着数组已排序。
引理2:两个相邻元素的单个交换将使数组中的反转总数最多减少1
证明：当我们交换两个相邻元素ai和ai+1时，它们相对于数组中所有其他元素的相对位置将保持不变。也就是说，对于在i+1之后的所有元素，它们仍将在i+1之后，而对于i之前的所有元素而言，它们仍在1前面。这也意味着，如果i或i+1与元素aj形成反转，则它们在交换后仍将与其形成反转。因此，如果我们交换ai和ai+1，我们将只影响这两个元素用来形成的逆。由于两个元素可能参与不超过一个逆，我们也证明了引理。
引理3:为了对数组进行排序，我们至少需要对相邻元素进行NI交换，其中NI是数组中的逆次数
证明：在排序的数组中没有逆。同样根据引理2，一次交换最多可以减少一次反转次数。因此，我们需要执行至少与反转次数一样多的互换。
引理4:我们总是可以对执行相邻元素的NI交换的数组进行排序，其中与上面一样，NI是数组中的反转数
证明：如果我们假设在我们的数组中没有两个相邻元素的反转，那么根据引理1，数组将被排序，我们就完成了
否则，至少有一对相邻元素形成反转。我们可以交换它们，从而将反演的总数减少一次。我们可以准确地继续执行此操作NI次。
现在，我从一开始就证明了我的说法。
剩下的唯一问题是如何计算给定数组中的反转次数。您可以使用对合并排序的轻微修改来实现这一点，在合并阶段累积反转。您可以看看这个答案，了解如何实现它的详细信息。该算法的总体复杂度为O(n*log(n))。
感谢@Ivaylo Strandjev的解释，为了让答案更完整，这里是Java实现：
// http://stackoverflow.com/questions/20990127/sorting-a-sequence-by-swapping-adjacent-elements-using-minimum-swaps
// The minimum number if swaps is equal to the number of inversions in the array
public static long sortWithSwap(int [] a) {
return invCount(a, 0, a.length-1);
}
private static long invCount(int[] a, int left, int right) {
if(left >= right) return 0;
int mid = left + (right-left)/2;
long cnt = invCount(a, left, mid) + invCount(a, mid+1, right);
cnt += merge(a, left, mid, right);
return cnt;
}
private static long merge(int[] a, int left, int mid, int right) {
long cnt = 0;
int i = left, j = mid+1, k = left;
int[] b = new int[a.length];
while(i<=mid && j<=right) {
if(a[i] <= a[j]) b[k++] = a[i++];
else {
b[k++] = a[j++];
cnt += mid - i + 1;
}
}
while(i <= mid) {
b[k++] = a[i++];
}
while(j <= right) {
b[k++] = a[j++];
}
for(i=left; i<=right; i++) a[i] = b[i];
return cnt;
}