多多重复，百炼成钢！！！

 

 要求升序-建大堆
 要求降序-建小堆

步骤：
 1.先找到最后一个节点，然后找到他的父亲a，在a在的堆（无序），通过向下调整把该堆调整为有序（大堆或小堆）
 2. 通过 i-- 找到父亲a的前一个节点b（也是另外一个堆的父亲-b），然后在父亲b所在的堆（无序）向下调整为有序
 3.迭代往根方向往上走-最后整个堆都有序（大堆或小堆）

向下调整

gap越大，直接插入排序就越快，反而不那么有序
gap越小，直接插入排序就越慢，反而更有序

思路：（要求升序）把第一个元素设为最小值从这里开始找，遍历一轮数组，若找到比最小值还小的元素（遍历元素里面最小的）则交换；

然后把第二个元素作为最小值从这里开始找，遍历......以此类推，到最后一个元素为止

时间复杂度-最坏（O（N^2)) 最好（O(N))

空间复杂度：O(1)

稳定性：好

1.优化：三数取中：三个数当中取个数值大小为中间值的值

  取出来的值作为keyi

霍尔排序：

R找比keyi小的值，找到则停下； L找比keyi大的值，找到则停下；   然后L和R交换，依次到最后碰面，把keyi和碰面时的值交换，完成排序。

最后返回碰面的下标

步骤：

先把key（left)所在位置作为坑位；

然后R先走，找到比keyi小的值则把该值填到坑位，然后该位置为新的坑位；

然后L走，找到比keyi大的值则把该值填到坑位，然后形成新的坑位；

以此类推，最后碰面时作为最后的坑位，把keyi填进去；

最后返回最后坑位的下标

步骤：

cur和prev一起走：如果cur遇到比keyi大的值则prev停下，则cur继续走，之后若遇到比keyi小的值则该值与prev所在的值交换；

以此类推，cur越界后prev停下，此时把prev所在值与keyi交换；

最后返回prev所在的下标

若需要需要把数组[9,8,7,6,5,4,3,2,1,0]进行升序排列：

先把下标为0 9push入栈（出栈顺序为9 0 - 对应区间为[0,9]）；

然后取left=0 right=9 并且都pop掉 然后对该区间[left,right]进行排序；

然后分为两个区间[0,4] 5 [6,9]；

然后把下标为 6 9push入栈，再把 下标为 0 4 push入栈 ；

然后取left=0，right=9 并且都pop掉然后对该区域[left,right]进行排序；

然后再分区间......

以此类推

停止排序： 要么剩下一个元素 要么元素不存在（越界）

---