[数据结构与算法]六、基础算法 -- 超快速排序

题目描述

在这个问题中，您必须分析特定的排序算法----超快速排序。

该算法通过交换两个相邻的序列元素来处理 $n$ 个不同整数的序列，直到序列按升序排序。

对于输入序列 9 1 0 5 4，超快速排序生成输出 0 1 4 5 9。

您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。

输入格式

输入包括一些测试用例。

每个测试用例的第一行输入整数 $n$，代表该用例中输入序列的长度。

接下来 $n$ 行每行输入一个整数 $a_i$,代表用例中输入序列的具体数据，第 $i$ 行的数据代表序列中第 $i$ 个数。

当输入用例中包含的输入序列长度为 $0$ 时，输入终止，该序列无需处理。

输出格式

对于每个需要处理的输入序列，输出一个整数 $op$，代表对给定输入序列进行排序所需的最小交换操作数，每个整数占一行。

数据范围

$0\le n<500000$,
一个测试点中，所有 $n$ 的和不超过 $500000$。
$0\le a_i\le 999999999$

输入样例：

5
9
1
0
5
4
3
1
2
3
0

输出样例：

6
0

算法

(归并排序)

前置知识： 逆序数

在一个排列中，如果一对数的前后位置与大小顺序相反，即 前面的数大于后面的数，那么它们就称为一个逆序。一个排列中 逆序的总数 就称为这个排列的逆序数。也就是说，对于 n 个不同的元素，先规定各元素之间有一个标准次序（例如 n 个 不同的自然数，可规定从小到大为标准次序），于是在这 n 个元素的任一排列中，当某两个元素的实际先后次序与标准次序不同时，就说有 1 个逆序。一个排列中所有逆序总数叫做这个排列的逆序数。

第一个例子： 2 3 4 5 6 1 的逆序数为 5， a[i] 表示当前下标为 i 的逆序数量

• 2 1 是一个逆序对 a[1] = 1
• 3 1 是一个逆序对 a[2] = 1
• 4 1 是一个逆序对 a[3] = 1
• 5 1 是一个逆序对 a[4] = 1
• 6 1 是一个逆序对 a[5] = 1
• 1 没有逆序对 a[6] = 0

2 3 4 5 6 1 -> 2 3 4 5 1 6 -> 2 3 4 1 5 6 -> 2 3 1 4 5 6 -> 2 1 3 4 5 6 -> 1 2 3 4 5 6

若将该序列转化成从小到大排序，需要 a[1] + a[2] + a[3] + a[4] + a[5] + a[6] = 5 (也就是该数列逆序数) 次交换。

第二个例子： 2 4 3 1 的逆序数为 4

• 2 1 是一个逆序对 a[1] = 1
• 4 3 是一个逆序对 a[2] = 1
• 4 1 是一个逆序对 a[2] = 2
• 3 1 是一个逆序对 a[3] = 1
• 1 没有逆序对 a[4] = 0

2 4 3 1 -> 2 4 1 3 -> 2 1 4 3 -> 1 2 4 3 -> 1 2 3 4

若将该序列转化成从小到大排序，需要 a[1] + a[2] + a[3] + a[4] = 4 (也就是该数列逆序数) 次交换。

掌握了上述知识后可以尝试一下这道题目：逆序对的数量

暴力枚举

计算一个排列的逆序数的直接方法是逐个枚举逆序，同时统计个数。例如在序列 { 2, 3, 4, 5, 6，1 } 中，逆序依次为 (2,1)，(3,1)，(4,1)，(5, 1)，(6, 1) 因此该序列的逆序数为 5。但是时间复杂度为 $O(n^2)$。

归并排序

在归并排序的同时计算逆序数。且该方法只是交换相邻的两个元素。所以上述问题就变成了求一个排列的逆序对数量。

首先先看一张图：

归并排序算法的框架为：

1. 递归算$左边$的；
2. 递归算$右边$的；
3. 算$一个左一个右$的；
4. 把三个结果加在一起
   

问题详解：

1. 在一些题解中说到可以不用计算前两种情况，只需要看第三种情况，我的理解是：需要真正知道归并排序在做什么。这就是我们上面的那张图，归并排序分为两个大步骤；$分$ 和 $治$，从上面的栗子中我们看出，分的步骤会把所有的数组分为一个单独的数字，所以也就解释了为什么不需要考虑前两种情况，最种都会到第三种情况上，因为只有每组只有一个数字，它没有人同组，所以最终都是会变成第三种情况。
2. 下面解释治.
   

具体步骤

1. 第一步对元素进行排序，可以看到直接是求两个单独元素的逆序对，如果是逆序对，答案 ans++ ,然后合并两个数字变成一个有序的数组。
2. 第二步，在对两个分组的数字进行求逆序对，此时没有到只剩下两个分组的情况，可以把这些步骤看作是内部之间求逆序对。
3. 第三步就是两个分组求逆序对。可以看到此时前后两个分组都是有序的，前面的数组的下边为 l ~ mid，后面的下标为 mid + 1 ~ r，我们可以在归并的时候是需要把两个数组的值重新赋值到原数组中的，所以就可以比较两个数组的值，也就是可以求逆序对。如果 A 数组的值 q[i] 大于 B 数组的值 q[j]，代表在 A 数组中 i~mid 都是大于q[j] 的，所以对于 q[j] 来说他的逆序对数量为 mid - i + 1 ，可以参考上面的图。
4. 例如 2 3 4 5 6 1 经过归并后得出两个有序序列 2 3 4 和 1 5 6 （注意：2 3 4 也是需要归并交换位置得到 1 2 3的）即将 1 插入到 2 位置前，此操作相当于交换了 3 次位置，设 2 元素的位置为 i，1 元素的位置是中间位置 mid ，则此时交换的次数为 mid - i + 1 = 3。

C++ 代码

#include <cstdio>

using namespace std;

typedef long long LL;

const int N = 500010;

int n;
LL q[N], w[N];

LL merge_sort(int l, int r)
{
    if (l == r) return 0;

    int mid = l + r >> 1;
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) w[k ++ ] = q[i ++ ];
        else
        {
            res += mid - i + 1;
            w[k ++ ] = q[j ++ ];
        }
    while (i <= mid) w[k ++ ] = q[i ++ ];
    while (j <= r) w[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = w[j];

    return res;
}

int main()
{
    while (scanf("%d", &n), n)
    {
        for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

        printf("%lld\n", merge_sort(0, n - 1));
    }

    return 0;
}

参考资料

超快速排序 - 小呆呆