题目链接

算法竞赛进阶指南-21.超快速排序

题目要求只能过比较相邻两个数值的排序方法，实际上就是冒泡排序。在排序过程中找到一对大小颠倒的相邻数值，把它们交换，就会使得整个序列的逆序对数量-1。而对于一个有序序列，显然其逆序对的数量为0，因此该题就可以转换为求一个序列逆序对的数量，即为题目所求的交换次数。

Method : 归并排序

使用归并排序可以在${O(nlog_2n)}$，求一个长度为n的序列的逆序对的个数。

递归对左右两半排序时，可以把左右两半各自内部的逆序对数作为子问题，在合并时只需要考虑“左边一半里一个较大的数”与“右边一半里一个较小的数”构成逆序对的情形。

合并两个有序子序列${arr[l \sim mid]}$与${arr[mid + 1 \sim r]}$，采用两个指针$i，j$分别扫描，当出现$arr[i] > arr[j]$时，说明${arr[i \sim mid]}$中所有元素都与$arr[j]$满足逆序对，数量为$mid - i + 1$个。

#include <vector>
#include <iostream>

using namespace std;

typedef long long LL;

const int N = 5e5 + 7;

int n;
vector<int> tmp;

LL merge_sort(vector<int> &arr, int l, int r) {
    if (l >= r) return 0;
    
    int mid = l + (r - l) / 2;
    LL res = merge_sort(arr, l, mid) + merge_sort(arr, mid + 1, r);
    
    int k = 0;
    int i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) tmp[k ++] = arr[i ++];
        else {
            tmp[k ++] = arr[j ++];
            res += mid - i + 1; // 从i到mid全是满足的逆序对
        }
    }
    
    while (i <= mid) tmp[k ++] = arr[i ++];
    while (j <= r) tmp[k ++] = arr[j ++];
    
    for (int i = l, j = 0; j < k; i ++, j ++) arr[i] = tmp[j];
    return res;
}


int main () {
    while (true) {
        int n;
        scanf("%d", &n);
        
        if (n != 0) {
            vector<int> arr;
            for (int i = 0; i < n; i ++) {
                int x;
                scanf("%d", &x);
                arr.emplace_back(x);
            }
            tmp.resize(arr.size());
            LL res = merge_sort(arr, 0, arr.size() - 1);
            cout << res << endl;
        }
        else {
            break;
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度${O(nlog_2n)}$， 就是归并排序的时间复杂度。

• 空间复杂度${O(n)}$ 要开辟数组arr和tmp，长度均为n。