各种排序学习笔记

因为学了冒泡后就会用 sort 了,完全没有学过各种排序,第一次面试因为不会手写快排 GG ,痛定思痛,决定认真写篇学习博客 QAQ

冒泡排序

时间复杂度 $O(n^2)$ ,空间复杂度 $O(1)$ ,不断 swap 把大的排到后面,咕噜咕噜冒泡泡

1
2
3
4
5
6
7
8
9
10
11
12
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)$ ,每次将新元素插入已排序的数组中。

1
2
3
4
5
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)$ ,每次将最值放在当前可操作的首位。

1
2
3
4
5
6
7
8
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)$ ,递归,每次将要排序的子数组分成两个部分排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 ,根据这个值对数组进行调整。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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)$ ,每次对无序的子数组进行堆调整,将最值置于堆顶,然后把最值移到数组末尾,再对剩下的子数组进行操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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)$ ,将元素放进桶里,按桶的大小取出。

1
2
3
4
5
6
7
8
9
10
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