Yharim
Snow is on the ground
So NVIDIA, Fuck You🖕
算法
发布于 2021-1-10

排序

你听说过猴子排序吗？

简介 #

排序数组 $a$（长度 $n$）中的元素. 本章只研究升序排序.

选择排序 #

在第 $i$ 次遍历中，交换 $a[i]$ 和第 $i$ 小的数.

时间复杂度：$O(n^2)$.

for (int i = 1; i <= n; i ++) {
    int tmp = i;   // tmp: 第 i 小的数
    for (int j = i + 1; j <= n; j ++)
        if (a[j] < a[tmp]) tmp = j;
    swap(a[i], a[tmp]);
}

冒泡排序 #

重复扫描数组 $a$. 若 $a[i]>a[i+1]$ 就交换它们. 当没有可交换元素时结束排序.

时间复杂度：$O(n^2)$.

while (true) {
    bool swapped = false;
    for (int i = 1; i <= n; i ++) {
        if (a[i] > a[i + 1]) {
            swap(a[i], a[i + 1]);
            swapped = true;
        }
    }
    if (!swapped)
        break;
}

插入排序 #

将数组 $a$ 分为「已排序」和「未排序」区. 每次将「未排序」区的一个元素插入「已排序区」的正确位置.

时间复杂度：$O(n^2)$.

for (int i = 2; i <= n; i ++) {
    int tmp = a[i], j = i - 1;
    while (j >= 1 && a[j] > tmp)
        a[j + 1] = a[j --];
    a[j + 1] = tmp;
}

计数排序 #

记录每个元素出现的次数，然后依次输出.

$f[x]$：数字 $x$ 出现了几次.

时间复杂度：$O(n)$. 不适用于大范围元素.

int maxn = - 1e9;
for (int i = 1; i <= n; i ++) {
    f[a[i]] ++;
    maxn = max(maxn, a[i]);
}
int p = 0;
for (int i = 1; i <= maxn; i ++)
    for (int i = 1; i <= f[i]; i ++)
        a[++ p] = i;

快速排序 #

  1. 设定基准数为数组的中间数 $a[m]$.
  2. 扫描数组，将所有比 $a[m]$ 小的元素移至其左，大于 $a[m]$ 的元素移至其右.
  3. 对 $a[m]$ 左右的子数组进行相同操作.

平均时间复杂度：$O(n\log n)$.

最坏时间复杂度：$O(n^2)$.

void qsort(int l, int r) { // 对 a[l ... r] 排序
    if (l >= r) return;
    int i = l, j = r, m = (l + r) / 2;
    while (i <= j) {
        while (a[i] < a[m]) i ++;
        while (a[j] > a[m]) j --;
        if (i <= j)
            swap(a[i ++], a[j --]);
    }
    qsort(l, j), qsort(i, r);
}

归并排序 #

  1. 将数组分为 $a[l\sim m]$ 和 $a[m+1\sim r]$ 两个子数组.
  2. 递归排序两个子数组.
  3. 合并两个已排序的子数组.
    • 设定指针 $i$ 和 $j$，最初位置分别为两个子数组的起始位置.
    • 比较 $a[i]$ 和 $a[j]$，选择更小的放入数组 $b$ ，并移动其指针向下一位置.
    • 重复上一步直到某指针超出数组末尾.
    • 将子数组剩下的所有元素放入数组 $b$，再将数组 $b$ 拷贝到数组 $a$.

时间复杂度：$O(n\log{n})$.

void msort(int l, int r) {
    if (l == r) return;
    int m = (l + r) / 2;
    msort(l, m);
    msort(m + 1, r);
    int i = l, j = m + 1, k = l;
    while (i <= m && j <= r) {
        if (a[i] <= a[j])
            b[k ++] = a[i ++];
        else
            b[k ++] = a[j ++];
    }
    while (i <= m) b[k ++] = a[i ++];
    while (j <= n) b[k ++] = a[j ++];
    for (i = l; i <= r; i ++)
        a[i] = b[i];
}

猴子排序 #

随机交换两个元素，直到排完序.

平均时间复杂度：$O(n\cdot n!)$.

最好时间复杂度：$O(n)$.

最坏时间复杂度：$O(\infty)$.

srand(unsigned(time(0)));
while (true) {
    swap(a[rand() % n + 1], a[rand() % n + 1]);
    bool solve = true;
    for (int i = 2; i <= n; i ++)
        if (a[i] < a[i - 1])
            solve = false;
    if (solve) break;
}

逆序对数 #

若 $i<j$ 且 $a[i]>a[j]$，则 $(a[i],a[j])$ 是一组逆序对.

在 归并排序 的第 3 步：合并两个有序数组时，若出现 $a[i]>a[j]$ 的情况，由 $i<j$ 可知 $a[i\sim m]$ 和 $a[j]$ 构成了 $m-i+1$ 个逆序对，便可以统计到答案中.

void msort(int l,int r){
	if(l == r) return;
	int m = (l + r) / 2;
	msort(l, m);
	msort(m + 1, r);
	int i = l, j = m + 1, k = l;
	while (i <= m && j <= r) {
		if(a[i] <= a[j])
            b[k ++] = a[i ++];
		else {
            b[k ++] = a[j ++];
            ans += m - i + 1;   // 统计逆序对
        }
    }
	while (i <= m) b[k ++] = a[i ++];
	while (j <= r) b[k ++] = a[j ++];
	for (i = l; i <= r; i ++)
        a[i] = b[i]; 
}

稳定性 #

若在原数组中，任意相同元素在排序前后的相对位置不变，则此排序是稳定的.

稳定排序不会破坏相同元素的原顺序. 例如对于结构体 Student：

struct Student {
    int score;
    int id;
}

现给出已按 id 排序的 Student 数组，要求按 score 再排序. 稳定排序能保证所有 score 相同的 Student 仍按照 id 排序.

算法 是否稳定 算法 是否稳定
选择排序 $\times$ 快速排序 $\times$
冒泡排序 $\sqrt{}$ 归并排序 $\sqrt{}$
插入排序 $\sqrt{}$ 猴子排序 $\times$
记数排序 $\sqrt{}$