排序
计数排序
-
计数排序是一种计算每个数字出现次数后做值域上的前缀和以对各元素排序的排序方式。
-
计数排序是一种非比较排序。
-
具体实现：依次枚举每个元素，将其丢进其关键字对应的桶里（这些桶的管辖范围都是
1 ，也可以认为计数排序就是桶排序的退化）。全部放置完毕后，做前缀和以求出每个元素的排名。 -
计数排序的复杂度为
O(n+w) ，其中w 为关键字值域大小。
基数排序
-
基数排序是一种对排序各元素的各个关键字依次排序的排序方式，或者说思想。
-
基数排序是一种非比较排序。
-
基数排序需要一种稳定算法来完成内层的对关键字排序。
-
具体实现：
-
枚举各个关键字并排序。
-
应当在枚举完毕后
k 个关键字后使得数组按照后k 个关键字有序。 -
具体来说，就是先对第
k 关键字排序，然后对第k-1 关键字稳定排序，以此类推。 -
正序倒也可以，但是需要的不是稳定排序而是分进不同的桶内，每个桶分别排序，带来的空间复杂度难以忽视。
-
-
实际使用中，内部排序算法通常为计数排序。此时有总复杂度为
O(\sum\limits_{i=1}^k(n+w_i)) ，其中w_i 为第i 关键字的值域大小（相当于做了k 次计数排序）。
std::sort 与 std::stable_sort
-
前者是内省排序：先用快排，分割次数过多时转局部堆排序防退化，当范围足够小时使用插入排序（注意这一步可能会严重增加比较次数，在
cmp 不是O(1) 时影响较大）。 -
后者在有额外空间的时候是严格归并排序，否则是最优原地后缀排序算法。请注意，这个名字很长的算法的复杂度是
O(n\log^2 n) 。
冒泡排序
-
冒泡排序的交换次数是总逆序对数。
-
和比较排序恰好相反，冒泡排序
k 次后，至少后k 个数字的位置是正确的。 -
冒泡排序
k 次后，i 处元素为[1,i+k] 间的最小值，除非它已经用于<i 的地方（即这个结论必须从前向后递推）。