各种排序学习笔记
因为学了冒泡后就会用 sort 了，完全没有学过各种排序，第一次面试因为不会手写快排 GG ，痛定思痛，决定认真写篇学习博客 QAQ
冒泡排序
时间复杂度 O(n^2) ，空间复杂度 O(1) ，不断 swap 把大的排到后面，咕噜咕噜冒泡泡
void BubbleSort(int *a,int len){
for(int i=1;i<len;++i){
int ff(0);
for(int j=0;j<len-i;++j){
if(a[j]>a[j+1]){
swap(a[j],a[j+1]);
ff++;
}
}
if(!ff) break; // 小剪枝
}
}插入排序
时间复杂度 O(n^2) ，空间复杂度 O(1) ，每次将新元素插入已排序的数组中。
void InsertSort(int *a,int len){
for(int i=1;i<len;++i)
for(int j=i;j>0;--j)
if(a[j]<a[j-1]) swap(a[j],a[j-1]);
}选择排序
时间复杂度 O(n^2) ，空间复杂度 O(1) ，每次将最值放在当前可操作的首位。
void SelectSort(int *a,int len){
for(int i=0;i<len;++i){
int mn=i;
for(int j=i+1;j<len;++j)
if(a[j]<a[mn]) mn=j;
swap(a[i],a[mn]);
}
}归并排序
时间复杂度 O(nlogn) ，空间复杂度 O(n) ，递归，每次将要排序的子数组分成两个部分排序。
void MergeSort(int *a,int l,int r){
if(l>=r) return;
int mid=l+r>>1;
MergeSort(a,l,mid);
MergeSort(a,mid+1,r);
int i=l,j=mid+1,tlen=l,tmp[maxn];
while(i<=mid&&j<=r){
if(a[i]<=a[j]) tmp[tlen++]=a[i++];
else tmp[tlen++]=a[j++];
}
while(i<=mid) tmp[tlen++]=a[i++];
while(j<=r) tmp[tlen++]=a[j++];
for(int i=l;i<=r;++i) a[i]=tmp[i];
}
void solve(){
MergeSort(a,0,len-1);
}快速排序
时间复杂度 O(nlogn) ，空间复杂度 O(logn) ，每次找一个比较合适的 pivot ，根据这个值对数组进行调整。
int findmiddle(int a,int b,int c){
int tmp=a^b^c;
int mx=max({a,b,c});
int mn=min({a,b,c});
return tmp^mx^mn;
}
void QuickSortAdjust(int *a,int l,int r){
if(l>=r) return;
int pivot=findmiddle(a[l],a[r],a[l+r>>1]);
int i=l,j=r;
while(i<=j){
while(i<=j&&a[i]<pivot) i++;
while(i<=j&&a[j]>pivot) j--;
if(i<=j) swap(a[i++],a[j--]);
}
QuickSortAdjust(a,l,j);
QuickSortAdjust(a,i,r);
}
void QuickSort(int *a,int len){
QuickSortAdjust(a,0,len-1);
}堆排序
时间复杂度 O(nlogn) ，空间复杂度 O(1) ，每次对无序的子数组进行堆调整，将最值置于堆顶，然后把最值移到数组末尾，再对剩下的子数组进行操作。
void HeapAdjust(int *a,int len){
for(int i=len-1;i>0;--i){
if((i&1)&&(a[i]>a[i/2]))
swap(a[i],a[i/2]);
else if(!(i&1)&&(a[i]>a[i/2-1]))
swap(a[i],a[i/2-1]);
}
}
void HeapSort(int *a,int len){
while(len){
HeapAdjust(a,len--);
swap(a[0],a[len]);
}
}
// 加速版
void _HeapAdjust(int *a,int x,int len){
int fa=x,son=(fa<<1)|1;
while(son<len){
if(son+1<len&&a[son]<a[son+1]) son++; // 哪个小孩
if(a[fa]>=a[son]) break;
swap(a[fa],a[son]);
fa=son; son=(fa<<1)|1;
}
}
void _HeapSort(int *a,int len){
for(int i=(len>>1)-1;i>=0;--i)
_HeapAdjust(a,i,len);
for(int i=len-1;i>=0;--i){
swap(a[0],a[i]);
_HeapAdjust(a,0,i);
}
}桶排序
时间复杂度 O(n+k) ，空间复杂度 O(n+k) ，将元素放进桶里，按桶的大小取出。
void BucketSort(int *a,int len){
int vis[maxn]={0}; // 值域
for(int i=0;i<len;++i){
vis[a[i]]++;
}
int cnt(0);
for(int i=0;i<maxn;++i){
while(vis[i]) vis[i]--,a[cnt++]=i;
}
} 基数排序
时间复杂度 O(n*k) ，空间复杂度 O(n+k) 。两种：一种（LSD）从低位到高位放进桶里（每次 10 个）。一种（MSD）从高位到低位放进桶里，一位处理完后，直接在当前桶里分下一位的类。复杂度略高而且代码过长，感觉能嘴就行 233
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录