各种排序算法的再整理
各种排序算法的再整理
插入排序：就是创建一个有序序列，然后将每个数插进去n2
折半插入：就是创建一个有序序列，然后每次折半的寻找这个插入位置n2（因为找到之后，还是要从那个位置移动数组）最好情况on
希尔排序：根据增量进行排序，增量是多少就有几个组，然后先将这组利用插入排序排好，然后增量/2并向下取整复杂度：on1.3（平均）
最好：on 最坏：on2
不稳定
冒泡排序：每轮从后往前以此比较相邻两个，逆序交换
快速排序：每次找到一个枢纽，利用左右指针来寻找比枢纽小和大的元素，分别放左边和放右边（具体方法为初始有左空位，然后从r开始减少，直到遇到比枢纽值小的数，然后放入l指针位置，反过来执行，直到指针重合，放入枢纽），然后递归完成左右区间排序。
稳定
简单选择排序：每轮选最小的
堆排序：复杂度为on+nlogn
先进行建堆，从非叶子结点开始，看是否大于左右子节点，如果均小于不变，反之调整，将大的子节点与小的父节点交换，调整后要再次检查调整的子节点；
然后进行排序，排序是每次将堆顶与目前数组长度的最后一个节点交换，交换后重复如上调整，同时需要维护数组长度-1；
归并排序：我们进行logn轮的归并操作，将n个单独的子序列，不断翻倍的进行归并。
两个子序列进行归并的方式就是：双指针，选出当前更小的节点，共n次。
基数排序：每轮对一位进行排序
稳定
最大位数*（要排的数个数+桶数）