图解九大基础排序算法
1、算法描述：
Step1：将待排序数组分为有序和无序两组（初始情况下有序组为第一个元素）
Step2：取出无序组第一个元素（First_unsorted）放入临时空间，将first_unsorted与有序组从最后一个元素开始进行比较，如果比有序组小，则将有序组中的该元素向后移一位，直到找到第一个比first_unsorted小的时候，将first_unsorted放入。至此，有序组++，无序组--。
Step3：重复step2，直到无序组数量为0.
算法结束。
2、适用情况分析：
稳定
数组，链表均可实现
空间复杂度O(1)
时间复杂度O(n2)
最差情况：反序，需要移动n*(n-1)/2个元素
最好情况：正序，不需要移动元素
数据量较小，较有序的情况下性能较好
3、（顺序版本）参考代码如下图所示：
4、链式版本代码如下图所示：
1、算法描述：
Step1：将待排序数组分为有序和无序两组（初始情况下有序组为空）
Step2：从左向右扫描无序组，找出最小的元素，将其放置在无序组的第一个位置。至此有序组++，无序组--；
Step3：重复Step2，直至无序组只剩下一个元素。
算法结束。
2、适用情况分析：
不稳定
数组，链表均可实现
空间复杂度：O(1)
时间复杂度：O(n2)
最坏情况：O(n2) 第一个元素为最大元素，其余元素正序，需要交换n-1个元素（如：4 3 2 1）
最好情况：O(n2) 正序，不需要交换元素
选择排序的最坏情况和最好情况下的实际没有太大区别。即选择排序对于原始记录的顺序不敏感。
3、参考代码如下图所示：
1、算法描述：
Step1：比较相邻的元素。如果第一个比第二个大，就交换他们两个
Step2：对每一对元素均进行此操作，经过一轮后最大的元素应位于最后一位
Step3：从第一个元素重复进行前两步，每一轮最后一个元素都不参与比较，进行n轮
算法结束。
2、适用情况分析：
稳定
大部分采取顺序，链式也可实现
空间复杂度O(1)
时间复杂度O(n2)
数据顺序对算法影响不大
3、参考代码如下图所示：
1、算法描述：
Step1：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序。
Step2：依次缩减增量再进行排序。
Step3：待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
算法结束。
因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序相较于前几种方法有较大的提升。
2、适用情况分析：
不稳定
采取顺序实现，对下标敏感
空间复杂度O(1)
时间复杂度O(nlogn)
步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。
Donald Shell 最初建议步长选择为N/2并且对步长取半直到步长达到1
已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,...)
3、参考代码如下图所示：
4、在网络上看到了简化版本的shell sort，也可作参考，如下图所示：
1、算法描述：
Step1：在待排序列中选取一个轴点（pivot），通常选取中间点
Step2：将轴点与其他元素进行比较，将比轴点小的元素放在轴点之前，比轴点大的元素放在轴点之后。至此，pivot已被排好序
Step3：对0-（pivot-1）和（pivot+1）-n分别递归进行上述两步。
算法结束。
2、适用情况分析：
不稳定。
顺序实现
空间复杂度：O(1)
时间复杂度：O(nlog2n)
最坏情况：O(n2)要排序数组基本有序，基准值每次取最大（最小）元素，退化为冒泡。
最好情况：O(nlog2n) 基准值两边元素个数基本相同.
3、参考代码如下图所示：
1、算法描述：
Step1：把待排序的列表划分为分成近似相等的两部分
Step2：分别将两个子列表排序（递归进行）
Step3：然后再合并成一个完整的列表
算法结束。
2、使用情况分析：
稳定
链式实现
空间复杂度：O(n)
时间复杂度：O(nlog2n)
最坏情况：O(nlog2n)
最好情况：O(nlog2n)
3、参考代码如下图所示：
1、算法描述：
堆的定义：堆是一棵完全二叉树或者是近似完全二叉树。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者的堆称为小根堆，又称最小堆。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。
Step1：建堆，序列分成无序和有序两组（初始有序为0）
Step2：取出堆顶最大的元素，与待排序列的最后一个元素作交换，至此，无序组--，有序组++，并对无序组进行堆调整
Step3：重复上述步骤，直至无序组仅剩一个元素
算法结束。
2、使用情况分析：
不稳定
顺序结构实现
时间复杂度：o(nlogn)
空间复杂度：o(1)
由于建初始堆所需的比较次数较多，不建议在数据量小的情况下使用
3、代码如下图所示：
1、算法描述：
LSD：
Step1：将待排序的元素按照最后一位进行分桶操作（桶按照最后一位排序从大到小）
Step2：按顺序将各个桶中的数据连接起来，形成新的序列
Step3：依次对新序列的倒数第二位至第一位进行上述两步操作
算法结束
MSD：
Step1：将待排序的元素按照最高位进行分桶操作
Step2：对每个桶的按照第二位进行再次分桶（递归进行）
Step3：进行至最后一位分桶操作完成后，对每个桶进行合并操作，得到有序序列
算法结束
2、使用情况分析：
稳定
链式实现
时间复杂度：假设在基数排序中，r为基数，d为位数。则基数排序的时间复杂度为O(d(n+r))
空间复杂度：在基数排序过程中，对于任何位数上的基数进行“装桶”操作时，都需要n+r个临时空间
数据量大时有明显优势，通常使用LSD法
3、MSD参考代码如下图所示：
4、LSD参考代码如下图所示：
1、算法描述：
对于一棵二叉查找树，中序遍历的序列即为有序序列。
因此，二叉查找树的插入过程也可以看成是排序的过程。即
Step1：将无序序列逐一插入二叉排序树。
Step2：对二叉排序树进行中序遍历
算法结束
2、适用情况分析：
不稳定
链式实现
时间复杂度：o（nlogn）
空间复杂度：o（1）
Tree sort比较适合于无序的序列，对于基本有序的序列效率较低
3、参考代码如下图所示：
