興味深いソートアルゴリズム--Monkey Kingソートの詳細

前言
ソートアルゴリズムはテーマの中でよく使われています.プログラムの中で、私たちは一般的に速いソート、集計、スタックなどの効率的なソートをしています.さらに、sortで直接ソートすることもあります.今日は、奇抜なソート方法--Monkey Kingソートを紹介します.次の内容があなたに役立つと信じています.
アルゴリズムの概要
Monkey Kingソートは吉吉国王ソートとも呼ばれ、高効率ソートアルゴリズムであり、その発明者はL.E.M.Tこんにゃくであり、2021年1月28日に機械室で水を漕ぐ際に発明された(実際には他人のでたらめを聞いて最適化された)、本アルゴリズムの学習の敷居は極めて低く、初学者の学習に適している.
思想
シミュレーションサル(bushi)我々は2つの変数x x xとy y yを想定し,我々が交換する可能性のある2つの数,s w a p(a[x],a[y])swap(a[x],a[y])swap(a[x],a[y])を表し,交換後O(n)O(n)O(n)n)スキャンして現在のシーケンスが合法かどうかを判断すればよい.
その時間は複雑度が高くないのかと聞かれるかもしれません.
確かに!
だから次は吉吉国王のソートの核心部分です!
時間の複雑さを減らすカギとなる部分でもあります!
x x x x y yを列挙する時間をどのように減らすかを考えることができます.サルがランダムに2つの数を選択して直接この2つの数で交換できるとは考えにくい.(yiまじめ)
コードは以下の通り

//This is monkeykingsort ! ! !
#include
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
",a[i]);
}

でも颜が黒くなったらどうする??では残念ながら、あなたは本当の吉吉国王ではありませんが、私たちは最適化を通じてあなたを本当の吉吉国王に変えることができます(??)
最適化
2つの数を列挙すると、どのような状況で交換できるか考えることができます.
xa[y]a[x]>a[y]a[x]>a[y]a[x]>a[y]の場合に交換できることは明らかである(小から大列まで)
最適化されたコードは次のとおりです.

//This is monkeykingsort ! ! !
#include
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
",a[i]);
}

まあまあだと思います~~~
時間の複雑さ
理論O(T N)O(TN)O(TN)O(TN)(Tは交換回数であり、「定数」であり、省ける)前提は顔が十分良いこと??
だからO(無限)O(無限)O(無限)O(無限)??に劣化します.
そうしましょう...
まさか本当に誰かがここを見ているのではないでしょうか(逃げる