排序
即将一个无序的数列通过一定方式转换成有序数列的一种操作.
算得上萌新们接受的第一类算法了.
julao们可以直接往下翻…
在萌新们学到了数组之后,就有了数据存储下来的能力.
就是定义一个数组…
大小有限,元素不一定有序.
一些题目要求,或者是有些处理需要将这些数据变得有序.
比如由大到小？或者是按某个权值排序..(struct)
就需要排序
萌新们需要学习的排序算法
1.桶排序
2.冒泡排序
3.选择排序
4.插入排序
5.归并排序
6.快速排序
7.基数排序
8.堆排序
9.希尔排序
第九个不一定需要学习….
以上九种排序方法,使用最多的当然是STL里面的sort啊快速排序
但是桶排序和基数排序有些题的思想需要用到,归并排序有些题比较特殊就需要用到归并.
这并不意味着冒泡排序、选择排序、插入排序这些没必要学哦.
这三种排序,实现较为简单,可以极大能力的提升萌新的代码能力.(建议掌握)
桶排序
桶排序,是目前来说最快的一种排序,只需要\(O(N)\)的时间复杂度即可将数组排序完.
\(O(N)\)的时间复杂度意味着只需要扫一遍数组中的所有元素即可将元素排好序.
代价就是所消耗的空间极大.(不定)
我们对于一个无序数组\(a\).
我们访问数组中的每一位元素.直接把以这个元素为下标的数组制为1.最后扫描一遍这个数组即可.
什么意思？
例如\(a\)数组中有5个元素,分别为7,6,2,5,1
我们打标的过程就是
\(f[7]=true\),\(f[6]=true\),\(f[2]=true\),\(f[5]=true\),\(f[1]=true\);
最后
|
1 2 |
for(int i=1;i<=maxa;i++) if(f[i]) b[++cnt]=i; |
\(maxa\)表示的是\(a\)数组中元素的最大值.举的例子就是7.
b[++cnt]的意思就是先将\(cnt+1\),再看\(b[cnt]\)的值.
与之对应的是b[cnt++]，这种是先看，再把\(cnt+1\)，这两种是不一样的
这个相当于我们访问了\(f\)数组中的1-7号元素,发现1、2、5、6、7号元素都出现过,所以我们按顺序把这些元素存到\(b\)数组中.
通过上面的方法,我们就可以把一个无序的数组\(a\)变成一个有序的数组\(b\)
当然你直接覆盖到a数组上也没什么问题
代码实现？
|
1 2 3 4 5 6 7 8 |
for(int i=1;i<=n;i++){ scanf("%d",&a[i]);//n个元素,存到a数组中 f[a[i]]=1; maxa=max(maxa,a[i]); } int cnt=0; for(int i=1;i<=maxa;i++) if(f[i]) b[++cnt]=i; |
不同的题目有不同的需要,第7行把元素再存到\(b\)数组当中也可以不用.
如果题目要求输出的话,可以直接输出
|
1 2 |
for(int i=1;i<=maxa;i++) if(f[i]) printf("%d",i); |
当然也可以直接把第2行换了,我们不需要将元素存储下来.
|
1 2 3 4 5 6 |
for(int i=1;i<=n;i++) { int a; scanf("%d",&a); f[a]=1; maxa=max(maxa,a); } |
最后直接遍历\(f\)数组就好了.
所以具体实现方法有很多.这个就是一种解决问题的思路.
个人倾向于把这种解决处理一类问题的相似做法称为一类问题的算法.
这是一种用空间换时间的想法.
因为这个数组一旦接近百万级别.就相当于需要开一个大小为百万级别的\(f\)数组.(不然会导致数组越界)
然而这样会导致你的程序消耗了很多无用的空间,并且最后在寻找的时候需要遍历百万级个变量.
这样就会让桶排序变得效率极差.就需要其他的排序方法出现了.
冒泡排序
冒泡排序与桶排序思路完全不同.
冒泡排序取名字与其具体做法有关系.
我们对一个无序的数组,需要将最大值移到数组的最后
只用扫描一遍数组就好了
|
1 2 3 4 5 6 7 |
for(int i=1;i<n;i++) if(a[i]<a[i+1]){//交换相邻变量.也可以用库函数swap. int tmp=a[i]; a[i]=a[i+1]; a[i+1]=tmp; } |
那么问题来了,如果我们需要将这个数组变得有序,使用类似的方法如何解决？
其实做法类似.因为扫描一遍数组可以将最大值移到数组的最后
那么扫描第二遍的时候就可以将次大值移到数组的倒数第二位.
嗯？
扫描\(n\)遍的时候就可以让数组中的元素有序了.
所以总的时间复杂度是\(O(N^2)\)的
这时候有人要提出疑问了,我们第二遍扫描的时候不用管最后一个值.所以每次扫描的时候都可以少扫描一个值.这样时间复杂度还是\(N^2\)的么？
是的.每次扫描都可以让下次扫描少扫描一个值.这样可以优化到程序的一部分运行速度.
我们将此类优化称之为常数优化.
如果我头还可以的话,每次少扫描一个可以让总的时间复杂度下降到\(O(\frac{N^2}{2})\).
然而对于\(N\)是百万级别的话,单纯的除以2并不能保证在\(1s\)内跑完.所以没什么p用
这是冒泡排序的思路.
代码实现？
|
1 2 3 4 |
for(int i=1;i<=n;i++) for(int j=1;j<n;j++) if(a[j]>a[j+1]) swap(a[j],a[j+1]);//未加优化 |
|
1 2 3 4 |
for(int i=1;i<=n;i++) for(int j=1;j<n-i+1;j++) if(a[j]>a[j+1]) swap(a[j],a[j+1]);//加优化的 |
注意j的结束边界不加等于号.不然j+1会导致访问到n个元素之外的元素.
这个排序是从由小到大没关系,反过来排序后的结果可能会出现莫名的0.
有木有觉得很简单!!
没有
选择排序
留着填坑喽
插入排序
留着填坑喽
归并排序
其实我写这个博客是打算复习归并排序的..
突然没了写下去的想法,听说要考试了,难受
归并用了分治的思想来搞的.
首先我们考虑如果说是两个有序的数列要合并成一个的话,其实很好实现的.
比较,小/大的加入到新的数组中,然后删除原来数组中的元素,一直到某一个数组为空截止,一旦一个为空的话就直接把另一个数组中的所有元素直接pia过来,这样就可以合并两个有序数列了.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
void m_sort(int a[],int n,int b[],int m,int c[])//把有序数组a,b合并到c中 { int i,j,k; i=j=k=0; while(i<=n&&j<=m){ if(a[i]<b[j]) c[k++]=a[i++]; else c[k++]=b[j++]; } while(i<n) c[k++]=a[i++]; while(j<m) c[k++]=b[j++]; } |
其实合并的效率很高的.可以到达\(O(N)\)的.
那现在问题是如何让两个数组变成有序的？
想一下如果两个数组中元素仅剩一个的话,是不是可以说明这个数组是有序的.
那就是说我们需要先递归的把数列分为n个小数组.在把这些个数列合并起来就好了.
我们拆的时候是一次将一个长度为\(n\)的数组拆成两个长度为\(\frac{n}{2}\)的数组.
所以将数列拆成小数列一共需要\(log_2N\)步.每次拆完都要合并,所以总的时间复杂度就是
\(O(Nlog_2N)\)
即便是快排、堆排序、希尔排序这类时间复杂度在同一个水平线上的排序,还是归并排序更稳一些考试的时候一样写sort..
对于排序的时间复杂度可以看这个例子
代码展示？
|
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 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std ; template<class T>void read(T &x){ x=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9'){f|=(ch=='-');ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x=f?-x:x; return ; } int a[100010],tmp[100010]; void cc(int l,int m,int r){ int i=l,j=m+1,k=l; while(i<=m&&j<=r) if(a[i]>a[j])tmp[k++]=a[j++]; else tmp[k++]=a[i++]; while(i<=m) tmp[k++]=a[i++]; while(j<=r) tmp[k++]=a[j++]; for(int x=l;x<=r;x++) a[x]=tmp[x]; } void msort(int l,int r){ if(l<r){ int M=(l+r)>>1; msort(l,M);msort(M+1,r); cc(l,M,r); } } int main() { int n; read(n); for(int i=1;i<=n;i++) read(a[i]); msort(1,n); for(int i=1;i<=n;i++) printf("%d ",a[i]); return 0; } |
快速排序
留着填坑喽
基数排序
留着填坑喽
堆排序
留着填坑喽
希尔排序
留着填坑喽
By:Wahacer
2017.12.19