逆序数与排序¶

在线性代数中，定义行列式的时候，我们接触了一个叫做逆序数的概念。

而我们知道，在排列里交换两个数的位置时，逆序数的奇偶性改变。由此，我们可以联想数的排序问题应该和逆序数有关。

逆序对和逆序数¶

一般地，对于\(n\)个两两不同的数组成的数组\((a_1, \dots, a_n)\)（称为这\(n\)个数的一个排列；通常取\(1,2,\dots,n\)），若存在两个数\((a_i, a_j)\)满足\(i < j\)且\(a_i>a_j\)，则这对数称为逆序对(inversion)；而逆序对的总数则称为这个排列的逆序数(inversion number)。

冒泡排序¶

冒泡排序简介¶

给定\(n\)个数\(a_1, \dots, a_n\)构成的有序数组，我们希望找到一种算法，将这列数变成升序排列。其中最简单的一种算法便是冒泡排序(bubble sort)。

冒泡排序算法

Step 1 我们先从数组的第一项\(a_1\)开始，若\(a_1>a_2\)，则交换两个数的位置；否则，不做任何操作。继续将第一步得到的\(a_2\)与\(a_3\)比较，若\(a_2>a_3\)，则交换两个数的位置；否则，不做任何操作。以此类推，继续比较至\(a_{n-1},a_n\)，Step 1结束。

Step 1完成后，数组里最后一个数即为数组中最大的数。

Step 2 继续上一步得到的数组，由于最后一个已经最大，我们只需要对前\(n-1\)个数做排序，这样，继续使用Step 1中的方法，从\(a_1,a_2\)比较至\(a_{n-2},a_{n-1}\)，Step 2结束。

同样地，Step 2完成后，数组里倒数第二个数是数组里第二大的数。

重复以上过程，到Step \(n-1\)之后，所有的数就排序完成了。

Question

如何用数学归纳法证明这一个排序算法的正确性？

冒泡排序的时间复杂度为 \(\Theta(n^2)\)。下面是这一算法的 C 语言示例。

C语言示例

输入格式：第一行为一个正整数 \(n\)，代表数组的长度；第二行为 \(n\) 个整数 \(a_1, \dots, a_n\)，表示待排序的数列。

输出格式：一行 \(n\) 个数，表示按升序排列的数列。

#include <stdio.h>

const int MAXN = 100;
int a[MAXN];

void bubble_sort(int *start, int *end)
{
    int tmp;
    for (int* i = end - 1; i > start; i--)
    {
        for (int* j = start; j < i; j++)
        {
            if (*j > *(j + 1))
            {
                tmp = *j;
                *j = *(j + 1);
                *(j + 1) = tmp;
            }
        }
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    bubble_sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

冒泡排序与初等变换¶

因为冒泡排序的“交换两数”恰好对应了矩阵初等变换的交换两行，所以可以利用冒泡排序的思想来解决一些初等变换问题。

行列式逆序

将一个行列式的列通过初等变换变为原来的倒序排列（即，设 \(|A| = \text{det}(c_1, c_2, \dots, c_n)\)，我们要将行列式变换为 \(|B| = \text{det}(c_n, c_{n - 1}, \dots, c_1)\)），给出一种具体的变换方案，并确定变换后行列式的符号。

Solution

将一个数列变为原来的反序，也即将排列由 \(n, n - 1, \dots, 1\) 变为 \(1, 2, \dots, n\)。可以利用冒泡排序实现。由于数组是反序的，可以验证每次循环都会交换一次相邻数，因此总共交换了 \(1 + 2 + \dots + (n - 1) = n(n - 1)/2\) 次，符号变为 \((-1)^{n(n - 1)/2}\)，即 \(|B| = (-1)^{n(n - 1)/2}|A|\)。

冒泡排序与逆序数¶

在冒泡排序中，若给定的\(n\)个数两两不同，则交换的次数等于数组的逆序数。

Proof

设冒泡排序的交换次数为\(s\)，逆序数为\(i\)。

冒泡排序中，每次交换都对应消除一对相邻的逆序对，而这两个数与其他数的逆序关系，以及其他数之间的逆序关系都不变，此时逆序数\(i\)减少1。

当冒泡排序结束时，排列变成升序排列，逆序数减少到0。所以有\(i-s=0\)，即\(i=s\)。

归并排序¶

归并排序简介¶

归并排序 (merge sort) 是利用分治算法设计的一种排序方法。其平均和最坏时间复杂度均为 \(O(n \log n)\)，是一种优秀的排序算法。

归并排序的原理是，先将数列折半，拆分为两个小数列，如此递归下去直至拆分为单个数。单个数本身是有序的，接下来将小数列不断合并，保证合并后的数列依然有序。因为每次合并需要 \(\Theta(n)\) 的时间，归并排序的复杂度是 \(T(n) = T(n / 2) + \Theta(n)\)，根据主定理可以得出 \(T(n) = \Theta(n \log n)\)。

归并排序的算法实现¶

函数输入格式：a 为数组指针，l 为开头下标，r 为结尾下标，均为闭区间。

void merge_sort(int a[], int l, int r)
{
    if (l == r)
    {
        return;
    }
    int mid = (l + r) / 2;
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);

    // 合并两个数组
    int i = l, j = mid + 1, k = 0;
    while (i <= mid || j <= r)
    {
        if (i <= mid && j <= r)
        {
            if (a[i] <= a[j])
            {
                tmp[++k] = a[i];
                i++;
            }
            else
            {
                tmp[++k] = a[j];
                j++;
            }
        }
        else if (i <= mid)
        {
            tmp[++k] = a[i];
            i++;
        }
        else
        {
            tmp[++k] = a[j];
            j++;
        }
    }
    for (int i = 0; i < k; i++)
    {
        a[l + i] = tmp[1 + i];
    }
}

归并排序与逆序数¶

逆序数可以通过在冒泡排序中统计交换数来计算得到，但是，冒泡排序算法的时间复杂度是 \(\Theta(n^2)\)，这种算法效率太低了，有没有更快地方法呢？

答案是存在的，可以在归并排序的过程中统计一个数列的逆序数，这样就可以在 \(\Theta(n \log n)\) 时间内求出逆序数。这种方法的原理如下：

归并排序每次将数列折半分为前、后两个部分，容易验证数列的逆序数 = 前半段逆序数 + 后半段逆序数 + “前半段大于后半段”的逆序对数。前两者可以递归求解，而后者可以如下求解：假设我们在合并 \(a, b\) 两个升序数列，每次加入 \(a_i\) 时，设 \(b\) 已经加入 \(b_1, \dots, b_{j - 1}\)，则此时 \(a_i\) 比 \(b_1, \dots, b_{j - 1}\) 都大，因此 \(a_i\) 贡献的逆序数是 \(j - 1\)。这样就可以在合并时顺便统计出后者，得到完整的逆序数。

C 语言代码如下：

long long inversion(int a[], int l, int r)
{
    int mid = (l + r) / 2;
    long long ans = 0;
    if (l < mid)
    {
        ans += inversion(a, l, mid);
    }
    if (mid + 1 < r)
    {
        ans += inversion(a, mid + 1, r);
    }
    int i = l, j = mid + 1, k = 0;
    while (i <= mid || j <= r)
    {
        if (i <= mid && j <= r)
        {
            if (a[i] <= a[j])
            {
                tmp[++k] = a[i];
                i++;
                ans += j - mid - 1;
            }
            else
            {
                tmp[++k] = a[j];
                j++;
            }
        }
        else if (i <= mid)
        {
            tmp[++k] = a[i];
            ans += r - mid;
            i++;
        }
        else
        {
            tmp[++k] = a[j];
            j++;
        }
    }
    memcpy(a + l, tmp + 1, k * sizeof(int));
    return ans;
}