企鹅
镇楼

一、冒泡排序( PopSort )总结
作为一种初学者最早接触的排序之一，冒泡排序有着许多优势,比如说十分的newbie-friendly.
1.算法原理
不断扫描序列，一旦两个元素不满足偏序关系则交换两个元素.
偏序关系: ∀ 0 < i < j < n ,A(i) < A(j)
算法命名: 由于形如让气泡浮出水面的方式而得名
2.算法的VB实现
一个显然的优化，前面已经排好序的部分可以不扫描,这样可以让运行时间减半
所以可以对循环部分做以下修改
3.算法分析:
时间复杂度: O(n^2)
时间常数: 低( 约为 1/2 )
空间复杂度: O(n) + O(1)
(空间复杂度表示方式 : A(静态空间) + B(运行时空间) )
实现复杂度:极低
主要优势: 空间小，常数小，实现简单
主要劣势: 时间复杂度较劣
4.算法应用:
适用数据类型: 广适(即适用所有可以比较大小的数据类型)
在工业中多被快速排序取代.
在一些需要开发效率的小程序或数据量不大的地方被使用.
在空间要求严格的地方被使用

二.选择排序( SelectSort )总结
作为一种初学者最早接触的排序之一,选择排序有着许多优势,比如说更容易理解.
1.算法原理
每次暴力遍历整个数组找到数组最小值然后放入答案数组的第一个，
并把该数字从原数组中抹除(?)
抹除:不管使用任何手段(?),反正使得该元素不被再次计入答案即可
任何手段:
- 使用标记 代价( 时间 * 2,空间 + O(n) )
- 赋值为无穷大 代价( 时间 * 2 )
- 使用链表 代价( 空间 + O(n) )
- 使用Swap 代价()
2. 算法实现
为了防止初学者不适,我直接使用代价最小的实现(懒)
3. 算法分析
时间复杂度: O(n^2)
时间常数: 较低( 约为 1/2 )，但是由于玄学原因大于PopSort
空间复杂度: O(n) + [ O(1) - O(n)
实现复杂度:低
主要优势: 容易理解
主要劣势: 时间复杂度较劣，实现\常数 均劣于PopSort
4. 算法运用
适用数据类型: 广适(即适用所有可以比较大小的数据类型)
在工业中多被冒泡排序取代.
一般适用于基础数据类型.
其中寻找最大值的方法被日常使用.

支持一下

五、堆排序
作为最无脑的O(n * logn)的排序，堆排序有话要说
1.算法原理及实现
由于楼主想偷懒，就直接搬自己以前发的帖子了
https://tieba.baidu.com/p/5383563508?pid=113833917020&cid=0#113833917020
2.算法分析
时间复杂度: O(n * logn)
空间复杂度: O(n) + O(n)
常数: 较大,大于MergeSort
优势: 无脑
劣势: 常数大
3.堆排序的特质:
虽然堆排序十分无脑，但是无脑有无脑的好
由于堆排序使用的高级(?)数据结构,所以他可以支持带插入的排序，
即可以在排序后加入新的元素并使得其有序.
在这一点上，堆排序和归并排序就吧快排甩开了一条街

以上五大基本排序

六、高级数据结构排序
作为不正经的排序算法，高级数据结构排序对堆排序能进入五常表示很不服
可以用于排序的高级数据结构:
动态开点权值线段树,treap,fhq treap,splay,替罪羊树,宗法树,01trie
2.算法分析
时间复杂度: O(n * logn)
空间复杂度: O(n) + [ O(n) , O(n * logn) ]
常数: [较小 - 很大]
优势: 无脑且强大
劣势: 代码实现长，且不实用
2.5.代码实现(以后挑几个补上)
3.高级数据结构维护序列的强大之处
相比堆而言，这些数据结构不仅支持插入，而且支持删除和修改，
并且可以有效的查询更多的有序序列上信息，例如前k大的和

楼主，这些算法就靠你了，都是c的，本来还想vb化一下，无奈技术不够，顶顶顶

来处在这

七,可持久化数据结构排序
做为并没有什么意义的排序，只是来凑个数字(我保证后面的排序认真讲)
可以用于排序的高级数据结构加入可持久化:
可持久化权值线段树,可持久化01trie
使得我们可以记录数列的历史状态(并没有卵用)
1.算法分析
时间复杂度: O(n * logn)
空间复杂度: O(n) + O(n * logn)
常数: 很大
优势: 无
劣势: 代码实现长，且不实用
1.5.代码实现(不存在的)

八、桶(鸽巢)排序( Pigeonhole sort )总结
咕咕咕~
1.算法原理
前置技能: 桶( bin ) ?
桶 : 一个由数组模拟的数据结构，支持以下标为关键字O(1)修改、查询
> 实例: 比如我们要查询一个序列中是否出现9，我们可以在扫描到9的在9号桶上打上标记(即选择排序中的标记)
> 例题: https://www.luogu.org/problemnew/show/P1047
桶排序: 使用桶的排序
> 原理: 由于桶的下标离散有序,所以我们可以对每个元素的打上标记使得数列有序,然后扫描桶即可
> 例题: https://www.luogu.org/problemnew/show/P2824
>>Tip:这个题目本来正解应该是线段树，由于桶排序实在太优秀，就O(n^2)过掉了
2.算法实现及优化
最普通的写法
显然的优化1:
如果保证原数组不重复，我们可以使用bitset(?)代替桶
优化 : 运行时空间 * (1/32) , 时间常数小幅度降低
bitset: 由于桶使用Int32(32bits),而记录的有效信息只有很少(1bits),
我们可以考虑充分利用空间，将整数的每一位虚拟成一个boolean类型即可.
一个简单的bitset的VB实现，长度只有32，想要应用的同志请自行魔改
显然的优化2:
显然如果值差距过大时，很多的空桶是不必要的，所以我们可以按值域分块,对于无效的块可以直接skip掉
很容易知道当 块大小 = sqr(V) (?) 时最优 (?)
V : 值域大小
证明: x + (V/x) 在 x = sqrt(V)时有最小值
3.算法分析
时间复杂度: O(V)
空间复杂度: O(n) + [O(V) - O(V ^ (1/2)) ]
常数: 极小
优势: 理解简单,衍生运用多
劣势: 消耗空间大
4.算法运用
各种桶相关的骚操作,
推荐例题,楼主出的:https://www.luogu.org/problemnew/show/U40356

九、基数排序( RedixSort )总结
作为一种不基于比较而基于数字的排序，基数排序由桶排序发展而来
1.算法原理:
因为桶排序的速度会因为值域的扩大而劣化，所以我们按位考虑，
把所有数根据最高位分桶然后桶内排序。
例如，对于数组 11,12,15,23,31,22
我们按十位可以分成三个桶
1 : 11,12,15
2 : 22,23
3 : 31
这样他们十位就是有序的了，再考虑个位，就会发现不行，原来十位的限制就被打破了，而十位的权重大于个位，所以我们反过来考虑，先按个位分桶排序，然后再按十位排序，然后再更高位，由于桶内部不会破坏原来的顺序，这样，我们就可以轻松排序了，时间复杂度为O( n * C ),C为层数,由于C = log10V,所以理论复杂度并没有比分治的排序优秀，所以我们可以考虑优化,以10为底对于Int32 2e9 的值域来说太过于浪费了.我们考虑以65536为底，则只需要两层即可完成排序,代码如下
2.算法实现及优化
65536为底的基数排序
具体实现理解需要些基础的数据处理功底.而除非当面讲，我也难以讲清楚.所以大家多自己研究吧.
优化:缓存优化
由某著名Oier 王逸松 提出,当 Redix = 255 时,该数组能完美装入缓存，则可以极大的优化速度
虽然 256 ^ 4 才能覆盖In32的值域，但是由于缓存的OI速度超过为内存的10倍，所以在卡常数的时候有奇效
有兴趣的同学可以自己验证一下
3.算法分析
时间复杂度: V很小时 近似O(n)
时间常数: 小
空间复杂度 O(n) + O(n)
优势: 时间复杂度低
劣势: 只能运用于整数
4.算法运用
主要运用于空间不敏感但时间复杂度要求高的场合
不易于比较的多关键字排序
衍生运用1: 后缀排序
例题: https://www.luogu.org/problemnew/show/P3809
题意: 给定字符串S,求所有后缀的排名
倍增以后题目就简化为双关键字的排序，时间复杂度要求高，所以使用基数排序降至O( n*log2n )
衍生运用2: 后缀自动机
例题: https://www.luogu.org/problemnew/show/P3804
由于需要对子串的出现次数排序，而时间复杂度要求O(n)，所以使用基数排序解决.
P.S.写的好累啊.为什么没有人捧场呢？

捧场！！！

支持优质学术讨论贴~

感谢各位大佬的支持，由于楼主昨天去考试了，所以没有更新.先fix一下前面的坑.
十、插入排序( InsertionSort )
作为三大初学者排序之一，他是最容易被忘记的。(反正我是忘了的)
1.一句话算法思路
就是把每个元素插入有序数据结构(比如queue,heap)，然后就完了.严格意义上来说堆排序属于插入排序.
2.代码实现
一个终于放假回家获得正宗IDE的楼主.
3.算法分析
对比冒泡排序，insertSort显然常数要小一些
关于常数: 由于期望下插入的数字要遍历1/2个有序数列，所以期望常数为1/4
时间复杂度: O(n) - O(n^2)
空间复杂度: O(n) + O(1)
如果你想外接链表实现的话就会 O(n) + O(n)，但是时间常数又会降低一些,好像.
4.优化 - 希尔排序( ShellSort )
其实楼主最开始的计划里边是没有这两排序的，因为楼主甚至不知道它们的存在，然后简单学了一下。
其实希尔排序就是多次分组插入排序，组距依次递减为1，由于插入时间复杂度是不定的，取决于期望遍历长度，我们考虑跳着分组，然后就可以让其有概率一次跨过许多元素，使得减少遍历次数。
但是在现实中希尔排序很少运用·所以不详细展开,只留下实现
由于分组的原因，期望时间复杂度降至O(n * logn) - O(n ^ (4/3)),证明 ?
证明:不会
.