因为学了冒泡后就会用 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