排序算法

前言

欢迎米娜桑大家来到大连市第二十四中学金普学校！

我叫于子洋

今年高一 现役信竞队队员

是队里最菜的

所以讲的不好还请见谅

后面的巨佬们讲的都比我好

所以各位不要急，等一个多小时就换下一个人讲了（）

在接下来的一个多小时里，各位有任何问题可以直接打断我，不用有任何顾虑，也不要紧张，毕竟我也没比你们大多少，我们就当作聊天，就把我当作同校同学就行

（回归正题）那么，感谢各位参见本次活动

接下来由我讲述最基础的排序算法

【呱唧呱唧】

引入->算法->例题

讲解内容:

冒泡排序

选择排序

插入排序

桶排序

sort与cmp

第一节 引入

什么是排序?

人类智慧?

代码实现!?

第二节 算法+例题

冒泡排序

冒泡排序是最简单的常见排序算法。

冒泡排序的工作原理是每次检查相邻两个元素，如果前面的元素比后面的元素大，就将相邻两个元素交换，使得前面的元素比后面的元素小。

当没有相邻的元素需要交换时，排序就完成了。

由于在算法的执行过程中，较小的元素像是气泡般慢慢「浮」到数列的顶端，故叫做冒泡排序。

code

排序板子题

选择排序

选择排序的原理是每次找出第i小的元素（也就是从第i个往后最小的元素），然后将这个元素与数组第i个位置上的元素交换位置。这样每次操作完就可以使前i个元素是有序的。

假设元素一共有n个，那么操作n次后，排序就完成了。

code

排序板子题

插入排序

插入排序的工作原理为将待排列元素划分为「已排序」和「未排序」两部分，每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。

code

排序板子题

关于本人英语水平的一些说明=.= (蒸乌鱼)

桶排序

排序，但是不比较 ?!

不用比较怎么排序？难以理解

桶排序按下列步骤进行：

1. 设置一个定量的数组当作空桶；
2. 遍历序列，并将元素一个个放到对应的桶中；
3. 将桶里的元素依次取出

code

利用桶找出现次数最多的字母

sort()与cmp函数

一共有多少种排序?

常见排序：冒泡 选择 插入 桶排 基数 快排 计数 希尔 归并.....

“这么多排序方法，其实实现的不都是一个目的嘛？”

“每次都要重写一遍排序代码，好麻烦啊”

所谓有需求就有供应，在c++中已经有人为我们写好了在大多数情况下最快速的排序方法并封装了起来方便我们使用，这种排序叫做std sort，即“标准排序”

目前阶段我们不需要知道标准排序的原理是什么，因为那太过复杂，我们只需要知道【标准排序可以干什么】【怎么用标准排序】就可以了

【标准排序可以干什么】

标准排序可以在大多数情况下以近乎最高的效率将若干元素进行排序

【如何使用标准排序】

sort()函数

假设我们有一个数组a[]

数组a中存有n个元素(下标从1到n)

我们想使用标准排序对a数组中的n个元素进行排序

只需要在程序中以下列格式调用函数即可

sort(a+1,a+1+n);

注意，在填写括号内容时，假设我们要排序的元素下标从x到y，数组名叫a，那么逗号前要写成a+x，而逗号后要写成a+y+1

我们并不需要知道为什么这样做，只需要记住它的使用方法即可

code

排序板子题

cmp()函数

想必各位刚刚考完期末考试（坏笑）

大多数班级在考试后会将班内所有人按照成绩进行排名

但是排名过程中可能遇到一个问题

如果有两个人的总分一样怎么办？

大多数人认可的潜规则是，如果总分一样，就按语文成绩分出先后，如果语文成绩还一样，就用数学成绩分出先后，如果数学成绩.....

由此可见，有时候我们在对元素进行排序时，依照的关键字不止一种。如上述例子中，关键字不仅有总分，还有语文成绩，数学成绩.......

而我们刚刚学习的算法，都只能处理单一关键字的排序需求。

那么，如何进行多关键字排序呢？

前面讲到的std sort就封装了多关键字排序

我们只需要告诉它按照什么规则来排序就好

例如，在上述期末成绩的例子中，我们可以告诉std sort，我们要优先按照总分排序，如果总分相同，再按照语文成绩排序，这样std sort才能知道按照什么规则来排序。

具体地，我们若想实现多关键字排序，只需在调用sort函数时在括号内多打一个逗号和cmp，就像这样

sort(a+1,a+n+1,cmp);

然后写一个cmp函数就可以了

那么如何写cmp函数呢？

请背过以下模板：

code

多关键字排序

第三节 练习题

单词排序

车厢重组

出现次数超过一半的数

合影效果