排序及应用专题训练

Login to join training plan

排序定义

​排序算法​（英语：Sorting algorithm）是一种将一组特定的数据按某种顺序进行排列的算法。排序算法多种多样，性质也大多不同。

性质

稳定性

稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。

拥有稳定性这一特性的算法会让原本有相等键值的纪录维持相对次序，即如果一个排序算法是稳定的，当有两个相等键值的纪录 $R$和 $S$，且在原本的列表中 $R$出现在$S$之前，在排序过的列表中$R$也将会是在$S$之前。

基数排序、计数排序、插入排序、冒泡排序、归并排序是稳定排序。

选择排序、堆排序、快速排序、希尔排序不是稳定排序。

时间复杂度

时间复杂度用来衡量一个算法的运行时间和输入规模的关系，通常用 $O$ 表示。

简单计算复杂度的方法一般是统计「简单操作」的执行次数，有时候也可以直接数循环的层数来近似估计。

时间复杂度分为最优时间复杂度、平均时间复杂度和最坏时间复杂度。OI 竞赛中要考虑的一般是最坏时间复杂度，因为它代表的是算法运行水平的下界，在评测中不会出现更差的结果了。

基于比较的排序算法的时间复杂度下限是 $O(n\log n))$的。

当然也有不是 $O(n\log n))$的。例如，计数排序 的时间复杂度是$O(n + w)$，其中 $w$代表输入数据的值域大小。

以下是几种排序算法的比较。

空间复杂度

与时间复杂度类似，空间复杂度用来描述算法空间消耗的规模。一般来说，空间复杂度越小，算法越好。

排序相关 STL

头文件<algorithm> 。

std::sort

参见：std::sort

用法：

// a[0] .. a[n - 1] 为需要排序的数列
// 对 a 原地排序，将其按从小到大的顺序排列
std::sort(a, a + n);

// cmp 为自定义的比较函数
std::sort(a, a + n, cmp);

注意：sort 的比较函数的返回值是 true 和 false，用 true 和 false 表示两个元素的大小（先后）关系，具体内容详见上方给出的 sort 的文档。

std::sort 函数是更常用的 C++ 库比较函数。该函数的最后一个参数为二元比较函数，未指定 cmp 函数时，默认按从小到大的顺序排序。

自定义比较

参见：运算符重载

内置类型（如 int）和用户定义的结构体允许定制调用 STL 排序函数时使用的比较函数。可以在调用该函数时，在最后一个参数中传入一个实现二元比较的函数。

对于用户定义的结构体，对其使用 STL 排序函数前必须定义至少一种关系运算符，或是在使用函数时提供二元比较函数。通常推荐定义 operator<。

示例：

int a[1009], n = 10;
// ...
std::sort(a + 1, a + 1 + n);                  // 从小到大排序
std::sort(a + 1, a + 1 + n, greater<int>());  // 从大到小排序

struct data {
  int a, b;

  bool operator<(const data rhs) const {
    return (a == rhs.a) ? (b < rhs.b) : (a < rhs.a);
  }
} da[1009];

bool cmp(const data u1, const data u2) {
  return (u1.a == u2.a) ? (u1.b > u2.b) : (u1.a > u2.a);
}

std::sort(da + 1, da + 1 + 10);  // 使用结构体中定义的 < 运算符，从小到大排序
std::sort(da + 1, da + 1 + 10, cmp);  // 使用 cmp 函数进行比较，从大到小排序

计数排序

本页面将简要介绍计数排序。

定义

计数排序（英语：Counting sort）是一种线性时间的排序算法。

过程

计数排序的工作原理是使用一个额外的数组 $C$，其中第 $i$ 个元素是待排序数组 $A$ 中值等于 $i$ 的元素的个数，然后根据数组 $C$ 来将 $A$中的元素排到正确的位置。

它的工作过程分为三个步骤：

1. 计算每个数出现了几次；
2. 求出每个数出现次数的 前缀和；
3. 利用出现次数的前缀和，从右至左计算每个数的排名。

计算前缀和的原因

阅读本章内容只需要了解前缀和概念即可

直接将 $C$中正数对应的元素依次放入 $A$ 中不能解决元素重复的情形。

我们通过为额外数组 $C$ 中的每一项计算前缀和，结合每一项的数值，就可以为重复元素确定一个唯一排名：

额外数组 $C$ 中每一项的数值即是该 key 值下重复元素的个数，而该项的前缀和即是排在最后一个的重复元素的排名。

如果按照 $A$的逆序进行排列，那么显然排序后的数组将保持 $A$ 的原序（相同 key 值情况下），也即得到一种稳定的排序算法。

性质

稳定性

计数排序是一种稳定的排序算法。

时间复杂度

计数排序的时间复杂度为 $O(n+w)$，其中 $w$代表待排序数据的值域大小。

代码实现

const int N = 100010;
const int W = 100010;

int n, w, a[N], cnt[W], b[N];

void counting_sort() {
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= n; ++i) ++cnt[a[i]];
    for (int i = 1; i <= w; ++i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; --i) b[cnt[a[i]]--] = a[i];
}

结构体

结构体（struct），可以看做是一系列称为成员元素的组合体。

可以看做是自定义的数据类型。

​本页描述的 struct 不同于 C 中 struct，在 C++ 中 struct 被扩展为类似 class 的类说明符​。

定义结构体

struct Object {
  int weight;
  int value;
} e[array_length];

const Object a;
Object b, B[array_length], tmp;
Object *c;

上例中定义了一个名为 Object 的结构体，两个成员元素 value, weight，类型都为 int。

在 } 后，定义了数据类型为 Object 的常量 a，变量 b，变量 tmp，数组 B，指针 c。对于某种已经存在的类型，都可以使用这里的方法进行定义常量、变量、指针、数组等。

关于指针：不必强求掌握。

定义指针

如果是定义内置类型的指针，则与平常定义指针一样。

如果是定义结构体指针，在定义中使用 StructName* 进行定义。

struct Edge {
  /*
  ...
  */
  Edge* nxt;
};

上例仅作举例，不必纠结实际意义。

访问/修改成员元素

可以使用 变量名.成员元素名 进行访问。

如 : 输出 var 的 v 成员：cout << var.v。

也可以使用 指针名->成员元素名 或者 使用 (*指针名).成员元素名 进行访问。

如 : 将结构体指针 ptr 指向的结构体的成员元素 v 赋值为 tmp：(*ptr).v = tmp 或者 ptr->v = tmp。

为什么需要结构体？

首先，条条大路通罗马，可以不使用结构体达到相同的效果。但是结构体能够显式地将成员元素（在算法竞赛中通常是变量）捆绑在一起，如本例中的 Object 结构体，便将 value,weight 放在了一起（定义这个结构体的实际意义是表示一件物品的重量与价值）。这样的好处边是限制了成员元素的使用。 想象一下，如果不使用结构体而且有两个数组 value[], Value[]，很容易写混淆。但如果使用结构体，能够减轻出现使用变量错误的几率。

并且不同的结构体（结构体类型，如 Object 这个结构体）或者不同的结构体变量（结构体的实例，如上方的 e 数组）可以拥有相同名字的成员元素（如 tmp.value,b.value），同名的成员元素相互独立（拥有独自的内存，比如说修改 tmp.value 不会影响 b.value 的值）。 这样的好处是可以使用尽可能相同或者相近的变量去描述一个物品。比如说 Object 里有 value 这个成员变量；我们还可以定义一个 Car 结构体，同时也拥有 value 这个成员；如果不使用结构体，或许我们就需要定义 valueOfObject[],valueOfCar[] 等不同名称的数组来区分。

注意事项

为了访问内存的效率更高，编译器在处理结构中成员的实际存储情况时，可能会将成员对齐在一定的字节位置，也就意味着结构中有空余的地方。因此，该结构所占用的空间可能大于其中所有成员所占空间的总和。

主题库排序训练 - ACjudge