type
status
date
slug
summary
tags
category
icon
password
这节课是算法竞赛系列的第 7 讲，从 C++ 基础过渡到算法与数据结构的学习，主要内容是算法复杂度与排序算法入门。
📝 课程大纲
算法复杂度
时间复杂度
- 时间复杂度判断
- 时间复杂度排序
- 降低时间复杂度的必要性
空间复杂度
- 数据类型占用空间
- 数组占用空间
排序算法
基础排序算法
- 选择排序
- 插入排序
- 冒泡排序
高级排序算法
- 快速排序
- 归并排序
- 堆排序
特殊排序算法
- 计数排序
- 基数排序
- 桶排序
- 希尔排序
- 锦标赛排序
- Tim 排序
🤗 整理归纳
算法复杂度
请参考《算法竞赛入门教程》。
排序算法
排序算法（Sorting algorithm）是一种将一组特定的数据按某种顺序进行排列的算法。排序算法多种多样，性质也大多不同。
常见排序算法可以分为两大类：
- 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 ，因此也称为非线性时间比较类排序。
- 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
排序算法的稳定性：稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。拥有稳定性这一特性的算法会让原本有相等键值的纪录维持相对次序，即如果一个排序算法是稳定的，当有两个相等键值的纪录 和 ，且在原本的列表中 出现在 之前，在排序后的列表中 也将会在 之前。
- 稳定排序算法：基数排序、计数排序、插入排序、冒泡排序、归并排序。
- 不稳定排序算法：选择排序、堆排序、快速排序、希尔排序。
选择排序
Selection Sort
像挑水果，每次都从剩下的里面挑出最大（最小）的放到一边。
稳定性：选择排序是一种不稳定的排序算法。
时间复杂度：选择排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 。
插入排序
Insertion Sort
像整理扑克牌，每抓一张牌都插入到手中已经排好序的牌里。
稳定性：插入排序是一种稳定的排序算法。
时间复杂度：插入排序的最优时间复杂度为 ，在数列几乎有序时效率很高。插入排序的最坏时间复杂度和平均时间复杂度均为 。
冒泡排序
Bubble Sort
像水中的气泡上浮，大气泡不断往上冒，最终大的都浮到了上面。
稳定性：冒泡排序是一种稳定的排序算法。
时间复杂度：在序列完全有序时，冒泡排序只需遍历一遍数组，不用执行任何交换操作，时间复杂度为 。在最坏情况下，冒泡排序要执行 次交换操作，时间复杂度为 。冒泡排序的平均时间复杂度为 。
快速排序
Quick Sort / Quicksort
像整理衣物，先按大小分成两堆，再分别整理每一堆。
稳定性：快速排序是一种不稳定的排序算法。
时间复杂度：快速排序的最优时间复杂度和平均时间复杂度为 ，最坏时间复杂度为 。
在实践中，几乎不可能达到最坏情况，而快速排序的内存访问遵循局部性原理，所以多数情况下快速排序的表现大幅优于堆排序等其他复杂度为 的排序算法。
归并排序
Merge Sort
像运动会比赛，选手先分组比赛，获胜者再互相比，最后决出名次。
稳定性：归并排序是一种稳定的排序算法。
时间复杂度：归并排序的时间复杂度在最优、最坏与平均情况下均为 。
空间复杂度：归并排序可以只使用 的辅助空间，但为便捷通常使用与原数组等长的辅助数组。
堆排序
Heap Sort
像公司晋升，总是把最优秀的人提拔到最高位置。
稳定性：堆排序是一种不稳定的排序算法。
时间复杂度：堆排序的最优时间复杂度、平均时间复杂度、最坏时间复杂度均为 。
空间复杂度：由于可以在输入数组上建立堆，所以这是一个原地算法。
计数排序
Counting Sort
像给学生按年龄分组，数一下每个年龄有多少人，然后排好。
稳定性：计数排序是一种稳定的排序算法。
时间复杂度：计数排序的时间复杂度为 ，其中 代表待排序数据的值域大小。
基数排序
Radix Sort
像整理扑克牌，先按花色分，再按点数分，最后合在一起。
稳定性：如果对内层关键字的排序是稳定的，则 MSD 基数排序和 LSD 基数排序都是稳定的排序算法。
时间复杂度：每一次散列需要对每个元素进行分配，即 次操作，最多进行最大的数的位数轮散列分配，即 轮，所以时间复杂度为 。
空间复杂度：基数排序需要的额外空间为 ，其中 为待排序集合大小， 为 （无负数元素）或 （有负数元素）。
桶排序
Bucket Sort
像整理衣服，把不同尺码的衣服放到不同的篮子里，再分别整理。
稳定性：如果使用稳定的内层排序，并且将元素插入桶中时不改变元素间的相对顺序，那么桶排序就是一种稳定的排序算法。由于每块元素不多，一般使用插入排序。此时桶排序是一种稳定的排序算法。
时间复杂度：桶排序的平均时间复杂度为 （将值域平均分成 块 + 排序 + 重新合并元素），当 时为 。桶排序的最坏时间复杂度为 。
希尔排序
Shell Sort
像整理图书馆的书，先按大类大致分类，再细分，最后微调。
稳定性：希尔排序是一种不稳定的排序算法。
时间复杂度：希尔排序的最优时间复杂度为 。
希尔排序的平均时间复杂度和最坏时间复杂度与间距序列的选取有关。设间距序列为 ，下面给出 的两种经典选取方式，这两种选取方式均使得排序算法的复杂度降为 级别。
- 命题 ：若间距序列为 （从大到小），则希尔排序算法的时间复杂度为 。
- 命题 ：若间距序列为 （从大到小），则希尔排序算法的时间复杂度为 。
锦标赛排序
Tournament Sort
像篮球锦标赛，所有球队先分组对战，胜者晋级，最后决出冠军。
稳定性：锦标赛排序是一种不稳定的排序算法。
时间复杂度：锦标赛排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 。它用 的时间初始化「锦标赛」，然后用 的时间从 个元素中选取一个元素。
空间复杂度：锦标赛排序的空间复杂度为 。
Tim 排序
Timsort
像整理衣柜，零散衣服快速整理，已经叠好的衣服不动，最后分类合并放好。
稳定性：Timsort 是一种稳定的排序算法。
时间复杂度：Timsort 的时间复杂度取决于数据的有序性：
- 最优情况：当数据已经有序或近似有序时，算法识别出的 Run 长度接近 ，归并次数减少，复杂度趋近于 。
- 最坏情况：在数据完全无序的情况下，每一个 Run 的长度都接近 ，因此需要 次归并，每次归并的代价为 ，总复杂度为 。
排序算法归纳
🔗 参考链接
- 作者:DrimTech
- 链接:https://drim.cc/online-class-11
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
相关文章
