堆排序、希尔排序

考研数据结构手记：堆排序、希尔排序

希尔排序，又叫做缩小增量排序

考研：一般考一趟希尔排序的序列

选择步长，步长是从当前数的下一个数开始数的，步长是几，就会分几组。最后一次是做直接插入排序。

插入类排序：直接插入排序，折半插入排序，希尔排序。

堆排序：

堆主要分为大顶堆和小顶堆，其实就是完全二叉树

题目是这么出的，给一个序列，让我们建立一个小顶堆。

1.我们首先把这个序列写成完全二叉树，然后开始取最后一个非叶结点（|n/2|这个要向下取整-1），其实也就是找到最后一个非叶子结点，因为其他是叶子结点，它已经符合堆的定义了，所以不用理他了。

2.所以我们只需要从最后一个非叶子结点到第一个结点依此进行筛选就可以建立堆了。

For(j=n/2;j>=1;j--)

Heap_adjust(R,j,n);

比如我们建立小顶堆，首先指向最后一个非叶子结点，看它的左右孩子是不是比它要小，是的话，跟其中最小的一个孩子交换，ok，完成。指针--，上移一个指针，再看它的左右孩子，跟最小的交换，ok，再移动指针，这时候注意，这个结点有孩子的孩子的孩子。。。所以，当我们把这个结点跟它的小孩子交换后，要注意，交换后是否符合堆定义，时刻进行调整。以此类推。

以上是建立小顶堆的过程。

广工历年831仅考过建立小顶堆，未考过堆排序

下面进行堆排序。

最后一个图，是根据上面方法建立好的大顶堆，下面进行堆排序。

首先将98输出，以序列最后一个结点记录作为新的跟结点，而原来堆的左右子树都是堆，则筛选一次就可以成为堆。

堆排序时间复杂度：O(nlog2n),空间复杂度：O(1)