排序算法刷题笔记【牛客网】

排序算法刷题记录，来自牛客网，主要是有些题目会去搜一下相关知识，这里就用来做笔记，类似错题本了。
会持续更新……

其实就是把45前面的排好了，然后45从后往前比较。
45前面的排列：15,23,38,54,60,72,96,45应该是在38和54之间，然而我做的时候只数到了54，忘了还要比较38<45才能确定45的位置。。。

哎，忘了选希尔排序。

堆排序（时间复杂度O(nlogn) ）的步骤就是：

a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

所以，下题选堆排序。
希尔排序是插入排序的改进版本，也称为缩小增量排序，把记录按下标的一定增量分组，对每组使用直接插入排序算法排序：