排序算法大汇总（包含各种奇葩排序算法）持续更新中

经验分享区
1

常见初级排序

1.冒泡排序

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

思路：从左到右扫一遍，遇到左侧比右侧大的就交换。
时间复杂度： O(n^2) 。
空间复杂度： O(n) 。

2.选择排序

for(int i=2;i<=n;i++){
    int v=i;
    for(int j=i+1;j<=n;j++){
    	if(a[j]<a[v]){
			v=j;
		}
    }
    swap(a[i],a[v]);
}

思路：从左到右扫，找到右边最小的数，与他交换。
时间复杂度： O(n^2) 。
空间复杂度： O(n) 。

3.桶排序

for(int i=1;i<=n;i++){
	cin>>m;
	a[m]++;
}
for(int i=1;i<=1000;i++){
	while(a[i]--){
		cout<<i<<" ";
	}
}

思路：在输入时用map或int []存储每个数出现的次数，再输出。
时间复杂度： O(n+m) 。
空间复杂度： O(m) 。

4.STL标准模板库排序（sort）

sort(a+1,a+n+1);

时间复杂度： O(nlogn) 。
空间复杂度： O(n) 。

较为复杂（其实也没多复杂）的排序

5.快速排序

void qs(int a[],int l,int r){
	if(l<r){
		int i=l,j=r,k=a[l];
		while(i<j){
			while(i<j&&k<=a[j])j--;
			a[i]=a[j];
			while(i<j&&k>=a[i])i++;
			a[j]=a[i];
		}
		a[i]=k;
		qs(a,l,i-1);
		qs(a,i+1,r);
	}
}

思路： 选择第一个元素作为基准值。比基准值高的放在基准值右边，比基准值低的放在基准值左边。在对两边用相同的方法排序。
时间复杂度： 平均 O(nlogn) ，最坏 O(n^2) 。
空间复杂度： O(n) ，辅助空间 O(logn) 。

1 个赞
2

我有一种排序， 时间复杂度 O(1) ,本该在2024年4月31日时获得图灵奖， 可惜那时候我忙着 给西西弗送钱 导致了该排序算法被湮没
现在我决定开源这份代码， 在 O(1) 的复杂度内解决困惑诗人的排序问题
显而易见， 该算法有着一项比较难以发现的缺点， 但是瑕不掩瑜， 虽然该排序只能对 1个元素进行排序

template <typename T>
inline T const& sort(T const& a) 
{ 
    return a;
}

调用方法

T a;
cin >> a;
cout << sort(a);
3

只能对不超过两个数排序，且在有两个数时无法控制正序还是逆序是吧（doge）

4

如果我没记错的话，有一个时间复杂度Ο(n)的排序算法：

for(int i=0;i<n-1;i++){
    if(a[i]>a[i+1]){
        swap(a[i],a[i+1]);
    }
}
for(int i=n-2;i>=0;i--){
    if(a[i]>a[i+1]){
        swap(a[i],a[i+1]);
    }
}
5

不行，给一组数据你。

5
3 7 4 9 2

目前世界上最优秀的排序算法是 Tim\,sort ，时间复杂度最坏情况 O(nlogn) ，空间复杂度 O(n) ，稳定。
空间复杂度优于归并。
还有用map优化的桶排序也能做到类似的复杂度。不过 Tim\,sort 的时间复杂度最好可以达到 O(n) 。