洛谷 P1177 【模板】快速排序【13种排序模版】

时间:2022-09-10 03:43:47

P1177 【模板】快速排序

题目描述

利用快速排序算法将读入的N个数从小到大排序后输出。

快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料,掌握后独立完成。(C++选手请不要试图使用STL,虽然你可以使用sort一遍过,但是你并没有掌握快速排序算法的精髓。)

输入输出格式

输入格式:

输入文件sort.in的第1行为一个正整数N,第2行包含N个空格隔开的正整数a[i],为你需要进行排序的数,数据保证了A[i]不超过1000000000。

输出格式:

输出文件sort.out将给定的N个数从小到大输出,数之间空格隔开,行末换行且无空格。

输入输出样例

输入样例#1:
5
4 2 4 5 1
输出样例#1:
1 2 4 4 5

说明

对于20%的数据,有N≤1000;

对于100%的数据,有N≤100000。

题目链接:https://www.luogu.org/problem/show?pid=1177

下面给出几种排序方法:

1.松式基排

所谓普通基排,就是以65536为底,用位运算,把一个数拆成两部分,要循环两遍

松式基排,就是以256为底,用位运算把一个数拆成四部分,要循环四遍

为什么松式基排在WC的时候会更快呢,因为这样的话cnt数组刚好能装进L1高速缓存

下面给出如下代码:

 #include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = ;
const int BIT = ;
const int U = ;
int n, a[MAXN];
inline int getd( int x, int d ) {
return (x>>(d*BIT))&(U-);
}
int cnt[U], b[MAXN];
void radix_sort() {
int *x = a, *y = b;
for( int d = ; d < ; ++d ) {
for( int i = ; i < U; ++i ) cnt[i] = ;
for( int i = ; i < n; ++i ) ++cnt[getd(x[i],d)];
for( int i = ; i < U; ++i ) cnt[i] += cnt[i-];
for( int i = n-; i >= ; --i ) y[--cnt[getd(x[i],d)]] = x[i];
swap(x,y);
}
for( int i = ; i < n; ++i ) printf( "%d ", x[i] );
}
int main() {
scanf( "%d", &n );
for( int i = ; i < n; ++i ) scanf( "%d", a+i );
radix_sort();
return ;
}

2.归并排序

时间复杂度:O(nlogn)

注意:

1.其他排序算法的空间复杂度是O(1),而归并排序的空间复杂度很大,为O(n)。

2.下面的end是“末尾索引+1”,即数列末尾要留一个空位。

下面给出如下代码:

 #include<iostream>
using namespace std;
int a[];
int temp[];
void merge_sort(int *a,int start,int end)
{
if(start+>=end) //回渊
return;
//int temp[start-end+5];
int mid=start+(end-start)/; //划分阶段
int i=start,j=mid,count=start;
merge_sort(a,start,mid);
merge_sort(a,mid,end);
while(i<mid||j<end) //合并解
{
if(j>=end||(i<mid&&a[i]<=a[j]))
{
temp[count++]=a[i++];
}
else
temp[count++]=a[j++];
}
//int x=0;
for(int v=start;v<end;v++)
{
a[v]=temp[v];
}
}
int main()
{
int n;
cin>>n;
for(int i=;i<n;i++)
{
cin>>a[i];
}
merge_sort(a,,n);
for(int i=;i<n;i++)
{
cout<<a[i]<<' ';
}
return ;
}

3.快速排序(优化读入读出)

下面给出如下代码:

 #include <cstdio>
#include <iostream>
using namespace std;
int a[];
int read_int() //读入优化
{
int x,f=; //f表示符号,x表示数值
char ch;
while (ch=getchar(),ch<||ch>) //如果ch不是数字
if (ch=='-') f=-f; //如果是符号就改变符号
x=ch-; //首位数字
while (ch=getchar(),ch>=&&ch<=) //接下来的每位数字
x=x*+ch-; //将数字添加进x内
return x*f; //返回数值
}
void write_int(int x)
{
if (x==) //判断0的情况
{
putchar('');
return;
}
int num=;
char c[]; //然而我刚开始打的是10,然后发现输出10位数乱码了
while (x) //x!=0
c[++num]=x%+,x/=; //保存每一位
while (num) //如果未输出完
putchar(c[num--]); //输出
}
int sort(int l,int r) //快排,不用多说了吧
{
int i,j,x;
x=a[(l+r)>>]; //基准
i=l;
j=r;
do
{
while (a[i]<x) ++i;
while (a[j]>x) --j; //跳过排序完毕的元素
if (i<=j)
{
a[]=a[i];
a[i]=a[j];
a[j]=a[];
++i;
--j; //交换
}
}
while (i<=j);
if (l<j) sort(l,j);
if (i<r) sort(i,r); //排序左右子序列
}
int main()
{
int n,i;
n=read_int();
for (i=;i<=n;i++)
a[i]=read_int(); //快读的正确打开方式
sort(,n);
for (i=;i<n;i++)
{
write_int(a[i]);
putchar(' '); //输出的正确打开方式
}
write_int(a[n]);
putchar('\n'); //强迫症...
return ;
}

4.利用stl实现堆排序,不是优先队列,比优先队列快上不少,而且容易记

下面给出如下代码:

 #include <cstdio>
#include <algorithm>
#include <queue>//头文件
using namespace std;
const int maxx = + ;
int Heap[maxx];
int main()
{
int n,num = ,x;
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&x),Heap[++num]=x,push_heap(Heap+,Heap+num+,greater<int>());
for(int i=;i<=n;i++)
printf("%d ",Heap[]),pop_heap(Heap+,Heap+num+,greater<int>()),num--;//这几步是关键
return ;
}//代码比手搓堆短很多,而且时间差不多

5.朴素的堆排模板类

下面给出如下代码:

 #include <bits/stdc++.h>
using namespace std;
template<typename T> //定义一个交换模板
void change(T& a,T& b)
{
T t;
t=a;a=b;b=t;
}
template<typename T> //定义一个模板类
class Heap{
T data[]; //存储数据 void ify(int i); //维护堆
Heap(int); //构造函数
~Heap(); //析构函数
void build(); //建堆
void heapsort(); //堆排序
istream& scan(istream&); //读入
ostream& print(ostream&); //输出
};
template<typename T>
Heap<T>::Heap(int n_):n(n_)
{
}
template<typename T>
Heap<T>::~Heap()
{
}
template<typename T>
void Heap<T>::ify(int i)
{
int l=i<<;
int r=(i<<)+;
int m;
if (l<=size&&data[l]>data[i]) m=l;
else m=i;
if (r<=size&&data[r]>data[m]) m=r;
if (m!=i)
{
change(data[m],data[i]); //找到最大数后交换并维护子树
ify(m);
}
}
template<typename T>
void Heap<T>::build()
{
int i;
size=n;
for (i=n/;i>;i--) //对每个非叶子节点维护一次
ify(i);
}
template<typename T>
void Heap<T>::heapsort()
{
build();
for (int i=n;i>;i--)
{
change(data[],data[i]); //将最大数扔到最后
--size;
ify(); //维护
}
}
template<typename T>
istream& Heap<T>::scan(istream& is) //读入
{
for (int i=;i<=n;i++)
is>>data[i];
return is;
}
template<typename T>
ostream& Heap<T>::print(ostream& os) //输出
{
for (int i=;i<n;i++)
os<<data[i]<<' ';
os<<data[n];
return os;
}
template<typename T>
istream& operator>>(istream& is,Heap<T>& a) //重载运算符
{
return a.scan(is);
}
template<typename T>
ostream& operator<<(ostream& os,Heap<T>& a) //同上
{
return a.print(os);
}
int main()
{
int n;
cin>>n;
Heap<int> a(n);
cin>>a;
a.heapsort();
cout<<a<<endl;
}

6.优先队列priority_queue

下面给出如下代码:

 #include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int main(){
priority_queue<int,vector<int>,greater<int> > q;
int n,x;
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&x);
q.push(x);
}
for(int i=;i<=n;i++){
x=q.top();
printf("%d ",x);
q.pop();
}
return ;
}

7.用一个红黑树来实现

下面给出如下代码:

 #include <cstdlib>
#include <iostream>
#include <set>
#include <string>
using namespace std;
int main(int argc, char *argv[])
{
multiset<int>sort;//新建一个红黑树
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
int a;
cin>>a;
sort.insert(a);//将数据插入红黑树
}
set<int>::iterator it;
for(it=sort.begin();it!=sort.end();it++)
cout << *it<<' ';//遍历输出红黑树,即排序结果
cout<< endl;
return ;
}

8.排序二叉树

有一种很好的办法是用排序二叉树。。。建好树后中序遍历输出。。。就好了。

不过二叉排序树有退化成链的可能,所以可以用splay或是treap甚至AVL以及红黑树来排序。。。

伸展树(splay)的写法:

 #include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define xh(a,b,c)for(int a=(b);a<=(c);a++)
#define dxh(a,b,c)for(int a=(b);a>=(c);a--)
#define hy(a)memset(a,0,sizeof(a))
using namespace std;
void qin(int &x){//快速读入
int base=,num;
char c=getchar();
while(!(c=='-'||c>=''&&c<=''||c==EOF))c=getchar();
if(c==EOF)exit();
if(c=='-')base=-,c=getchar();
num=c-'';
c=getchar();
while(c>=''&&c<=''){
num*=;
num+=c-'';
c=getchar();
}
x=num*base;
}
char integ[];
void qout(int x){//快速输出
if(x<)putchar('-'),x=-x;
int len=;
do{
integ[len++]=x%+'';
x/=;
}while(x);
while(len--){
putchar(integ[len]);
}
}
struct jd{//静态splay
int x;
int l,r,h;
};
const int N=;
jd bst[N];
int root,n;//root表示根节点的编号
void lj(int u,int d,int fx){
if(fx==)bst[u].r=d;
else bst[u].l=d;
bst[d].h=u;
}
void zig(int x){//左旋
int b1=bst[x].l,b2=bst[x].r,h=bst[x].h,b3=bst[h].r;
root=x;
bst[x].h=;
lj(x,h,);
lj(x,b1,-);
lj(h,b2,-);
lj(h,b3,);
}
void zag(int x){//右旋
int b1=bst[x].l,b2=bst[x].r,h=bst[x].h,b3=bst[h].l;
root=x;
bst[x].h=;
lj(x,h,-);
lj(x,b2,);
lj(h,b3,-);
lj(h,b1,);
}
void zigzig(int x){//略。。。反正是向上调
int b1=bst[x].l,
b2=bst[x].r,
h=bst[x].h,
b3=bst[h].r,
hh=bst[h].h,
b4=bst[hh].r,
hhh=bst[hh].h;
if(hhh==){
root=x;
bst[x].h=;
}else if(bst[hhh].l==hh)lj(hhh,x,-);
else lj(hhh,x,);
lj(x,h,);
lj(h,hh,);
lj(x,b1,-);
lj(h,b2,-);
lj(hh,b3,-);
lj(hh,b4,);
}
void zagzag(int x){//略。。。反正是向上调*2
int h=bst[x].h,
hh=bst[h].h,
hhh=bst[hh].h,
b1=bst[hh].l,
b2=bst[h].l,
b3=bst[x].l,
b4=bst[x].r;
if(hhh==){
root=x;
bst[x].h=;
}else if(bst[hhh].l==hh)lj(hhh,x,-);
else lj(hhh,x,);
lj(x,h,-);
lj(h,hh,-);
lj(x,b4,);
lj(h,b3,);
lj(hh,b1,-);
lj(hh,b2,);
}
void zigzag(int x){//略。。。反正是向上调*3
int b1=bst[x].l,
b2=bst[x].r,
h=bst[x].h,
b3=bst[h].r,
hh=bst[h].h,
b4=bst[hh].l,
hhh=bst[hh].h;
if(hhh==){
root=x;
bst[x].h=;
}else if(bst[hhh].l==hh)lj(hhh,x,-);
else lj(hhh,x,);
lj(x,h,);
lj(x,hh,-);
lj(hh,b1,);
lj(h,b2,-);
lj(h,b3,);
lj(hh,b4,-);
}
void zagzig(int x){////略。。。反正是向上调
int b1=bst[x].l,
b2=bst[x].r,
h=bst[x].h,
b3=bst[h].l,
hh=bst[h].h,
b4=bst[hh].r,
hhh=bst[hh].h;
if(hhh==){
root=x;
bst[x].h=;
}else if(bst[hhh].l==hh)lj(hhh,x,-);
else lj(hhh,x,);
lj(x,h,-);
lj(x,hh,);
lj(h,b1,);
lj(hh,b2,-);
lj(h,b3,-);
lj(hh,b4,);
}
void splay(int x){//伸展操作(把x节点调到根节点)
while(bst[x].h){
if(bst[bst[x].h].h==){
if(bst[bst[x].h].l==x)zig(x);
else zag(x);
}
else{
int h=bst[x].h,hh=bst[h].h;
if(bst[h].l==x){
if(bst[hh].l==h)zigzig(x);
else zigzag(x);
}
else{
if(bst[hh].l==h)zagzig(x);
else zagzag(x);
}
}
}
}
void ins(int r,int i){//插入
if(bst[i].x<bst[r].x){
if(bst[r].l==){
lj(r,i,-);
splay(i);//每当插入一个数后都要把这个数调到根节点
}
else ins(bst[r].l,i);
}
else{
if(bst[r].r==){
lj(r,i,);
splay(i);;//每当插入一个数后都要把这个数调到根节点
}
else ins(bst[r].r,i);
}
}
void bl(int x){//中序遍历
if(x==)return;
bl(bst[x].l);
qout(bst[x].x);
putchar(' ');
bl(bst[x].r);
}
int main(){
qin(n);
qin(bst[].x);
root=;
xh(i,,n){
qin(bst[i].x);
ins(root,i);
}
bl(root);
putchar('\n');
return ;
}

9.可并堆

 #include<bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
struct tree{
tree *l,*r,*f;
int v,sl,sr;
tree(){
l=r=f=NULL;
v=sl=sr=;
}
}*root,*k,*d;
tree* merge(tree *x,tree *y){//合并
if(x==NULL)return y;
if(y==NULL)return x;
if(x->v>y->v)
swap(x,y);
x->r=merge(x->r,y);
x->sr++;
if((x->sl)<(x->sr)){
swap(x->l,x->r);
swap(x->sl,x->sr);
}
return x;
}
void insert(int x){//插入
k=new tree;
k->v=x;
if(root==NULL)root=k;
else root=merge(root,k);
}
int top(){//顶端元素
if(root!=NULL)return root->v;
return -;
}
void pop(){//弹出
if(root!=NULL)root=merge(root->l,root->r);//合并左右子数
}
int main(){
root=NULL;
int n;
scanf("%d",&n);
fr(i,,n){
int a;
scanf("%d",&a);
insert(a);
}
fr(i,,n){
printf("%d ",top());
pop();
}
return ;
}

10.希尔排序

 #include <cstdio>
using namespace std;
int i,j,k,n,m,x,y,t,d,a[];
void ShellInsert(int* pDataArray, int d, int iDataNum){
for (int i = d; i < iDataNum; i += ){
int j = i - d;
int temp = pDataArray[i];
while (j >= && pDataArray[j] > temp){pDataArray[j+d] = pDataArray[j];j -= d;}
if (j != i - d)pDataArray[j+d] = temp;
}
}
void ShellSort(int* pDataArray, int iDataNum){
int d = iDataNum / ;
while(d >= ){ShellInsert(pDataArray, d, iDataNum);d = d / ;}
}
int main(){
scanf("%d",&n);if (n==) return ;
for (i=;i<n;i++) scanf("%d",&a[i]);
ShellSort(a,n);
for (i=;i<n;i++) printf("%d ",a[i]);
return ;
}

11.用动态插入堆排序

 #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
ll heap[];
#define lson(x) x<<1
#define rson(x) x<<1|1
#define fa(x) x>>1
ll N;
struct Heap{
int size;
Heap(){
size=;
}
void pushDown(int i){ //从顶部向下推至合适位置
int l,r,k;
while(lson(i)<=size){
l=lson(i);r=rson(i);k=i;
if(heap[k]>heap[l]){
k=l;
}
if(r<=size && heap[k]>heap[r]){
k=r;
}
if(k!=i){
swap(heap[i],heap[k]);
i=k;
}else break;
}
}
void pushUp(int i){ // 从底部推至合适位置
while(fa(i)>=){
if(heap[fa(i)]>heap[i]){
swap(heap[fa(i)],heap[i]);
i=fa(i);
}else break;
}
}
void pop(){ //删除堆顶元素
heap[]=heap[size--];
pushDown();
}
ll top(){
return heap[];
}
void insert(int x){ //插入一个新元素到堆底
heap[++size]=x;
pushUp(size);
}
}H;
inline ll read(){
ll a=;
char ch=getchar();
bool flag = false;
while(ch>'' || ch<'' || ch=='-'){
if(ch=='-') flag=true;
ch=getchar();
}
while(ch>='' && ch<=''){
a=a*+ch-'';
ch=getchar();
}
if(flag) a=-a;
return a;
}
int main(){
N=read();ll v;
for(int i=;i<=N;++i){
v=read();H.insert(v);
}
while(H.size){
printf("%lld ",H.top());
H.pop();
}
return ;
}

12.基数排序(O(n))

 #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#define Z 1000000+10
#define K 10+10//位数设为20 , 11 也可以
#define FORZ(a,b,c) for(a=b;a<=c;a++)
#define FORJ(a,b,c) for(a=b;a>=c;a--)
#define M0(a) memset(a,0,sizeof(a))
using namespace std;
int a[Z];
int b[Z];
int cnt[K];
int getmax(const int n)
{
int i,p=,sum=;
FORZ(i,,n)
{
while(a[i]>=sum)
{
sum*=;
p++;
}
}
return p;
}
void JS_sort(const int n)
{
int i,j,k,l,o,p,u;
int wei=getmax(n);
int ord=;
FORZ(k,,wei)
{
M0(cnt);
FORZ(i,,n)
{
u=a[i]/ord%;
cnt[u]++;
}
FORZ(i,,)
{
cnt[i]+=cnt[i-];
}
//滚包裹
FORJ(i,n,)
{
u=a[i]/ord%;
b[cnt[u]]=a[i];
cnt[u]--;
}
FORZ(i,,n)
{
a[i]=b[i];
}
ord*=;
}
}
int main()
{
int n,i,j,k,l,u,o,p;
scanf("%d",&n);
FORZ(i,,n)scanf("%d",&a[i]);
JS_sort(n);
FORZ(i,,n)printf("%d ",a[i]);
}

13.最不值得一提的sort(不建议,毕竟这是一道模版题)

 #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[];
int main()
{
int n;
cin>>n;
for(int i=;i<=n;i++)
cin>>a[i];
sort(a+,a++n);
for(int i=;i<n;i++)
cout<<a[i]<<" ";
cout<<a[n]<<endl;
return ;
}