常见排序算法及其时空复杂度
一、 常见排序算法说明
1、 冒泡排序
外层循环i次, 内层循环i-1次, 从左到右, 两两对比, 大的放后。
2、 选择排序
外层循环i次, 内层循环i-1次, 每次把最小的放在前面。
3、 插入排序
寻找插入位置, 将元素后移, 待排序元素插入已排序数组。
4、 希尔排序
插入排序在几乎有序情况下的时间复杂度趋近O(n), 所以利用缩小增量分区法进行分区, 每个分区内部进行插入排序。 直到增量变为1。
(缩小增量分区法: 数据规模依次减半, 交错进行分区, 如123456789, 首次分区为13579和2468)
5、 归并排序
利用二分法拆分到每个分区直到只有一个元素, 然后进行比较合并。
6、 快速排序
先设置中轴, 将大数放后, 小数放前, 然后对中轴两侧的数据进行递归。
7、 堆排序
利用堆数据结构进行选择排序。
8、 计数排序
如果数据量大且范围较小, 适合用计数排序。 新建一个计数数组，遍历待排序数组, 计数数组中下标为待排序数值的元素自增, 遍历完后依次取出。
9、 桶排序
设置桶个数, 利用映射函数将待排序数组放入桶中, 对每个桶进行插入排序。
（映射函数：取最大最小值的差为数据范围进行平均分区，每个数值将一一映射在每个分区）
10、基数排序
从计数排序到基数排序, 每次都做了优化, 基数排序的适用范围最广。设置一个二维数组, 10行n列。10行应该就是基数的精髓所在，10进制数的基数就是10。二维数组中第i行为待排序数个位上数值的元素放入i行第j列， j自增， 遍历完后依次放回原数组，继续遍历十位、百位直到最高位。 遍历结束，放回原数组后则完成排序。
二、 时空复杂度一览表
冒泡排序平均：因为需要两两对比, 所以对比次数为求组和An2, 如果进行标志位优化, 并且加上概率, 时间复杂度为O（An2/2）
最好：顺序+标志位优化
最坏：逆序
空间：O(1)选择排序
时间复杂度一致为O(n^2)
空间：O(1)插入排序
平均：同冒泡
最好：顺序
最坏：逆序
空间：O(1)希尔排序
时间复杂度证明较为复杂, 因为其交换消除的逆序对不止一个, 所以突破了O(n^2)
空间：O(1)归并排序
归并如果用递归来分析, 递下去用logn层, 归回来也用logn层, 归回来的时候需要处理n次合并, 一共(n+1)logn, 即O(nlogn)
空间：O(n)快速排序
同归并排序算法一样, 但是快排在取中轴的时候不一定能取到1/2, 所以时间复杂度在O(nlong)~O(n^2)之间
空间：递归调用，每层为O（1），共logn层，所以空间复杂度为O（logn）堆排序
首次堆化时间复杂度O(n), 更改堆元素后重建堆时间复杂度为O(nlogn), 所以时间复杂度为O(nlogn)
空间：O（1）计数排序
计数排序的时间复杂度为O(n+k), 其中n为数据规模, k为数据范围、因为只用遍历两次所有数据即可排序, 所以时间复杂度为O(n+k)
空间：O（k）桶排序
最好的情况是被均匀地分配到每个桶里面, 最坏的情况是被分配到极个别桶里面, 甚至是一个里、所以时间复杂度为O(n+k)~O(n^2)
空间：O（n+k）, 因为需要创建k个桶，以及N个元素的数组基数排序
时间复杂度为O(n*k), n为数据规模, k为最大元素的位数.
空间：O（n+k）, 其中k为桶的数量，需要分配n个空间的数组.