十大排序模板

傷城~ 2022-04-01 09:52 203阅读 0赞

#include<bits/stdc++.h>
    using namespace std;
    void insertsort(int a[],int n){//插入
    	int j;
    	for(int i=2;i<=n;i++){
    		if(a[i]<a[i-1]){
    			a[0]=a[i];
    			for(j=i-1;a[j]>a[0];j--)
    				a[j+1]=a[j];
    			a[j+1]=a[0];
    		}
    	}
    }
    
    void bubsort(int a[],int n){//冒泡
    	for(int i=1;i<n;i++)
    		for(int j=1;j<n-(i-1);j++)
    			if(a[j]>a[j+1])
    				swap(a[j],a[j+1]);
    }
    
    void selectsort(int a[],int n){//选择
    	for(int i=1;i<n;i++){
    		int k=i;
    		for(int j=i+1;j<=n;j++)
    			if(a[j]<a[k])k=j;
    		if(k!=i)swap(a[i],a[k]);
    	}
    }
    
    void quicksort(int a[],int left,int right){//快排
    	if(left>=right)return ;
    	int l=left,r=right,t=a[left];
    	while(l<r){
    		while(l<r&&a[r]>=t)r--;
    		if(l<r)a[l]=a[r];		
    		while(l<r&&a[l]<=t)l++;
    		if(l<r)a[r]=a[l];
    	}	
    	a[l]=t;
    	quicksort(a,left,l-1);
    	quciksort(a,l+1,right);
    }
    
    void merge(int a[],int left,int mid,int right,int tem[]){
    	int i=left,j=mid+1,m=mid,n=right,k=0;
    	while(i<=m&&j<=n){
    		if(a[i]<=a[j])tem[k++]=a[i++];
    		else tem[k++]=a[j++];
    	}
    	while(i<=m)tem[k++]=a[i++];
    	while(j<=n)tem[k++]=a[j++];
    	for(int i=0;i<k;i++)a[left+i]=tem[i];
    }
    void mergesort(int a[],int left,int right,int tem[]){
    	if(left<right){
    		int mid=(left+right)>>1;
    		mergesort(a,left,mid,tem);
    		mergesort(a,mid+1,right,tem);
    		merge(a,left,mid,right,tem);
    	}
    }
    
    void mergesortsolo(int a[],int left,int right){//归并简写
    	if(left>=right)return ;
    	int mid,i,j,p=l,q,len,t[1000];
    	mid=(left+right)>>2;
    	p=l;
    	q=mid+1;
    	j=1;
    	len=right-left+1;
    	mergesortsolo(a,left,mid);
    	mergesortsolo(a,mid+1,right);	
    	for(i=1;i<=len;i++){
    		if(q>right||(a[p]<a[q])&&p<=mid)t[i]=a[p++];
    		else t[i]=a[q++];
    	}
    	for(int i=1;i<=len;i++)a[left+i-1]=t[i];
    }
    //堆排序
    void heapadjust(int a[],int s,int m){//除了a[s]外均满足堆得定义 
    	for(int j=s*2;j<=m;j*=2){
    		if(j+1<=m&&a[j+1]<a[j])//找出孩子中的最小值 
    			j++;
    		if(a[s]<a[j])break;
    		swap(a[s],a[j]);
    		s=j;		//向下调整 
    	}
    }
    void heapsort(int a[],int n){//若是小根堆，得到的是降序；若是大根堆得到的是升序。 
    	for(int j=n/2;j>=1;j--)heapadjust(a,j,n);
    	for(int j=n;j>1;j--){
    		swap(a[j],a[1]);
    		heapadjust(a,1,j-1);		
    	}
    } 
    //基数排序。（根据n位，桶式排序，先个位再十位再百位，，，） 
    
    //