排序合集模板

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int a[N];
int t[N];
int n;
void bubbleSort(int a[],int n){
    //冒泡排序 ： 
    //时间复杂度 ： O(n^2) 
    //是否稳定 : 是 
	for(int i=n;i>1;i--){
		for(int j=1;j<i;j++){
			if(a[j]>a[j+1]){
				swap(a[j],a[j+1]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	exit(0); 
}
void insertSort(int a[],int n){
    //直接插入排序 ： 
    //时间复杂度 ： O(n^2) 
    //是否稳定  : 是 
	for(int i=2;i<=n;i++){
		for(int j=i;j>1;j--){
			if(a[j]<a[j-1]){
				swap(a[j],a[j-1]);
			}
			else{
				break;
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	exit(0); 
}
void selectSort(int a[],int n){
    //选择排序 ： 
    //时间复杂度 : O(n^2) 
    //是否稳定  : 否 
	for(int i=1;i<=n;i++){
		int ind=i;
		for(int j=i+1;j<=n;j++){
			if(a[ind]>a[j]){
				ind=j;
			}
		}
		swap(a[i],a[ind]);
	}
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	exit(0); 
}
void quickSort(int L,int R){
	//快速排序 ： 
    //时间复杂度 : O(nlogn)---O(n^2)
    //是否稳定  : 否 
    //递推边界 
    if(L>=R){
    	return ;
	}
	//分 
	int i=L;
	int j=R;
	int k=L;
	while(i<j){
		while(a[j]>=a[k]&&i<j){
			j--;
		}
		while(a[i]<=a[k]&&i<j){
			i++;
		}
		swap(a[i],a[j]);
	}
	swap(a[k],a[i]);
	//治 
	quickSort(L,i-1);
	quickSort(i+1,R);
	return ; 
}
void mergeSort(int L,int R){
	//归并排序 ： 
    //时间复杂度 : O(nlogn)
    //是否稳定  : 是
    //递推边界 
    if(L>=R){
    	return;
	} 
	//分 
	int mid=(L+R)/2;
	mergeSort(L,mid);
	mergeSort(mid+1,R);
	int i=L;
	int j=mid+1;
	int ind=0;
	int ans=0; 
	while(i<=mid&&j<=R){
		if(a[i]<a[j]){
			t[++ind]=a[i++];
		}
		else{
			t[++ind]=a[j++];
			//ans+=mid-i+1;
			//逆序对 
		}
	}
	//治 
	while(i<=mid){
		t[++ind]=a[i++];
	}
	while(j<=R){
		t[++ind]=a[j++];
	}
	for(int i=1;i<=ind;i++){
		a[L+i-1]=t[i]; 
	} 
	return ; 
}
void bucketSort(int a[],int n){
	//桶排序 ：
	//时间复杂度 ：O(n)
	//是否稳定 ：是
	for(int i=1;i<=n;i++){
		t[a[i]]++;
	}
	for(int i=1;i<=n;i++){
		while(t[a[i]]!=0){
			cout<<i<<" ";
			t[a[i]]--;
		}
	} 
	exit(0);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	//bubbleSort(a,n);
	//insertSort(a,n);
	//selectSort(a,n);
	//quickSort(1,n);
	//mergeSort(1,n);
	//bucketSort(a,n);
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	return 0;
}