图解九大基础排序算法

本篇经验将和大家介绍一下数据结构课程中常见的9大基础排序算法的算法描述、使用情况分析、参考代码等，希望对大家有所帮助。

2、适用情况分析：稳定数组，链表均可实现空间复杂度O(1)时间复杂度O(n2)最差情况：反序，需要移动n*(n-1)/2个元素最好情况：正序，不需要移动元素数据量较小，较有序的情况下性能较好

3、（顺序版本）参考代码如下图所示：

选择排序（selection Sort）

1、算法描述：Step1：将待排序数组分为有序和无序两组（初始情况下有序组为空）Step2：从左向右扫描无序组，找出最小的元素，将其放置在无序组的第一个位置。至此有序组++，无序组--；Step3：重复Step2，直至无序组只剩下一个元素。算法结束。

冒泡排序（Bubble Sort）

1、算法描述：Step1：比较相邻的元素。如果第一个比第二个大，就交换他们两个Step2：对每一对元素均进行此操作，经过一轮后最大的元素应位于最后一位Step3：从第一个元素重复进行前两步，每一轮最后一个元素都不参与比较，进行n轮算法结束。

2、适用情况分析：稳定大部分采取顺序，链式也可实现空间复杂度O(1)时间复杂度O(n2)数据顺序对算法影响不大

3、参考代码如下图所示：

2、适用情苄念上妒况分析：不稳定采取顺序实现，对下标敏感空间复杂度O(1)时间复杂度O(nlogn)步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。Donald Shell 最初建议步长选择为N/2并且对步长取半直到步长达到1已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,...)

3、参考代码如下图所示：

快速排序（Quick Sort）

1、算法描述：Step1：在待排序列中选取一个轴点（pivot），通常选取中间点Step2：将轴点与其他元素进行比较，将比轴点小的元素聚刁擞蛔放在轴点之前，比轴点大的元素放在轴点之后。至此，pivot已被排好序Step3：对0-（pivot-1）和（pivot+1）-n分别递归进行上述两步。算法结束。

归并排序（Merge Sort）

1、算法描述：Step1：把待排序的列表划分为分成近似相等的两部分Step2：分别将两个子列表排序（递归进行）Step3：然后再合并成一个完整的列表算法结束。

2、使用情况分析：稳定链式实现空间复杂度：O(n)时间复杂度：O(nlog2n)最坏情况：O(nlog2n)最好情况：O(nlog2n)

3、参考代码如下图所示：

2、使用情况分析：不稳定顺序结构实现时间复杂度：o(nlogn)空间复杂度：o(1)由于建初始堆所需的比较次数较多，不建议在数据量小的情况下使用

3、代码如下图所示：

2、使用情况分析：稳定链式实现时间复杂度：假设在基数排序中，r为基数，d为位数。则基数排序的时间复杂度为O(d(n+r))空间复杂度：在基数排序过程中，对于任何位数上的基数进行“装桶”操作时，都需要n+r个临时空间数据量大时有明显优势，通常使用LSD法

3、MSD参考代码如下图所示：

树排序（Tree Sort）

1、算法描述：对于一棵二叉查找树，中序遍历的序列即为有序序列。因此，二叉查找树的插入过程也可以看成是排序的过程。即Step1：将无序序列逐一插入二叉排序树。Step2：对二叉排序树进行中序遍历算法结束

2、适用情况分析：不稳定链式实现时间复杂度：o（nlogn）空间复杂度：o（1）Tree sort比较适合于无序的序列，对于基本有序的序列效率较低

3、参考代码如下图所示：