第二节 从排序开始

  今天看群里有同学说：“看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(数组名，初始化内容，初始化范围)；