前言

排序演算法在題目中經常需要用到，在程式中，我們一般打的是快排，歸并，堆排等高效率排序，更有甚者會直接用sort排序，而今天，我要介紹一種奇特的排序方法——Monkey King 排序，我相信接下來的內容會對你有一定幫助，

演算法簡介

Monkey King 排序也稱吉吉國王排序，是一種高效率 排序演算法，其發明者是L.E.M.T蒟蒻，于2021年1月28日在機房劃水時發明（其實是聽取了他人的瞎搞口胡再加以優化），本演算法學習門檻極低，適于初學者學習，

思想

模擬猴子（bushi）
我們設想取兩個變數 x x x 和 y y y ,表示我們可能要交換的兩個數， s w a p ( a [ x ] , a [ y ] ) swap(a[x],a[y]) swap(a[x],a[y])，交換之后 O ( n ) O(n) O(n)掃一遍判斷當前序列是否合法即可，

這時可能有人會問：那時間復雜度不會很高嗎？

確實！

所以下面便是吉吉國王排序的核心部分了！

也是降低時間復雜度的關鍵部分！

我們可以試想如何減少列舉 x x x y y y 的時間，不難想到我們可以模仿猴子隨機選擇兩個數直接用這兩個數交換，（yi本正經）

CODE如下

//This is monkeykingsort ! ! !
#include<bits/stdc++.h>
using namespace std;
int n,a[1000005],bj;
int main() {
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=2;i<=n;i++) if (a[i]<a[i-1]) {bj=1; break;}
	srand(time(NULL));
	while (bj) {
		int x=rand()%n+1,y=rand()%n+1;
		swap(a[x],a[y]),bj=0;
		for (int i=2;i<=n;i++) if (a[i]<a[i-1]) {bj=1; break;}
	}
	for (int i=1;i<=n;i++) printf("%d\n",a[i]);
}

但是如果臉黑怎么辦呢？？？
那么很可惜，你不是真正的吉吉國王，但是我們可以通過優化把你變成真正的吉吉國王（？？？）

優化

當我們列舉兩個數時，我們可以想一下什么情況下我們才可以交換，

很顯然，當 x < y x<y x<y 且 a [ x ] > a [ y ] a[x]>a[y] a[x]>a[y] 的情況我們才能交換（從小到大排）

所以優化后的代碼如下：

//This is monkeykingsort ! ! !
#include<bits/stdc++.h>
using namespace std;
int n,a[1000005],bj;
int main() {
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=2;i<=n;i++) if (a[i]<a[i-1]) {bj=1; break;}
	srand(time(NULL));
	while (bj) {
		int x=rand()%n+1,y=rand()%n+1;
		if (x>y) swap(x,y);
		if (a[x]>a[y]) {
			swap(a[x],a[y]),bj=0;
			for (int i=2;i<=n;i++) if (a[i]<a[i-1]) {bj=1; break;}
		}
	}
	for (int i=1;i<=n;i++) printf("%d\n",a[i]);
}

我覺得還行~~~

時間復雜度

理論 O ( T N ) O(TN) O(TN)（T是交換次數，是“常數”，可以省去） 前提是臉足夠好？？？

所以會退化到 O ( 無 限 ) O(無限) O(無限)？？？

就這樣吧，，，

不會真的有人看到這里吧（逃