[数据结构与算法]最常见的六种排序(选择、冒泡、插入、快排、归并、桶)

同样是排序，有的时间复杂度高，有的时间复杂度低。

1.选择排序 时间复杂度：O(N^2)

超级简单，就先小时候学的数线段，看代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e4+10;
int n,a[N];
void choose_sort(){
	for(int j=1;j<=n;j++){
		for(int i=j+1;i<=n;i++){
			if(a[j]>a[i]){
				swap(a[i],a[j]);
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
	}
	choose_sort();
	for(int i=1;i<=n;i++){
		printf("%d ",a[i]);
	}
	return 0;
}

2.冒泡排序 时间复杂度：O(N^2)?

根据冒泡每两个轻的在上，重的在下思想进行排序，看代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e4+10;
int n,a[N];
void bubble_sort(){
    for(int i=1;i<n;i++){
		bool flag=false;
		for(int j=1;j<=n-i;j++){
			if(a[j]>a[j+1]){
				swap(a[j],a[j+1]);
				flag=true;
			}
		}
		if(!flag) break;
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
	}
	bubble_sort();
	for(int i=1;i<=n;i++){
		printf("%d ",a[i]);
	}
	return 0;
}

3.插入排序 时间复杂度：O(N^2)

?

思想就是插入，看代码：?

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e4+10;
int n,a[N];
void c_sort(){
	for(int i=2;i<=n;i++){
		int j=i;
		int x=a[i];
		while(j>=1&&a[j-1]>x){
			a[j]=a[j-1];
			j--;
		}
		a[j]=x;
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
	c_sort();
	for(int i=1;i<=n;i++){
        printf("%d ",a[i]);
    }
	return 0;
}

4.快速排序 时间复杂度：O(NlogN)

?

思想是双指针排序，看代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e6+10;
int n,a[N];
void q_sort(int l,int r){
	if(l>=r) return;
	int i=l,j=r,top=a[r];
	while(i<j){
		while(a[i]<=top&&i<j) i++;
		a[j]=a[i];
		j--;
		while(a[j]>=top&&i<j) j--;
		a[i]=a[j];
	}
	a[i]=top;
	q_sort(l,i-1);
	q_sort(i+1,r);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	q_sort(1,n);
	for(int i=1;i<=n;i++){
		printf("%d ",a[i]);
	}
	return 0;
}

?5.归并排序 时间复杂度：O(NlogN)

?

先分再合，每合一次都是把两个有序数组合并的过程，看代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5;
int n,a[N];
void together(int al,int ar,int bl,int br){
	int num=0,b[N]={0};
	int i=al,j=bl;
	while(i<=ar&&j<=br){
		if(a[i]<a[j]) b[++num]=a[i++];
		else b[++num]=a[j++]; 
	}
	while(i<=ar) b[++num]=a[i++];
	while(j<=br) b[++num]=a[j++];
	for(int k=1,x=al;k<=num;k++){
		a[x++]=b[k];
	}
}
void gsort(int l,int r){
	if(l==r) return;
	int mid=(l+r)/2;
	gsort(l,mid);
	gsort(mid+1,r);
	together(l,mid,mid+1,r);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	gsort(1,n);
	for(int i=1;i<=n;i++)
		printf("%d ",a[i]);
	return 0;
}

6.桶排序 时间复杂度 O(N)

最快的排序，但空间较大，看代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e7+10;
int n;
bool a[N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		a[x]=1;
	}
	for(int i=0;i<N;i++){
		if(a[i]) printf("%d ",i);
	}
	return 0;
} 

以上是去重，再看一下不去重：

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e7+10;
int n,a[N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		a[x]++;
	}
	for(int i=0;i<N;i++){
		for(int j=1;j<=a[i];j++) printf("%d ",i); 
	}
	return 0;
} 

以上就是所有排序，要牢记！