排序
选择排序
基本思想:每次都把最大的数字放在最后一个,就可以把最后一个剔除出排序序列。
这样就等价于把剩下的
怎么找到最大的?直接扫一遍!
for(int i=n;i>=1;--i)
{
int pos=i;
for(int j=1;j<=i;++j)
{
if(a[j]>a[pos]) pos=j;
}
swap(a[i],a[pos]);
}
2
3
4
5
6
7
8
9
冒泡排序
基本思想和选择排序一致。
但是实现方法有所不同:
从前到后扫一遍,如果前面的比后面的大,就交换相邻的两个数字。
for(int i=n;i>=1;--i)
{
for(int j=1;j<n;++j)
{
if(a[j]>a[j+1]) swap(a[j],a[j+1]);
}
}
2
3
4
5
6
7
为什么叫冒泡?因为是相邻两个交换,如同从下往上冒泡,如果大泡泡在小泡泡下面,就冒到上面去,最后最大的泡泡在最上面。
每次排序后,最大的数字会冒泡到最后一个位置去,然后剩下的 n-1
个数字再继续冒泡。
这个和逆序对有关系!
逆序对的定义:
对于一个数列
如:
中的逆序对有
冒泡排序和他有什么关系呢?
冒泡排序只有在
无论 a[j],a[j+1]
是否交换:
对于 1~(j-1)
位置上的数字,他们和 a[j],a[j+1]
这两个数字之间的逆序对数不变。
对于 (j+2)~n
位置上的数字,他们和 a[j],a[j+1]
这两个数字之间逆序对数也不变。
综上:一次交换只会让逆序对数量减一
所以冒泡排序的总交换次数是序列的逆序对数。
快速排序
上面的排序都是
而快速排序思想不同:
首先,在序列中随机选一个数字,比如说是序列中间的数字,大小为 mid
。
然后,尝试将这个数字放在它该在的位置上
把小于他的数字都放他左边(不排序),大于他的数字都放在它右边(不排序)。
实现这个过程,设两个变量,一个指向左端点,一个指向右端点。
找到左边第一个大于等于 mid
的位置
找到右边第一个小于等于 mid
的位置
交换这两个位置上的数字,然后都跳过该位置。
重复这个过程,直到两个变量相遇。
这样就把 mid
放到了正确的位置,而且左边都小于 mid
,右边都大于 mid
。
然后再对左右两边分别排序。
inline void qsort(int l,int r)
{
int mid=a[(l+r)/2];
int i=l,j=r;
do
{
while(a[i]<mid) ++i;
while(a[j]>mid) --j;
if(i<=j)
{
swap(a[i],a[j]);
++i,--j;
}
}while(i<=j);
if(l<j) qsort(l,j);
if(i<r) qsort(i,r);
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
这样每个函数里面要花费
根据随机原则,我们可以假设这个数字的期望大小位于序列的中间位置。
所以会把序列分成两个差不多长的子序列。那么分
那么我们整个递归过程,会分成
注意,这里是每层的总长度是
比如第一层,范围是
那么第二层,就会分成
所以每个处理区间,时间复杂度应该和本区间的长度相关,而不能是和
因为不能保证我们选取的数字最后一定在正中间,所以只是期望复杂度。
归并排序
考虑这样一个问题,将两个已经有序的长度为
是
用两个变量从前往后表示两个数组的下标,每次把最小的那个放入新的数组里:
int a[101],b[101],c[201];
//假设序列a长度为n,序列b长度为m,把他们合并入c数组
int t1=1,t2=1;
for(int i=1;i<=n+m;++i)
{
if(t1<=n&&(t2>m||a[t1]<b[t2])) c[i]=a[t1++];
else c[i]=b[t2++];
}
2
3
4
5
6
7
8
那么,如果我们把整个序列分成两个小序列,把这两个序列排好序,然后再按上面方法拼接起来,岂不是完成了排序!
那怎么把两个小序列排好序呢?
简单,接着划分!不停地划分,分到序列长度为
然后再不停地按上述方法合并回去,直到把所有序列都合并完。
每次划分都会让序列长度减半,所以划分
每次合并时间都是
总时间复杂度是
代码如下:
void solve(int l,int r)
{
if(l==r) return;
solve(l,mid);
solve(mid+1,r);
int tl=l,tr=mid+1;
for(int i=l;i<=r;++i)
{
if(tl<=mid&&(tr>r||a[tl]<=a[tr])) f[i]=a[tl++];
else f[i]=a[tr++];
}
for(int i=l;i<=r;++i) a[i]=f[i];
}
2
3
4
5
6
7
8
9
10
11
12
13
而且这样还可以做到一个事情:顺便把逆序对数求出来。
怎么做呢?
我们看合并这一段。
假如两个变量是 tl,tr
,当前放入的是 tr
。
那么左半段序列中,还没有放的数字都应该比这个数字大(数字相同的情况下先放左边)。
此时,左半段中还没有放的数字都和 tr
位置上的数字构成了逆序对。
int ret=0;//统计逆序对数
void solve(int l,int r)
{
if(l==r) return;
solve(l,mid);
solve(mid+1,r);
int tl=l,tr=mid+1;
for(int i=l;i<=r;++i)
{
if(tl<=mid&&(tr>r||a[tl]<=a[tr])) f[i]=a[tl++];
else
{
f[i]=a[tr++];
ret+=(mid-tl+1);//这个数字和前半段产生了多少对逆序对
}
}
for(int i=l;i<=r;++i) a[i]=f[i];
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
有人可能会疑惑:这样能不重复不遗漏地算出所有的逆序对吗?
是可以的,这是分治算法的基本思想:
这是一个长度为
对于一个分治结构来说,每一对逆序对,都可以对应分治上的一个结点(除了最下面一排单独的)。
因为每个分治结点,都对应一条中位线,对于一对逆序对,我们只要看它跨过了哪些中位线,取最靠上的那个。
比如逆序对
再比如逆序对
所以,所有的逆序对都刚好被统计一次!这样就可以
sort
排序作为一个非常常用的功能,是有前辈们封装好的函数的:
int a[101];
//输入a数组
sort(a+1,a+n+1);
2
3
他的功能是将 a[1]~a[n]
从小到大排序。
这个排序的复杂度是
如果你不想从小到大排序?
bool cmp(int a,int b)
{
return a>b;
// 等价于 if(a>b) return 1; else return 0;
}
int main()
{
int a[101];
//输入a数组
sort(a+1,a+n+1,cmp);
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
可以在函数里加一个 cmp
参数,在里面定义你想要的排序规则。
cmp
是 bool
类型的,有两个参数,两个参数的类型必须和排序的数组类型一致。
然后返回值是排序规则。
需要注意的是,排序规则必须不能双向成立,比如说 a>=b
,当 a
和 b
相等时,无论 a
和 b
哪个在左边,式子都将成立,会导致程序产生段错误或超时。
通过 cmp
函数,你可以给任意类型制定任意的排序规则。
对于数字类型变量,默认排序规则是从小到大。
对于字符和字符串类型变量,默认排序规则是字典序。
注意自定义结构体排序必须要用 cmp
指定排序规则,因为本身结构体是不具有默认的排序规则的。
struct node
{
int x,y;
};
bool cmp(node a,node b)
{
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
node a[101];
sort(a+1,a+n+1,cmp);
2
3
4
5
6
7
8
9
10
11
桶排序
有一个题目叫三位数排序,给定三个数字 1<=a,b,c<=100
,把他们从小到大输出。
有一个同学是这样写的,非常新颖:
for(int i=1;i<=100;++i)
{
if(i==a) cout<<i<<' ';
if(i==b) cout<<i<<' ';
if(i==c) cout<<i<<' ';
}
2
3
4
5
6
这个思路可以拓展,给定一个数组,数字范围是 1~m
,将他们从小到大排序:
for(int i=1;i<=m;++i)
{
for(int j=1;j<=n;++j)
{
if(a[j]==i) cout<<i<<' ';
}
}
2
3
4
5
6
7
这样时间复杂度就是
还可以优化一下,每个数字对着整个数字对比一下太麻烦了,我们只想知道这个数组有没有这个数字出现过。
那么不如用另一个数组记录每个数字出现了多少次。
就好像先用标号为 1~m
的桶把每个数字都装进去,再从小到大把他们倒出来。
for(int i=1;i<=n;++i) cnt[a[i]]++;
for(int i=1;i<=m;++i)
{
while(cnt[a[i]]>0)
{
cout<<i<<' ';
--cnt[a[i]];
}
}
2
3
4
5
6
7
8
9
这样时间复杂度就变成了
这种排序方法适用于数字范围比较小的情况。
练习题
注意,我们学这么多排序并不只是为了排序本身(只想排序用 sort
就可以了),而是主要学习这些排序的思想,并拓展到解决到更多的问题上。
P1012 [NOIP1998 提高组] 拼数 需要一点科技,不会建议看题解