基础算法说明,不涉及算法的书写实现,只整理算法的操作思想,以及复杂度比较。
排序
排序的稳定性只对 结构类型数据 的排序有意义。
1. 插入排序
基本思想:每步将一个待排序的对象,按其有关键码大小,插入到前面已经排好序的一组对象的适当位置上,知道对象全部插入为止。
基本操作:有序插入。在有序序列中插入一个元素,保持序列有序,有序长度不断增加。
1.1 直接插入排序:采用顺序查找法查找插入位置。
直接插入排序,可以使用 “哨兵”。
原始数据越接近有序,排序速度越快。最坏情况下(数据逆序排序)。
实现排序的基本操作有两个,“比较” 序列中两个关键字的大小, “移动”。如果要提高查找速度,减少元素的比较次数和移动次数。
1.2 折半插入排序:二分法
减少了比较次数,不能减少移动次数。平均性能优于直接插入。
1.3 希尔排序:缩小增量,多遍插入排序
特点:
- 一次移动,移动位置较大,跳跃式的接近排序后的最终位置。
- 最后一次只需要少量移动。
- 增量序列必须是递减的,最后一个必须是1.
- 增量序列必须是互质的。
如何选择最佳 d 序列,目前尚未解决;最后一个增量必须是1,无除了1之外的公因子;不宜在链式存储结构上实现。
2. 交换排序
基于交换思想的排序。
2.1 冒泡排序
冒泡排序比较简单,但是效率较低。
n 个记录,总共需要 n-1 趟。第 m 趟需要比较 n-m 次。
2.2 快速排序
基本思想:通过一趟排序,将待排序记录分割成独立的两部分,其中的部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录进行排序,以达到整个序列有序。
具体实现:选定一个中间数作为参考,所有元素与之比较,小的调到其左边,大的调到其右边。中间数(枢轴) 可以是第一个数、最后一个数、最中间一个数、任选一个数等。
快速排序不是原地排序。由于程序中使用了递归,需要递归调用栈的支持,而栈的长度取决于递归调用的深度(即使不用递归,也需要使用用户栈)。
在平均情况下:需要 O(logn) 的栈空间。
最坏情况下:栈空间可达 O(n)。
快速排序是一种不稳定的排序。快排不适用于对基本有序或原本有序的记录序列进行排序(越乱越快)。
3. 选择排序
3.1 简单选择排序
基本思想:在待排序的数据中选出最大(小)的元素放在其最终的位置。
基本实现
- 首先通过 n-1 次关键字比较,从 n 个记录中找出关键字
最小
的记录,将它与第一个记录交换。 - 再通过 n-2 次比较,从剩余的 n-1 个记录中找出关键字
次小
的记录,将它与第二个记录交换。 - 重复以上操作,共进行 n-1 趟排序后,排序结束。
时间复杂度
- 移动次数
- 最好情况:已经排好序,移动次数为 0
- 最坏情况:逆序,每次都需要交换,移动次数为 3(n-1)
- 比较次数:无论待排序序列是什么状态,选择排序所需进行的 “比较” 次数都相同。
算法稳定性:简单选择排序是不稳定排序。
3.2 堆排序
堆的定义:若 n 个元素的序列 {} 满足 , 或者 , 。则分别称该序列 {} 为 小根堆 和 大根堆。
从堆的定义可以看出,堆实质是满足如下性质的 完全二叉树 :二叉树任一非叶子结点均小于(大于)它的孩子结点。
堆排序:若在输出 堆顶 的最小值(最大值)后,使得剩余 n-1 个元素的序列重又建成一个堆,则得到 n 个元素的次小值(次大值)……如此反复,便得到一个有序序列,这个过程称之为 堆排序。
实现堆排序需解决两个问题:
-
如何由一个无序序列建成一个堆?
单节点的二叉树是堆。 -
如何在输出堆顶元素后,调整剩余元素为一个新的堆?
对一个无序序列反复 “筛选” 就可以得到一个堆,即:从一个无序序列建堆的过程就是一个反复 “筛选” 的过程。
初始化所需时间不超过O(n)
排序阶段(不含初始化)
- 一次重新堆化所需时间不超过O(logn)
- n-1 次循环所需时间不超过O(nlogn)
堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复 “筛选” 上。堆排序在最坏情况下,其时间复杂度也为 ,这是堆排序的最大优点。无论待排序列中的记录是正序还是逆序排列,都不会使堆排序处于 “最好” 或 “最坏” 的状态。
4. 归并排序
基本思想:将两个或两个以上的有序子序列 “归并” 为一个有序序列。
4.1 2-路归并排序
在内部排序中,通常采用的是 2-路归并排序。即:将两个位置相邻的有序子序列 R[l…m] 和 R[m+1…n] 归并为一个有序序列 R[l…n]。
时间效率:O(nlog2n)
空间效率:O(n) 因为需要一个与原始序列同样大小的辅助空间。
归并排序是一个 稳定 的算法。
5. 基数排序
基本思想:分配+收集
也叫 桶排序 或 箱排序,设置若干个箱子,将关键字为 k 的记录放入第 k 个箱子,然后再按序号将非空的连接。
基数排序:数字是有范围的,均有 0-9 这十个数字组成,则只需设置十个箱子,相继按个、十、百…进行排序。
例如 {614, 738, 921, 485, 637, 101, 215, 530, 790, 306}
6. 外部排序
7. 各种排序方法比较
排序方法 | 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 | 空间复杂度 | 稳定性 |
---|---|---|---|---|---|
直接插入排序 | O() | O() | O() | O(1) | 稳定 |
直接插入排序 | O() | O() | O() | O(1) | 稳定 |
希尔排序 | O() | O() | ~O() | O(1) | 不稳定 |
冒泡排序 | O() | O() | O() | O(1) | 不稳定 |
快速排序 | O() | O() | O() | O() | 不稳定 |
直接选择排序 | O() | O() | O() | O(1) | 不稳定 |
堆排序 | O() | O() | O() | O() | 不稳定 |
归并排序 | O() | O() | O() | O(n) | 稳定 |
基数排序 | O() | O() | O() | O(n+m) | 稳定 |
7.1 时间性能
-
按平均的时间性能来分,有三类排序方法
-
时间复杂度为 O(nlogn) 的方法有:
快速排序、堆排序和归并排序,其中以快速排序为最好。 -
时间复杂度为 O(n^2) 的有:
直接插入排序、冒泡排序和简单选择排序,其中以直接插入为最好,特别是对那些对关键字近似有序的记录序列尤其如此。 -
时间复杂度为 O(n) 的排序方法只有:基数排序
-
-
当待排记录序列按关键字顺序有序时,直接插入排序和冒泡排序能达到O(n)的时间复杂度;而对于快速排序而言,这是最不好的情况,此时的时间性能退化为 ,因此是应该尽量避免的情况。
-
简单选择排序、堆排序、归并排序的时间性能不随记录序列中关键字的分布而改变。
7.2 空间性能
指的是排序过程中所需的辅助空间大小
- 所有的简单排序方法(包括:直接插入、冒泡和简单选择)和堆排序的空间复杂度为 。
- 快速排序为 ,为栈所需的辅助空间。
- 归并排序所需辅助空间最多,其空间复杂度为 。
- 链式基数排序需附设队列首尾指针,则空间复杂度为 。
7.3 稳定性
稳定的排序方法是指:对于两个关键字相等的记录,它们在序列中的相对位置,在排序之前和经过排序之后,没有改变。
- 当对多关键字的记录序列进行 LSD 方法排序时,必须采用稳定的排序算法。
- 对于不稳定的排序方法,只要能举出一个实例说明即可。
- 快速排序和堆排序是不稳定的排序方法。
关于排序方法的时间复杂度的下限
以上的几种排序方法,除基数排序外,其它方法都是基于 “比较关键字” 进行排序的排序方法,可以证明,这类排序法可能达到的最快的时间复杂度为 。基数排序不是基于 “比较关键字” 的排序方法,所以它不受这个限制。
可以用一棵判定树来描述这类基于 “比较关键字” 进行排序的排序方法。