排序

插入排序

直接排序实际上就是进行比较后一步步替换

空间复杂度为O(1)

时间复杂度为O(n^2)-->两个嵌套for循环（平均）

稳定性 稳定 （遇到相同数字，相对位置保持不变）

希尔排序

希尔排序是通过一个常数d作为增量，然后对于相隔d个增量的记录作为子表进行排序，经过几次排序，使得整个表格基本有序后，对全体进行一次排序即可

因为同样使用常数个辅助单元，所以空间复杂度为o(1)

时间复杂度依赖于增量d，一般来说是不确定的，所以一般我们不去考虑

最后两个相同数字的相对位置也不能保证，所以稳定性也是不稳定的

交换排序

冒泡排序

不做解释，一一交换

空间 O(1)

时间O(n^2)

快速排序

快速排序是选取一个固定数，通常为第一个数，将小于这个数的跟不小于这个数的值进行排序，然后依次进行，是一个递归的过程

所以

空间复杂度是O(log_2n)

时1间复杂度是O(nlog_2n)

稳定性为不稳定

快速排序是所有内部排序算法中平均性能最优的算法

但是并不适用于本身就已经有了一定顺序的序列进行排序

选择排序

简单选择排序

就是遍历每个元素，在遍历到第i个元素时，选择从i到n的所有元素中最小的一个，将其与第i个元素进行交换

空间复杂度为O(1)

时间复杂度为O(n^2)

稳定性为不稳定

堆排序

对于二叉树的排序结果，我们可以根据根节点存放的是最大结点还是最小结点将堆分为大根堆与小根堆

对于大根堆小根堆的构造，都是从n/2开始进行的

对于堆的删除操作，就是将栈顶元素输出后再次进行构造

对于堆的插入操作，我们将其放入栈尾，再次进行构造

空间复杂度O(1)

时间复杂度O(nlog_2n)

稳定性 不稳定

归并排序

归并排序是将两个或两个以上的有序表组成一个新的有序表

例如二路归并排序，就是将元素两两组合并进行排序

空间复杂度是O(n)

时间复杂度是O(nlog_2n)

稳定性 为稳定

基数排序

不基于比较与移动进行排序，而是基于关键字各位的大小进行排序

空间效率 O(r)

时间复杂度O(d(n+r))

稳定性 稳定

各种排序算法的比较