这个嘛。。。
接着

上次的帖子{:target=”_blank”}

上次好像还没讲完。。。
担心这个帖子承受不了（太长了。。。）

2022.2.14 批注：写完A+B题解回过头来看上次的那片十大排序算法感觉好短。。。。。。

所以就此结束。。。
现在继续！

还记得这个吗？从这里开始回顾吧！

稳定的排序

鸡尾酒排序（cocktail sort）— $O(n^2)$
原地归并排序— $O(n log_2 n)$如果使用最佳的现在版本
二叉排序树排序（binary tree sort）— $O(n log n)$期望时间；$O(n^2)$最坏时间；需要$O(n)$额外空间
鸽巢排序（pigeonhole sort）— $O(n+k)$；需要$O(k)$额外空间
基数排序（radix sort）— $O(n \times k)$；需要$O(n)$额外空间
侏儒排序（gnome sort）— $O(n^2)$
图书馆排序（library sort）— $O(n log_2 n)$期望时间；$O(n^2)$最坏时间；需要$(1+ε)n$额外空间
块排序（block sort）— $O(n log_2 n)$

不稳定的排序

Clover排序算法（Clover sort）— $O(n)$期望时间，$O(n^2)$最坏情况
梳排序— $O(n log n)$
平滑排序（smooth sort）— $O(n log_2 n)$
内省排序（introsort）— $O(n log_2 n)$
耐心排序（patience sort）— $O(n log_2 n + k)$最坏情况时间，需要额外的$O(n + k)$空间，也需要找到最长的递增子序列（longest increasing subsequence）

不实用的排序

(奇葩的排序)

猴子Bogo排序 — $O(n × n!)$，最坏的情况下期望时间为无穷，不过最好时间复杂度为$O(1)$。
Stupid排序 — $O(n^3)$;递归版本需要$O(n^2)$额外存储器
珠排序（bead sort）— $O(n)$ or $O(\sqrt n)$,但需要特别的硬件
煎饼排序 — $O(n)$,但需要特别的硬件
臭皮匠排序（stooge sort）算法简单，但需要约$O(n^{2.7})$的时间

我在上次的帖子的评论区发的：
有时间我会把下面这些排序算法其中一部分的代码
新创一个帖
放到上面
以免这个帖被挤爆。。。
当然就是这个帖子啦~~

。。。废话说了那么多。。。

也该切入正题了。。。

鸡尾酒排序

鸡尾酒排序是冒泡排序的优化版，又叫“快乐小时排序”（啥意思，完全不理解为啥取这个名字）。
在下面这种特殊数据中会体现出它的优势：

2 3 4 5 6 7 8 1
              ^

get到重点了吗？
从数据中可以发现：2~8都是排好序的，只有一个1在最后面
来看看冒泡排序的做法：

排序前：2 3 4 5 6 7 8 1
第一轮：2 3 4 5 6 7 1 8
第二轮：2 3 4 5 6 1 7 8
第三轮：2 3 4 5 1 6 7 8
第四轮：2 3 4 1 5 6 7 8
第五轮：2 3 1 4 5 6 7 8
第六轮：2 1 3 4 5 6 7 8
第七轮：1 2 3 4 5 6 7 8
第八轮：1 2 3 4 5 6 7 8 （没有数据交换，排序成功）

这个数据用冒泡排序法经过了八轮。
来试试鸡尾酒排序吧！
鸡尾酒排序：
如果现在正在进行第奇数轮，就从前往后遍历
如果现在正在进行第偶数轮，就从后往前遍历

排序前：2 3 4 5 6 7 8 1
第一轮：2 3 4 5 6 7 1 8
第二轮：1 2 3 4 5 6 7 8     ！！！
第三轮：1 2 3 4 5 6 7 8 （没有交换数据，排序成功）

天哪！鸡尾酒排序只用了三轮就解决了！
来看看代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int main() {
    scanf("%d", &n);
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    int cnt = 0;
    while (1) {
        int f = 0; cnt++;
        if(cnt & 1)
            for (int i = 1;i < n; i++) if(a[i] > a[i + 1]) swap(a[i], a[i + 1]), f = 1;
        else
            for (int i = n;i > 1; i--) if(a[i] < a[i - 1]) swap(a[i], a[i - 1]), f = 1;
        if(!f) break;
    }
    for (int i = 1;i <= n; i++) printf("%d ", a[i]); puts("");
    return 0;
}

二叉排序树排序

排序方法：

puts("二叉排序树(Binary Sort Tree)，又称二叉查找树(Binary Search Tree)。");
puts("对于每一个节点：");
puts("如果左子树不为空，则左子树上所有节点的值均小于它的值。");
puts("如果右子树不为空，则右子树上所有节点的值均大于它的值。");
puts("每次在二叉排序树中插入数值，最后输出中序遍历求出排序结果。");

不系很了解二叉排序树的童鞋们可以自己上网查找O~

#include<bits/stdc++.h>
#define LL long long
#define INF 0x7FFFFFFF
using namespace std;
const int N = 1e8 + 10;
int n, idx, rt;
int a[N], t[N];
int ch[N][2];
void insert(int &x, int val) {
    if (!x) {
        x = ++ idx;
        t[x] = val;
        return;
    }
    else {
        if(val < t[x]) insert(ch[x][0], val);
        else insert(ch[x][1], val);
    }
}
void dfs(int x) { //中序遍历二叉排序树
    if(!x) return;
    dfs(ch[x][0]);
    printf("%d ", t[x]); //输出
    dfs(ch[x][1]);
}
int main() {
    scanf("%d", &n);
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1;i <= n; i++) insert(rt, a[i]);
    dfs(rt);
    puts("");
    return 0;
}

侏儒排序

有一个侏儒对花盆进行排序。
他每次只关注自己在的位置上的花盆和往后一个位置的花盆
如果这两个花盆的顺序是正确的，那么他就往前走一个位置。
否则把这两个花盆交换，往后走一个位置。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int main() {
    scanf("%d", &n);
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    int s = 1;
    while(s <= n) {
        if(a[s - 1] <= a[s] || s == 0) s++;
        else swap(a[s], a[s - 1]), s--;
    }
    for (int i = 1;i <= n; i++) printf("%d ", a[i]); puts("");
    return 0;
} 

非常qi pa奇葩的猴子排序

。。。
这是什么鬼东东。。。
明显用来折磨人的
不TLE才怪。。。
定理：给一只猴子一个键盘，在无限长的时间里，这只猴子肯定能敲出指定的文本，如《莎士比亚全集》。
很奇葩啊。。。
猴子排序就是。。。每次把数组打乱，然后检查数组是否有序。。。

这这这过分了。。。

我们来康康猴子排序的特奇葩代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int check() {
    for (int i = 1;i < n; i++) if(a[i] > a[i + 1]) return 0;
    return 1;
}
int main() {
    scanf("%d", &n);
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    while (1) {
        random_shuffle(a + 1, a + 1 + n);   //随机打乱数组的系统函数 
        if(check()) break;
    }
    for (int i = 1;i <= n; i++) printf("%d ", a[i]); puts("");
    return 0;
}