[洛谷深基]第9章 排序v202102 - 图文

计数排序计数排序顾名思义，即统计每一个元素出现的次数，再按照顺序依次排列。数列中的元素就是“票”，而一个与元素取值范围相符的数组就是“票箱”。记??为数列长度，??为取值范围。需要??(??)的时间统计每一数值出现次数。之后再用??(??+??)的时间构造出结果数列，总时间??(??+??)。另外，需要????的额外空间作为票箱。优点：当??较小时，时间复杂度近似于??(??)，性能强大。缺点：当??远大于??时，时空复杂度均取决于??，得不偿失。取值范围为非整数时，无法实现。计数排序变种离散化计数排序若能将不可表示的数据范围（双向）映射到较小的整数集合上，则可以在映射后使用计数排序。这一映射过程称为离散化。桶排序将数列按数值区间（而非具体数值）划分为若干个桶。桶内采用其他排序算法。基数排序从低到高对每一个（X进制）位进行一次计数排序。这样，当高位有序时，所有低位均已有序。可以保证只使用X个桶。此处不要求掌握。选择/冒泡/插入排序现在我们开始玩牌。你要如何整理你的手牌呢？请翻至课本P131基于交换的排序方法我都是把相同的数字牌扣在桌面上来排序的！这不还是一种计数排序吗？没错，但是这样你的对手就可以通过观看牌桌上倒扣的牌堆推测你的牌型。所以你决定只通过交换的方式来排序。逆序对：假设排序应当是从小到大，如果有一对牌，前面的那张牌比后面的那张牌数字大，那么就是逆序对。基于交换的排序方法所谓交换，即数列元素两两比较；若顺序反了则对换二者位置。由于每一次交换逆序对数必然减少，持续交换必然可以完成排序，且具有不用到其他变量而直接在原数列中操作、额外空间复杂度??(1)的优点。考虑到元素两两间均需要互相比较，可以大致估计出，此类方法最坏时间复杂度均约为O(??2)。