堆排序算法思想

前两天看了看堆排序算法，啃了半天的书，最后搞明白了堆排序算法，今天有时间给大家说说这个堆排序算法。
首先讲一下算法的定义吧！
****算法****：解题方案的准确完整的描述，是解决问题的一系列清晰的指令，用系统的方法去描述解决问题的策略机制
<small>上面是一段比较官方用词的解释，我用自己简单点的话说就是算法就是用来解决问题的清晰的命令</small>

---

说完算法的定义我们还得说一下有关于算法的基础的知识点吧！
****树(tree):****是一种抽象数据类型,用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个具有层次关系的集合把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶是朝下的。
特点：
<li><small>每个节点有零个或多个子节点；</li>
<li>没有父节点的节点称为根节点；</li>
<li>每一个非根节点有且只有一个父节点；</li>
<li>除了根节点外，每个子节点可以分为多个不相交的子树；</small></li>
除了上面的这些还有一些比如说树的度，节点的度，父节点，子节点，兄弟节点等等这些我就不一一详细的介绍了，给大家一个网址上面对各个术语的解释。
https://zh.wikipedia.org/wiki/%E6%A0%91_(%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84)

---

终于到了堆排序算法了！
****堆排序：****简单的讲就是利用对的性质进行的一种选择排序。
堆分为大顶堆和小顶堆其中大顶堆满足条件：

image.png

小顶堆满足条件：

image.png

---

基本思想：(大顶堆)

1.将待排序的关键字序列（R1,R2,...Rn）构建大顶堆，此堆为初始的无序区.

2.将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区
(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];

3.由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

---

例：对数组a排序：a[]={16,7,3,20,17,8}

（1）构造树

image.png

（2）构造初始堆

image.png

和上图比较就会知道，我们首先比较子节点20>17>7

image.png

同上8>3

image.png

然后比较20,17,8，按照大顶堆得性质，最大的在最上面然后把最大的放在最后面，和最后一个换位置（Rn）如下图：

image.png
然后在进行排序，17>8>3
image.png
继续如上各个节点排序
image.png image.png image.png image.png image.png image.png image.png image.png

最后这样就排完序了

image.png