简单选择排序<span style="font-size: 12.7272720336914px;">（不稳定）</span><div style="font-size: 12.7272720336914px;">时间复杂度O（n^2）</div><div style="font-size: 12.7272720336914px;">空间复杂度 O（1）</div>
<div>算法思想</div><div>从头至尾顺序扫描序列，找出最小的一个数据，和第一个数据交换，接着从剩下的数据中继续这种选择和交换，最终使序列有序。</div>
<div>【注】</div><div>①完全二叉树的高度为<span style="color: rgb(51, 51, 51); font-family: arial; line-height: 20.0200004577637px;">⌈</span>log2(n+1)<span style="color: rgb(51, 51, 51); font-family: arial; line-height: 20.0200004577637px;">⌉ 所以时间复杂度是</span>O（nlog2n）</div><div>②时间复杂度最坏情况下也是O（nlog2n），这是堆排序相对于快速排序的最大优点</div><div>③堆排序空间复杂度为O（1），在所有时间复杂度为O（nlog2n）的排序中是最小的，这也是其一大优点</div><div>④堆排序适合的场景是记录数很多的情况，典型例子是从10000个记录中选出前10个最小的。如果记录数少，则不提倡使用堆排序</div>
堆排序<span style="font-size: 13px;">（不稳定）</span><div style="font-size: 12.7272720336914px;">时间复杂度 O（nlog2n）</div><div style="font-size: 12.7272720336914px;">空间复杂度 O（1）</div>
<div>1.算法思想</div><div>堆是一种数据结构，可以把堆看成一棵完全二叉树。完全二叉树满足：任何一个非叶节点的值都不大于其左右孩子节点的值（父亲小孩子大 小顶堆），或任何一个非叶节点的值都不小于其左右孩子节点的值（父亲大孩子小 大顶堆）。</div><div>将一个无序序列调整为一个堆，就可以找出这个序列的最大或最小值（即完全二叉树的根节点的值），然后将找出的这个值交换到序列的最后或最前，这样有序序列元素增加一个，无序序列元素减少一个，对于新的无序序列重复这样的在操作，就实现了排序。</div>
<div>2.执行流程（以大顶堆为例）</div><div>①从无序序列所确定的完全二叉树的第一个非叶子节点开始，从右至左，从下至上，对每个节点进行调整，最终将得到一个大顶堆。</div><div>对节点的调整方法如下：将当前节点a的值，与其孩子节点进行比较，如果存在大于a值的孩子节点，则从中选出一个最大的一个与a交换，当a来到下一层的时候，重复上述过程，直到a的孩子结点值都小于a的值为止。</div><div>②将当前无序序列中第一个元素，反应在树中是根节点（假设为a），与无序序列中最后一个元素交换（假设为b），a进入有序序列到达最终位置，无序序列中元素减少一个，有序列中元素增加一个，此时只有节点b可能不满足堆的定义，对其进行调整。</div><div>③重复②中过程，直到无序系列中的元素，剩下一个时排序结束。</div>
<div>【注】</div><div>①完全二叉树的高度为<span style="color: rgb(51, 51, 51); font-family: arial; line-height: 20.0200004577637px;">⌈</span>log2(n+1)<span style="color: rgb(51, 51, 51); font-family: arial; line-height: 20.0200004577637px;">⌉ 所以时间复杂度是</span>O（nlog2n）</div><div>②时间复杂度最坏情况下也是O（nlog2n），这是堆排序相对于快速排序的最大优点</div><div>③堆排序空间复杂度为O（1），在所有时间复杂度为O（nlog2n）的排序中是最小的，这也是其一大优点</div><div>④堆排序适合的场景是记录数很多的情况，典型例子是从10000个记录中选出前10个最小的。如果记录数少，则不提倡使用堆排序</div>
