题目：
解题过程：
第一次做这题的时候，很自然的想到了冒泡和选择，我交的代码是用选择写的。基本全WA(摊手)。
贴上第一次的代码：
//
// main.cpp
// sequenceschange
//
// Created by wasdns on 16/10/7.
// Copyright ? 2016年 wasdns. All rights reserved.
//
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
using namespace std;
int seq[50005];
int main() {
int i, j, n;
cin >> n;
for (i = 0; i < n; i++) {
cin >> seq[i];
}
int cnt = 0;
int t = 0;
for (i = n - 1; i >= 0; i--) {
for (j = i - 1; j >= 0; j--) {
if(seq[i] > seq[j]) break;
cnt ++;
t = seq[i];
seq[i] = seq[j];
seq[j] = t;
}
}
cout << cnt << endl;
return 0;
}
冒泡和选择，这两种算法的问题在于，会有重复比较的元素，不满足题意要求的最小比较次数。
本题也是比较经典的逆序对问题，解决的方法是插入排序。
这里给出链接参考：九大排序算法再总结
第二种算法(分治加插入排序)思想：
给出一个数组，以及给出左边界l右边界r代表需要排序的序列范围，将这个序列不断分成两个部分，直到递归到单个元素再向上进行Union的操作，Union的操作通过插入排序来实现。
//
// main.cpp
// 逆序对
//
// Created by wasdns on 16/12/1.
// Copyright © 2016年 wasdns. All rights reserved.
//
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[50010];
/*
用来debug的函数
*/
void printa(int l, int r)
{
for (int i = l; i <= r; i++) {
printf("%d ", a[i]);
}
printf("\n");
}
/*
交换函数
*/
void swap(int i, int j)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
/*
Union 两部分合并函数
*/
int Union(int l, int r)
{
if (l == r) return 0;
int i, p1, p2; //p1指向序列A的元素，p2指向序列B的元素
int cnt = 0; //记录比较次数
for (i = l+1; i <= r; i++)
{
p1 = i-1;
p2 = i;
while (a[p2] < a[p1] && p1 != 0)
{
swap(p1, p2);
cnt++;
p1--;
p2--;
}
}
return cnt;
}
/*
排序算法主体
*/
int divsort(int l, int r)
{
//printf("div:");
//printa(l, r);
if (l == r) return 0;
int cnt = 0;
int mid = (l+r) / 2;
int ltime = divsort(l, mid);
int rtime = divsort(mid+1, r);
cnt += ltime;
cnt += rtime;
cnt += Union(l, r);
//printf("afterdiv:");
//printa(l, r);
return cnt;
}
void Initial(int n)
{
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
}
int main()
{
int n;
cin >> n;
Initial(n);
int cnt;
cnt = divsort(1, n);
printf("%d\n", cnt);
return 0;
}
结果是部分点TLE：
分析下算法复杂度：选择最后一次的Union操作，最坏情况下一共有50000个节点，从l到mid是25000个排好序的元素，从mid开始到r有25000个无序的元素，将后面的25000个元素插入到前面的序列，>=25000*25000的时间；复杂度为O(n^2)，因此TLE。
于是选择使用归并排序，之前的操作和算法二的思想类似，但是修改了Union的操作：维护一个数组b，使用两个指针指向两个待排序的序列，把这两个指针分别指向的元素进行比较，较小的元素加入到b中，指向它的指针后移，直到到达边界。
另外一个需要care的点是cnt的计数：
倘若先前的序列叫做A，后面的序列叫做B，当判断出B序列的当前指向元素较小进入数组b时，相当于是通过mid+1-p1(p1是当前指针指向A的位置)次比较的操作将元素移至有序的位置。
int Union(int l, int r)
{
if (l == r) return 0;
int mid = (l+r) / 2;
int i, p1 = l, p2 = mid+1;
int cnt = 0;
int tot = 1;
while (p1 <= mid && p2 <= r)
{
if (a[p1] > a[p2]) {
cnt += mid+1-p1; //相当于比较了mid+1-p1次
b[tot++] = a[p2++];
}
else b[tot++] = a[p1++];
}
if (p1 > mid && p2 <= r)
{
while (p2 <= r)
{
b[tot++] = a[p2++];
}
}
else if (p2 > r && p1 <= mid)
{
while (p1 <= mid)
{
b[tot++] = a[p1++];
}
}
for (i = l; i <= r; i++)
{
a[i] = b[i-l+1];
}
return cnt;
}
int divsort(int l, int r)
{
//printf("div:");
//printa(l, r);
if (l == r) return 0;
int cnt = 0;
int mid = (l+r) / 2;
int ltime = divsort(l, mid);
int rtime = divsort(mid+1, r);
cnt += ltime;
cnt += rtime;
cnt += Union(l, r);
//printf("afterdiv:");
//printa(l, r);
return cnt;
}
算法复杂度：O(n)
2016/12/2