最简单的一集，算是开胃菜罢。
ps:图大部分是直接从 oi-wiki 上贺的。
目前大家用到的也就只有 \(sort\) ，归并和桶，但是初赛可能会考其它排序算法的思想和稳定性，所以还是要了解（真的会考吗）。
稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。
所以我们常用的 \(sort\) 是不稳定排序，如果真的有需求的话，可以用 STL 中的 stable_sort
放一张经典图在这：
初赛考排序也就能考点这个了，背过就行了。
表里没出现的不考
对于一个数列，我们从 \(1\) 枚举到 \(n\) ，对于每个 \(i\) ，找出 \(i\) 到 \(n\) 中最小的数与 \(a_i\) 交换（或者说是放到第 \(i\) 位）。
放张图：
过程：懒得打，直接贺 oi-wiki
它的工作原理是每次检查相邻两个元素，如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换。当没有相邻的元素需要交换时，排序就完成了。
经过 \(i\) 次扫描后，数列的末尾 \(i\) 项必然是最大的 \(i\) 项，因此冒泡排序最多需要扫描 \(n-1\) 遍数组就能完成排序。
没有图。
**冒泡排序的最优时间复杂度为 \(O(n)\)，最坏时间复杂度和平均时间复杂度均为 \(O(n^2)\) **
可以想象成在打牌，每次拿到一张牌后，在已有的手牌中从前往后找到第一个大于它的牌并放到它前面。
这回有图了：
插入排序最优时间复杂度为 \(O(n)\) ，最坏时间复杂度和平均时间复杂度均为 \(O(n^2)\)。
人话：桶排。
图：
时间复杂度为 \(O(n+w)\) ，其中 \(w\) 代表待排序数据的值域大小。
评价是：不如写 sort 。
然后玩原神将小于哨兵数的数放在哨兵数的左边，大于它的放在右边，最后对两边继续递归排序。
容易看出，每次选择的哨兵数若为数列的中位数，则每次左右两边的数的数量相同，时间复杂度最优，为 \(O(n\ \log\ n)\) 。但如果选择的数为区间最值，相当于每次数列长度只减小了 \(1\) ，时间复杂度为 \(O(n^2)\) 。
所以不如写 sort
其实就是用堆排序，时间复杂度与堆相同，最好、最坏、平均时间复杂度都是 \(O(n\ \log\ n)\)，因为可以在原数组中建堆，所以空间复杂度为 \(O(n)\) 。
不讲，不会考（不备课还不知道有这俩）。
应 \(KinNa\) 的要求，不讲。
假的。
先贺一个oi-wiki的定义在这。
我们先选择一个 \(h\) 作为初始间距，然后就把可以把原数组分成 \(h\) 个序列，每个序列中的数在原序列中间隔均为 \(h\) 。
这么说可能不太好理解，画个图吧。
然后对每个所有进行插入排序，每次操作完后使 \(h\) 缩小一定范围 ，再重新分序列，直至 \(h=1\) 。
平均时间复杂度 \(O(n^{1.3})\)，最优复杂度 \(O(n)\) ，空间复杂度 \(O(1)\)。