第二节 从排序开始

  今天看群里有同学说:“看dalao的博客,今天晚上估计要讲C++框架了”,这我能忍?让你们猜到了,我该多没面子啊。所以呢,今天我就把教程改了一下,顺便更好地串联后面的内容。

  如题,我们今天要讲的是排序,排序是写程序中,比较重要的一个部分,以后也会专门做一个章节去讲,今天只涉及一些简单的排序方法。

这他喵叫排序?——桶排序

  一直讲排序,可能会有些枯燥,我们先来点好玩的。

  桶排序是最简单的排序算法,思路也是最奇葩的,奇葩到我都不想把它算作排序。那么它具体是怎么来的呢,我们来看下面一个题目:

  在一次体育比赛中,某个选手的动作将会由多名裁判进行打分,分值在0~10之间的整数。输入一个数组,存放有N名裁判给出的分数(1<=N<=10000),输出要求从大到小输出裁判打出的分数。

  这道题很简单,有同学该说了,“我知道!用冒泡!”行,冒泡的确可以解决这个问题,但是时间复杂度可能会比较高。这道题,有一种更好的方法,那就是我们这一节的主角——桶排序,今天学了可能一辈子都再也用不到的排序方法。那么,究竟应该怎么去做呢?

  首先声明一个长度为11的数组a[11],再将该数组的每个元素都赋值为0。当选手得分为s时,进行操作a[s]++。这样进行一遍便利之后,我们数组中每个元素都将表示得s分的次数。这样,我们只需要将s打印a[s]次,就会得到我们需要的结果,代码如下:

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 <stdio.h>
#include <iostream>
#include <cstring>
#define N 10010
int grade[N];
using namespace std;
int main()
{
int n,a[11];
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&grade[i]);
}
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++) {
a[grade[i]]++;
}
for(int i=10;i>=1;i--) {
if(a[i]==0) continue;
else {
for(int j=1;j<=a[i];j++) {
printf("%d",i);
}
}
}
printf("\n");
return 0;
}

基础中的基础,“牛奶杯”排序

  有一杯水,一杯牛奶,想让他们两个换一下,那么我们得需要另一个杯子作为中转站。这是我们在写程序中,进行值交换的最简单的方法。比如航电上的hdu2000题:http://acm.hdu.edu.cn/showproblem.php?pid=2000这就是一道使用牛奶杯排序法的题目,我们只需要一个中间变量就可以实现两个变量值的交换,然后比较三次达到排序的目的。这种方法比较麻烦,适用于样本比较少的排序。

C++,带带我(利用C++的STL函数排序)

  其实在竞赛中,我们最常使用的是C++的STL中的排序函数。(STL是C++的标准模版库)

  sort()函数是我们最常用的排序函数,它在algorithm头文件中,使用时需要在你的程序上方添加一行:

1
#include<algorithm>

  排序函数在比赛中都是被允许的,它拥有三个参数:

sort(起始地址,终止地址,[比较方法])

  其中比较方法不是必须参数,它的使用方法我们将会在下一节进行说明。那么,一个使用sort()函数进行排序的简单程序如下:

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

  刚刚的那道hdu2000也可以使用这种方法去做,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
char str[3];
while(cin>>str) {
sort(str,str+3);
cout<<str[0]<<" "<<str[1]<<" "<<str[2]<<endl;
}
return 0;
}

初始化

  除了排序,初始化也很重要。在做和图、矩阵有关的题目时,我们经常会对二维数组进行初始化。将两个无关点之间的距离初始化为无穷,或者是给单位矩阵非对角线元素进行的初始化。C++给我们提供了memset() 函数实现初始化,这个函数在cstring头文件中。下面是memset() 函数的参数:

Memset(数组名,初始化内容,初始化范围);