旧金山大学的数据结构与算法在线动效：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

①时间、空间复杂度。

②稳定性：若是原本相同的两个数字一个前一个后在进行排序之后，两个数字发生了对调，此时可以说明其是不稳定的，若是没有发生对调则表示其是稳定的。

对于外部排序，若是数据太多则需要一批一批去读取到内存中来进行排序。

算法思想：每次将一个待排序的记录记录按其关键字大小插入到前面已排好序的子序列当中，直到全部记录插入完成。

核心代码案例举例：

①插入76

例如当指针移动到76的时候，我们需要依次和之前的数字进行比较，若是一旦有个数字是>76，则进需要进行移动：

最终就插入到如下图位置：

②插入27

朴素代码实现：

带哨兵的代码实现：数组多出一个位置来存储哨兵，之后将每次比较的元素放到哨兵位置来进行比较，可以省去一个比较条件

最好情况：O(n)

最坏情况：O(n2)

思路：针对于当前元素找到之前排序数序列中要插入的位置原本是从后往前，现在则可以在之前序列中使用二分查找。

由于中间过程移动元素的次数没有改变，所以时间复杂度依旧是O(n2)。

时间复杂度依然为O(n2)，在链表中我们无法来进行使用二分，但是在对于移动元 素的次数变少，但是关键字对比数量依旧为O(n2)：

叫做希尔的发明的，是插入排序的优化。

我们对下方来进行希尔排序：

根据每趟d产生的子表，我们来对其进行排序：

接着第三趟，此时当前的序列已经达成了一个基本有序的情况：

最后进行一次直接插入，即可完成排序：

注意：在考研中常常会自己去定义增量d的大小，有可能是3。

时间/空间复杂度

在最坏情况下，d=1时，则可能出现最坏时间复杂度O(n2)

稳定性

注意：希尔排序实现只能基于顺序表，不适用于链表！

每一趟可以找对应区间中最小的那个值放到最前面：

若是在一趟过程中没有出现交换的情况，那么表示当前序列已经是有序的了。

第一趟的过程就是从后往前依次进行比较，将小的元素进行往前交换，直到整个序列中最小的元素移动到第一个位置：

之后的每一趟都是这个思路，不断的将最小的值向前冒泡：

其中的flag就是表示当一趟过程比较大小中没有出现交换情况，那么表已经有序即可以退出：

稳定性：冒泡排序算法是稳定的！

时间与空间复杂度：

在对应的排序过程中，考研试题会去比较移动元素或者交换次数，一定要会懂得区分！！！

注意：对于链表可以从前往后依次进行对比，将更大的元素往后移动进行交换，最终最大的元素就会往后冒。

每一次都会使一个中间元素确定它的最终位置

首先选择一个枢纽（可选择开头的一个或者随机），定义一个low以及high指针方便之后来进行填入数据：

由于我们的枢纽是49，那么对于左右两边我们要分别找到左边=49的所有值：

首先从high开始，4978，此时将其进行交换：

③接着继续向前进行处理17：

通过检查发现右孩子最大，则17与45进行交换，此时同样以45为根节点即符合“大根堆”：

④接着继续向前处理53，由于右孩子更大，则跟右孩子进行互换

互换之后，可以看到当前这棵树已经构成了大根堆：

思路：基于选择排序的思想，每一趟将堆顶元素加入到有序子序列（将最大的堆顶元素与最后一个位置进行交换，接着去调整剩余n-1个为大顶堆）。

第一趟：将堆顶最大值与最后一个位置进行交换，并进行下坠节点构成大顶堆

①将堆顶最大值与最后一个位置进行交换

此时堆顶元素是最大值，那么我们将最大的堆顶元素与最后一个位置值进行交换，此时就将最大值找到并添加到最后

此时87这个数值位置就无需再改变了！

接下来我们将除了87的看做是一个堆来继续进行：

注意此时上面画圈的已经不是一个大根堆，此时我们则需要对09这个值来进行下坠调整：

②进行下坠节点构成大顶堆，将09元素值进行不断下坠

首先其右孩子是最大的，则跟其进行互换：

此时还没有下坠到最后一层，又当前左孩子是最大的，来进行交换，此时09下坠调整已经结束：

此时当前除了87的堆已经再次构成大根堆：

OK，此时完成了第一趟处理操作！！！

步骤二：进行第二趟的处理，将堆顶元素与堆底元素进行互换，接着再次构建大顶堆

此时完成交换，此时大顶堆中最大的元素再此放置到了最后一个位置：

此时78、87已经完成了排序，不再参与到之后的大跟堆排序当中！

接着我们对53为根节点的堆来进行调整为大顶堆：

首先53与65进行互换：

接着由于只有一个左孩子参与到大顶堆调整中，而9=最大节点，若是已经最大，那么表示无需进行调整，若是不是最大，则需要将最大的节点放置到当前的k位置上，并且调整当前指针指向下方的一个比其小的节点。

接着我们继续将交换过后的节点(指向53的索引)与下面左右孩子进行对比：

最终将78插入到53这个位置完成小元素的下坠：

此时最初始的大根堆就建立完成了。

堆下坠调整函数案例介绍

假设当前从09开始进行对比：

则总共需要去比较两次，第一次是09与96、32比较需要比较两次，第二次则是与左孩子42进行比较，需要比较1次。

初始建大顶堆具体分析

关于上图红色框的式子计算：将h代入到对应式子，即可以得到为2n*【j/2j，j∈[1, h - 1]】

注意这个j/2j，j∈[1, h - 1]，计算如下：

最终可以确定建立大根堆的时间复杂度为O(n)，调整为大跟堆的时间复杂度为O(logn)。

由于总共需要n-1趟，每交换一趟后就需要进行下坠调整，此时对于堆排序的时间复杂度为O(n.logn)。

稳定性：不稳定

稳定性举例

首先需要初始大根堆，首先去进行1进行下坠：

优先与左孩子进行交换：

接着进行堆排序：

首先将堆顶元素与最后一个堆元素进行互换：

接着堆顶元素与最后一个元素进行互换：

此时排序到此结束！可以看到与原先相等序列情况不一致，说明该排序是不稳定的：

思路：对于小根堆，新元素放到表尾，与父节点对比，若新元素比父节点更小，则将二者互换。新元素就这样一路“上升”，直到无法继续上升为止。

详细过程：

案例1：插入数13

我们在小根堆中插入一个数13，首先会将其放入到表尾：

插入到末尾之后此时已经破坏了小根堆，此时就需要将13不断的进行上升与父节点进行比较，此时1345不进行交换，此时上升比较就结束了！总共比较次数为1次！

思路：删除指定位置的元素，然后将堆底的元素填补上去，接着来让该节点不断进行下坠

详细过程：

假设要删除13，此时13位置删除，接着将堆中末尾元素移动到该删除的位置：

此时我们需要做的事情就是不断的让元素46进行下坠，由于17O(logn)，所以这里可以保留更高阶的空间复杂度O(n)。

无论给出的序列是有序还是无序，最终的时间复杂度为O(n.logn)【最好最坏时间复杂度】。

关于稳定性：稳定。