《漫画算法2: 小灰的算法进阶》第一章 排序算法进阶
什么是选择排序
选择排序：每一轮选出最小元素直接交换到左侧
选择排序时间复杂度：O(n^2)
选择排序空间复杂度：O(1)
选择排序具有不稳定性
什么是插入排序
插入排序：维护一个有序区，把元素一个个插入有序区的适当位置，直到所有元素都有序为止。
插入排序的优化
3与6进行比较，3<6，6复制到它的下一个位
3与5进行比较，3<5，5复制到它的下一个位
插入排序最坏的时间复杂度O(n^2)
插入排序的空间复杂度O(1)
什么是希尔排序
希尔排序：逐步分组进行粗调，再进行直接插入排序的思想上面示例中所使用的分组跨度（4，2，1），被称为希尔排序的增量，增量的选择可以有很多种。在示例中所用的逐步折半的增量方法，是Donald Shell在发明希尔排序时提出的一种朴素方法，被称为希尔增量。
希尔排序的优化
为了保证分组粗调没有盲区，每一轮的增量需要彼此“互质”，也就是没有除1之外的公约数。
其中最具代表性的是Hibbard增量和Sedgewick增量。
Hibbard的增量序列如下：
1, 3, 7, 15……
通项公式为2k-1
利用此种增量方式的希尔排序，最坏时间复杂度是O(n^(3/2))
Sedgewick的增量序列如下：
1, 5, 19, 41, 109……
通项公式为9×4k-9×2k+1或者4k-3×2k+1。
利用此种增量方式的希尔排序，最坏时间复杂度是O(n^(4/3))
希尔排序是不稳定排序
什么是归并排序
（p1，p2，p是三个辅助指针，用于记录当前操作的位置。）
由于1<2，所以把元素1放入大集合，指针p1和p各右移一位
归并排序的时间复杂度为O(nlogn)
归并排序的空间复杂度为O(n)
归并排序是稳定排序，两个值相同的元素在归并之后，左侧的元素仍然在左，右侧的元素仍然在右
基数排序
基数排序(Radix Sort)：把字符串元素按位拆分，每一位进行一次计数排序的算法
基数排序既可以从高位优先进行排序（Most Significant Digit first，简称MSD），也可以从低位优先进行排序（Least Significant Digit first，简称LSD）
基数排序的时间复杂度是O(k(n+m))
基数排序的空间复杂度为O(n+m)
基数排序是线性排序算法
小结
