2.4 KiB
4.2 排序算法
排序算法非常有用，除了用于实现类似于“按学生成绩进行排名”这种需求外，其他的一些需求和算法也往往以排序算法为基础。例如，在有序数组中进行查找，就比在无序数组中进行查找快很多，为了获得有序数组，就需要先对数组进行排序。
常见的三种排序算法为：冒泡排序、选择排序和快速排序。在讲解排序和查找等算法时，往往以数组为对象，但这些算法的应用对象并不仅限于数组。
4.2.1 冒泡排序
俩俩交换
比较和交换次数：O(N^2)
4.2.2 选择排序
选择排序是最简单，也是最容易理解的排序算法。其思想是：每次都从待排序的元素中选取最大/最小的元素，加入到已排序的列表中，直到没有待排序的元素为止。
例如，将元素按从 A-Z 的顺序进行排列（假设 A<B<C...），假设在排序前，数组中元素分布如下：
| 序号 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 元素 | B | E | A | F | C | D |
在排序最开始的时候，选取 0 号元素 B，接着将 B 与序号为 1-5 的元素进行比较，当 B 与 E 进行比较时，E>B，因此 E 不会被选中，接着 B 与下一个元素 A 比较，由于 A<B，因此 A 代替 B 被选中，并将 A B 进行交换。接着将 A 与后续元素进行比较。在完成一轮比较和选取操作后，将得到最小的元素，并且已置于 0 号位置。
| 序号 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 元素 | A | E | B | F | C | D |
接着选取 1 号元素 E，将 E 与 2-5 号元素进行比较、选取和交换。接着从 2 号元素开始...直到没有再需要被排序的元素为止。
比较次数：O(N^2) 交换次数：O(N)
4.2.3 插入排序
比较和交换次数：O(N^2)，一般情况下比冒泡排序快一倍，比选择排序还要快一点。
4.2.3 快速排序
基本有序
快速排序是一种常用的排序算法。比选择排序算法快。例如，C语言标准库中的函数 qsort 实现的就是快速排序。快速排序也使用了 D&C。
下面来使用快速排序对数组进行排序。对排序算法来说，最简单的数组什么样呢？还记得前一节的“提示码？就是根本不需要排序的数组。
大多数情况下执行时间为：O(N*logN)
练习
编码实现快速排序算法。