排序算法
本文默认升序（从小到大）排序
1. 入门排序
1.1 选择排序
在后（n-i)个元素中找到一个最小的，放在第i位。
时间复杂度为O(\(n^2\))。
代码实现如下：
for(int i=0;i<n;i++){
int minn=i;
for(int j=i+1;j<n;j++)
if(a[j]<a[minn])minn=a[j];
if(i!=minn) swap(a[i],a[minn]);
}
1.2 冒泡排序
判断相邻两个元素的大小关系，若逆序则交换，比较(n-i)次后即可将第i小的元素放在第i位。
时间复杂度为O(\(n^2\))。
优点是代码段，仅需3行，如下:
for(int i=0;i<n-1;i++)
for(int j=n-1;j>i;j--)
if(a[j]<a[j-1])swap(a[j],a[j-1]);
1.3插入排序
由插入排序联想到可以排序自己用扑克牌模拟排序，以此获得对算法更深的理解与记忆
插入排序默认第i个元素前面都已经有序了。只要把第i个元素插入到前面的合适位置即可。
时间复杂度为O(\(n^2\))。
代码如下:
for(int j,i=1;i<n;i++){
int key=a[i];
for(j=i-1;j>=0;j--){
if(key<a[j])a[j+1]=a[j];
else break;
}
a[j+1]=key;
}
2.提高排序
2.1快速排序
快速排序的是对冒泡排序的优化
采用分治思想，取一基准，再以基准为界划分为左右两部分，递归求解。
void qsort(int *a,int l,int r){
if(l>=r)return;
int mid=a[r],i=l,j=r;
while(i<j){
while(i<j&&a[i]<=a[mid])i++;
while(i<j&&a[j]>=a[mid])j--;
if(i<j)swap(a[i],a[j]);
}
swap(a[r],a[i]);
qsort(a,l,i-1);
qsort(a,j+1,r);
}
如果遇到出题人卡快排，可以采用随机基准
#include<stdlib.h>
#include<time.h>
srand((unsigned)time(NULL));
int mid=rand()%(r-l+1)+l,i=l,j=r;
swap(a[mid],a[l]);
生成[i,j]范围的随机数 rand%(j-i+1)+i
2.2归并排序
先不断递归将数组分成两部分，
再将两个数组有序合并。
void merge(int *al,int *ar,int *bl,int *br,int *c){
while(al<ar&&bl<br){
if(*al<*bl){
*c=*al;al++;
}
else{
*c=*bl;bl++;
}
c++;
}
while(al<ar){*c=*al;al++;c++;}
while(bl<br){*c=*bl,bl++;c++;}
}
void merge_sort(int l,int r){
if(r-l<=1)return;
int *tmp=new int(MAXN);
int mid=(l+r)/2;
merge_sort(l,mid);merge_sort(mid,r);
merge(a+l,a+mid,a+mid,a+r,tmp+l);
for(int i=l;i<r;i++)a[i]=tmp[i];
delete[] tmp;
}
归并排序的交换次数就是逆序对个数
优点：具有稳定性
缺点：需要额外空间
2.3堆排序
1.优先队列 priority_queue
2.手写二叉堆
#define op <//可决定大小根堆
int heap[MAXN],n;
void up(int x){
for(int i=x;i>1&&heap[i] op heap[i>>1];i>>=1)
swap(heap[i],heap[i>>1]);
}
int son(int x){
return x*2+
((x<<1)+1<=heap[0]&&heap[(x<<1)+1] op heap[x<<1]);
}
void down(int x){
for(int i=x,t=son(x);t<=heap[0]&&
heap[t] op heap[i];i=t,t=son(i))
swap(heap[i],heap[t]);
}
void push(int x){
heap[++heap[0]]=x;
up(heap[0]);
}
int top(){
return heap[1];
}
void pop(){
swap(heap[1],heap[heap[0]--]);
down(1);
}
void build(int *a,int n){
memcpy(heap+1,a,sizeof(int)*n);
heap[0]=n;
for(int i=(n>>1);i>0;i--)down(i);
}
int main(){
freopen("in.txt","r",stdin);
cin>>n;
for(int x,i=0;i<n;i++)cin>>x,push(x);
for(int i=0;i<n;i++)cout<<top()<<" ",pop();
return 0;
}