问题标题: 一种更快的排序方式（我自己想的）

洛谷

吴庞茂旭在2022-01-22 20:59:28追加了内容

/*
NAME:TreeSort 
NODE/TIPS:
name:TreeSort/FasterSort
introduc:
一种基于二叉树和中序遍历特**的排序，通过插入数字到二叉树并对二叉树进行中序遍历的方法巧妙
地得出数列的排序
implementation method:
一、先钦定一个树根；
二、对于插入的一个数x：
	1. x<树根，将x放入树根的左儿子中，若左儿子已经有过数字了，则将左儿子作为树根重复二； 
	2. x>树根，将x放入树根的右儿子中，若右儿子已经有过数字了，则将右儿子作为树根重复二；
	3. x=树根，去重，直接结束
三、通过中序遍历得出排序后的序列
advantage：
1. 好理解；
2. 时间稍快（大约为O(nk)，k≈2）
3. 不需要桶就可以在排序中去重，在数字较大而桶装不下而你又不想用map时可以使用
4. 基于插入排序而来的排序，但比插入排序快、简单，可以作为新手熟悉插入排序的引导 
5. 代码量其实不大（约40行） 
Time complexity (approximate):
经过多次测试，达到了O(nk)(k≈2)的优秀时间复杂度，在排序中属于佼佼者，如果不算外层的n次对
数字的提取，时间复杂的一定比快速排序快。
improvement：
FasterSortPlus，时间复杂度实际上也是O(nk)，是把二叉树变成了一维数组，但没有去重的功能了
，但是尤其是对于有序数组更加迅速，仅需要O(n)的时间复杂度！ 
*/
//std
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#include "windows.h"
#define int long long 
using namespace std;
const int MAXN=105;
const int INF=0x3f3f3f3f3f3f3f3f;
//排序树的定义 
int l[MAXN],r[MAXN];//左儿子和右儿子
int d[MAXN];//对应数值 
int tot=1;//数放到哪一个位置了 
void tree_push(int ,int );//将x放入排序树
void out(int idx,int a[],int &n);//从排序树中导出中序遍历到a[]
void check();//**排序是否正确
//基本定义
int n,m,a[MAXN];
int b[MAXN]; 
signed main(){
	srand(time(NULL));
	treesort:
	n=rand()%48+2;
	cout<<n<<endl;
	for(int i=1;i<=n;i++){
		a[i]=rand()%100;
		cout<<a[i]<<" ";
	}
	cout<<endl;
	//排序开始
	//初始化部分
	tot=1,m=0;memset(b,0,sizeof(b));memset(d,0,sizeof(d));//多次测试，必须的 
	memset(l,0x3f,sizeof(l));memset(r,0x3f,sizeof(r));//随便赋一个序列中没有的值就行了
	//排序 
	d[1]=a[1];//这一步貌似可以优化，但似乎优化了会占时间复杂度 
	for(int i=2;i<=n;i++){
		tree_push(1,a[i]);
	} 
	//导出排序树
	out(1,b,m);
	for(int i=1;i<=m;i++){
		cout<<b[i]<<" ";
	}
	cout<<endl;
	check();
	Sleep(10000);
	system("cls");
	goto treesort;
	return 0;
}
//函数实现 
void tree_push(int idx,int x){//将x放入排序树
	if(x==d[idx]){//去重
		return ; 
	}
	if(x<d[idx]){//不超过当前端点 
		if(l[idx]==INF){//当前端点左儿子是空的
			l[idx]=++tot;//指向当前数的位置
			d[tot]=x;//放置
			return ;//结束 
		} else{//当前端点左儿子不是空的
			tree_push(l[idx],x);//继续向下放置 
		}
	} else{//超过当前端点
		if(r[idx]==INF){//当前端点右儿子是空的
			r[idx]=++tot;//指向当前数的位置
			d[tot]=x;//放置
			return ;//结束 
		} else{//当前端点右儿子不是空的
			tree_push(r[idx],x);//继续向下放置 
		}
	}
}
void out(int idx,int a[],int &n){//从排序树中导出中序遍历到a[]
	if(idx==INF)return ;
	out(l[idx],a,n);//继续向左儿子遍历 
	a[++n]=d[idx];//导出该点
	out(r[idx],a,n);//继续向右儿子遍历 
}
void check(){//**排序是否正确
	for(int i=1;i<=m;i++){
		for(int j=i+1;j<=m;j++){
			if(b[i]>b[j]){//错误
				puts("Error!");
				exit(114514); 
			}
		}
	}
}