专栏文章

排序算法

kkevinf
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioud1s4
此快照首次捕获于
2025/12/03 01:17
3 个月前
此快照最后确认于
2025/12/03 01:17
3 个月前
查看原文

排序算法

总览

排序算法

1.选择排序

CPP
#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++){
		int minn=2e9,num=-1;
		for(int j=i;j<=n;j++){
			if(a[j]<minn) num=j;
			minn=min(a[j],minn);

		}
		swap(a[i],a[num]);
	}
	
	for(int i=1;i<=n;i++) printf("%d ",a[i]);
	puts("");
	return 0;
}

2.冒泡排序

CPP
#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++){
		for(int j=1;j<n;j++){
			if(a[j]>a[j+1]) swap(a[j],a[j+1]);
		}
	}
	
	for(int i=1;i<=n;i++) printf("%d ",a[i]);
	puts("");
	return 0;
}
优化#1
CPP
#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++){
		bool flag =false;
		for(int j=1;j<n;j++){
			if(a[j]>a[j+1]){
				swap(a[j],a[j+1]);
				flag=true;
			}
		}
		if(!flag) break;
	} 
	
	for(int i=1;i<=n;i++) printf("%d ",a[i]);
	puts("");
	return 0;
}

3.插入排序

CPP
#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int main(){
	int n;
	scanf("%d",&n);
	
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	int i,j;
	for(i=1;i<=n;i++){
		for(j=0;j<i;j++){
			//找 
			if(a[j]>a[i]){
				break;
			}
		}
		//插入 
		if(j!=i){
			int t=a[i];
			for(int k=i-1;k>=j;k--){
				a[k+1]=a[k];
				
			} 
			a[j]=t;
			
		}
	} 
	
	for(int i=1;i<=n;i++) printf("%d ",a[i]);
	puts("");
	return 0;
}
}

4.桶排序

CPP
#include<bits/stdc++.h>
using namespace std;
int a[1005];
int main(){
	int n;
	scanf("%d",&n);
	
	for(int i=1;i<=n;i++){
		int num;
		scanf("%d",&num);
		a[num]++; 
	}
	for(int i=0;i<=1000;i++){
		for(int j=0;j<a[i];j++)
			printf("%d ",i);
	}
	puts("");
	return 0;
}

5.归并排序

CPP
#include<iostream>
using namespace std;
int a[110],b[110];
int n; 

void merge(int l,int r){
	if( l >= r ) return;
	int mid = (l+r)>>1;
	
	//拆
	merge(l,mid);
	merge(mid+1,r);
	
	//合
	int i=l,j=mid+1,k=0;
	while( i<=mid && j<=r ){
		if( a[i] <= a[j] ) b[++k] = a[i],i++;
		else b[++k] = a[j],j++;
	}
	
	while(i<=mid) b[++k] = a[i],i++;
	while(j<=r) b[++k] = a[j],j++;
	
	for(int i=1;i<=k;i++){
		  a[l+i-1] = b[i];
	}	
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}		
	//归并排序
	merge(1,n);
	
	//输出	
	for(int i=1;i<=n;i++) cout<<a[i]<<" ";

	return 0;
}

6.快速排序

CPP
#include<iostream>
using namespace std;
int a[110],b[110];
int n; 
int partition( int low, int high) {
    int pivot = a[high];
    int i = low - 1;
    for (int j = low; j <= high - 1; j++) {
        if (a[j] < pivot) {
            i++;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[high]);
    return i + 1;
}

void quickSort( int low, int high) {
    if (low < high) {
        int pi = partition( low, high);
        quickSort( low, pi - 1);
        quickSort( pi + 1, high);
    }
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}		
	quickSort(1,n);
	for(int i=1;i<=n;i++) printf("%d ",a[i]);
	return 0;
}

7.计数排序

CPP
#include<bits/stdc++.h>
using namespace std;
int a[100005],b[100005],cnt[100005];

int main(){
	int n,mx=-2e9;
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		cnt[a[i]]++;
		mx=max(mx,a[i]);
	}

    for (int i = 1; i <= mx; ++i) cnt[i] += cnt[i - 1];
    //保证稳定性 
    for (int i = n; i >= 1; --i) b[cnt[a[i]]--] = a[i];
 


	for(int i=1;i<=n;i++) printf("%d ",b[i]);
	return 0;
}

8.基数排序

CPP
#include<bits/stdc++.h>
using namespace std;
int a[100005],b[100005],cnt[100005];
int n,mx=-2e9;
void fun(int res){
	memset(b,0,sizeof(b));
	memset(cnt,0,sizeof(cnt));
	for(int i=1;i<=n;i++){
		cnt[a[i]/res%10]++;
	}
	for(int i=1;i<=9;i++){
		cnt[i]+=cnt[i-1];
	}
	for(int i=n;i>=1;i--){
		b[cnt[a[i]/res%10]--]=a[i];
	}
	for(int i=1;i<=n;i++){
		a[i] =b[i]; 
	} 
}
int main(){
	
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		cnt[a[i]]++;
		mx=max(mx,a[i]);
	}
	for(int res=1;mx/res>0;res*=10){
		fun(res);
	}


	for(int i=1;i<=n;i++) printf("%d ",a[i]);
	return 0;
}

9.堆排序

CPP
#include<bits/stdc++.h>
using namespace std;
int a[100005],b[100005],cnt[100005];
int n;
//调整子树 
void heap_add(int root,int len){
	int mx=root,l=root*2,r=root*2+1;
	//如果左右孩子存在
	if(l<=len&&a[l]>a[mx]) mx=l;
	if(r<=len&&a[r]>a[mx]) mx=r;
	if(mx!=root){
		swap(a[root],a[mx]);
		heap_add(mx,len);
	}
}
void heap_sort(){
	//构建大顶堆
	for(int i=n/2;i>=1;i--){
		heap_add(i,n);
	} 
	for(int i=n;i>1;i--){
		swap(a[1],a[i]);
		heap_add(1,i-1);
	}
}
int main(){
	
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	heap_sort();


	for(int i=1;i<=n;i++) printf("%d ",a[i]);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...