关于排序那些事

排序

顾名思义，排序是对一堆无序数的处理，及一些基础操作，本篇博客对排序的几种方式进行一个整理。

No.1 sort排序

#include<cstdio>
#include<algorithm>
using namespace std;
long long int a[1000005];
int main(){
    long long int n;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)printf("%lld ",a[i]);
    return 0;
}

代码很简便，原理是在三路快速排序与归并排序之间选择速度快的一种方法进行排序，适合在一些排序预处理的题目中，可以省去许多代码
但是，如果待排序数为struct（结构体），请在主函数上，结构体下加上这行代码
升序排序：

bool cmp(结构体名称 x,结构体名称 y){return x.待排序变量名<y.待排序变量名;}

升序排序：

bool cmp(结构体名称 x,结构体名称 y){return x.待排序变量名>y.待排序变量名;}

No.2 桶排序

顾名思义，定义一个桶数组，个人喜欢perper。
原理十分简单，存储一下a[i] 出现次数再依次输出即可

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

桶排的优点在于实现简单，通俗易懂，时间复杂度十分优秀。

No.3 冒泡排序

排序中最为基础的方法，同时敲代码很耗时间！！！

#include<cstdio>
#include<algorithm>
using namespace std;
int a[100005];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n-i;j++){
			if(a[j]>a[j+1]){
				swap(a[j],a[j+1]);
			}
		}
	}
	for(int i=1;i<=n;i++)printf("%d ",a[i]);
	return 0;
}

同样，思路十分简单，再此不做多于赘述。

No.4 快速排序