排序专题

排序专题

基本题面:

设有n个正整数,保证n不大于100且这n个数都不大于1000,对其进行从小到大的排序。

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;
int main()
{
int n,a[100];
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)//依次确定应该填在下标为i的位置的数
{
for(int j=i+1;j<n;j++)//将下标i上保存的数依次与其后所有数字比较
{
if(a[i]>a[j])
{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;
int main()
{
int n,a[100];
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)//通过第i次交换,能确定下标为i的位置所应该填写的数
{
for(int j=n-1;j>i;j--)//每次把最小的交换到最前面
{
if(a[j-1]>a[j])//比较相邻两个
{
int temp=a[j-1];
a[j-1]=a[j];
a[j]=temp;
}
}
}
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}

桶排序

桶排序有其缺点:

1、必须全是整数(负数可以平移数轴)

2、必须知道数字最大不超过多少

3、所开数组不得超过题目的内存限制

需要以上三点同时满足,否则不可以使用桶排序

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
#include<iostream>
using namespace std;
int main()
{
int n,a[100];
int bucket[1000]={0};//用bucket[i]表示数字i出现的次数,初始化为0
//因为题目中说了都是正整数而且均小于1000,所以数组开到1000
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
{
int number=a[i];
bucket[number]++;//每当数字i出现,就令其出现次数+1
}
for(int i=0;i<1000;i++)//因为题目中说了都是正整数而且均小于1000,所以循环小于1000
{
if(bucket[i]!=0)//如果bucket[i]==0,则表示数字i没有出现过,就不需要输出了
{
for(int j=0;j<bucket[i];j++)
{
//因为数字出现了bucket[i]次,所以需要循环bucket[i]次
//否则会造成重复数字只会输出一个
cout<<i<<" ";
}
}
}
return 0;
}

sort函数

sort函数默认是从小到大排序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
int n,a[100];
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}

如果要令sort函数实现从大到小排序,可以写作如下程序段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
bool cmp(int a,int b)
{
if(a>b) return true;
else return false;
}
int main()
{
int n,a[100];
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n,cmp);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}

其中cmp函数因为bool类型的特性,又可简写,变为如下程序段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
int n,a[100];
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n,cmp);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}

还可以有不写cmp函数,而使用重载运算符的方法。此处不做介绍,详见C++语言-9-结构体。

堆排序

堆排序需要使用优先队列,开始学习队列后才需要学习。

优先队列默认是最大堆,也就是说最大的数在队首。要实现从小到大排序的话只能写作如下程序段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int main()
{
int n;
priority_queue<int,vector<int>,greater<int> >q;
cin>>n;
for(int i=0;i<n;i++)
{
int t;
cin>>t;
q.push(t);
}
for(int i=0;i<n;i++)
{
cout<<q.top()<<" ";
q.pop();
}
return 0;
}

而若要用优先队列实现从大到小排序,只需写作如下程序段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int main()
{
int n;
priority_queue<int>q;
cin>>n;
for(int i=0;i<n;i++)
{
int t;
cin>>t;
q.push(t);
}
for(int i=0;i<n;i++)
{
cout<<q.top()<<" ";
q.pop();
}
return 0;
}

快速排序

快速排序是分治算法的入门题,开始学分治算法后才需要学习。

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
#include<iostream>
#include<cstdio>
using namespace std;
void kuai(int l,int r)//每次确定区间最中间的数字
{
int i=l,j=r,mid=a[(l+r)/2];
while(i<=j)
{
while(a[i]<mid) i++;
while(a[j]>mid) j--;
if(i<=j)
{
int tmp=a[i];
a[i]=a[j];
a[j]=tmp;
i++;
j--;
}
}
if(l<j) kuai(l,j);//排序左区间
if(r>i) kuai(i,r);//排序右区间
}
int main()
{
int n,a[100];
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
kuai(0,n-1);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}

--It's the end.Thanks for your read.--