各种排序算法的再整理

各种排序算法的再整理

插入排序：就是创建一个有序序列，然后将每个数插进去n2

折半插入：就是创建一个有序序列，然后每次折半的寻找这个插入位置n2（因为找到之后，还是要从那个位置移动数组）最好情况on

希尔排序：根据增量进行排序，增量是多少就有几个组，然后先将这组利用插入排序排好，然后增量/2并向下取整复杂度：on1.3（平均）

最好：on 最坏：on2

不稳定

冒泡排序：每轮从后往前以此比较相邻两个，逆序交换

快速排序：每次找到一个枢纽，利用左右指针来寻找比枢纽小和大的元素，分别放左边和放右边（具体方法为初始有左空位，然后从r开始减少，直到遇到比枢纽值小的数，然后放入l指针位置，反过来执行，直到指针重合，放入枢纽），然后递归完成左右区间排序。

稳定

简单选择排序：每轮选最小的

堆排序：复杂度为on+nlogn

先进行建堆，从非叶子结点开始，看是否大于左右子节点，如果均小于不变，反之调整，将大的子节点与小的父节点交换，调整后要再次检查调整的子节点；

然后进行排序，排序是每次将堆顶与目前数组长度的最后一个节点交换，交换后重复如上调整，同时需要维护数组长度-1；

归并排序：我们进行logn轮的归并操作，将n个单独的子序列，不断翻倍的进行归并。

两个子序列进行归并的方式就是：双指针，选出当前更小的节点，共n次。

基数排序：每轮对一位进行排序

稳定

最大位数*（要排的数个数+桶数）