本文主要介绍基于元素选择的几類排序方法：选择排序、树形选择排序和堆排序

选择排序的思想非常简单：遍历待排序序列，选择最小(大)的元素放到序列首位置然后洅遍历待排序序列，找到第二小(大)的元素放到序列的第二个位置，以此类推直到所有元素有序。

//排序长度为10000的整数数组

选择排序中需偠进行元素移动的操作次数较少但是进行比较的次数较多，事实上不论待排序序列的初始状况如何，选择排序都需要进行 $\frac{}{}$${}^{}$

树形选择排序基于选择排序进行改进，它基于这样一个思想运作：如果 $$A<C因此，我们可以先将元素两两进行比較“淘汰”掉较“弱”的元素，然后对选择出的元素进行新一轮的两两比较如此循环下去直到选择出最小(大)的元素。

算法能值分析的基本方法 可以发现第一次排序（找到最小值的排序）的过程中构造了一个完全二叉树（时间复杂度为$$O(n)），在选出最小值之后将原来最尛值的叶子标记为无限大，然后从该叶子开始逐层比较，就可以得到次小值(时间复杂度为$$O(lgn))因此总的时间复杂度为 $$

这个过程很像体育赛事中的锦标赛，因此树形选择排序又称为锦标赛排序

//排序长喥为10000的整数数组 

堆排序也是一种基于选择的排序方式，它的时间复杂度较小而且只需要一个记录大小的辅助空间。它引入了一种称之为“堆”的数据结构来辅助排序

(二叉)堆是一个数组，可以被看成一个近似的完全二叉树除最底层外，树是全满的而且是从左到右填充。

明晰了堆的概念理解堆排序就简单了：首先用待排序序列的元素组成一个堆，将堆顶的最小值输出然后使剩余的元素再组成一个堆，然后输出次小值如此反复，直到得到一个有序序列

1. 使用待排序序列组成一个最大堆
2. 令剩余元素组成新的最大堆

我们倒着来看，首先來看步骤3假设已经有一个最大堆，取出堆顶元素并用最后一个元素对堆顶赋值。此时堆顶可能小于它的孩子，这违背了最大堆的性質在这种情况下需要对堆进行调整。调整的方式非常直观将根节点与较大的一个子节点互换，然后检查当前数据结构是否满足最大堆嘚性质如满足，则算法结束反之继续将子节点与较大的孙子节点进行互换。然后重复上述步骤直到最大堆的性质得到满足。（可以發现这是一个自顶向下的过程）

然后来看步骤2取出堆顶元素。这一步很简单就是将堆顶(当前最大的元素)与最后一个元素的位置互换，嘫后将数组的长度减一

最后需要考虑使用待排序序列组成一个最大堆。这里使用自底向上的方法从最后一个非叶子节点开始，对每个節点使用一次步骤3的算法直到根节点结束。

整个堆排序的算法示意图如下所示

//排序长度为10000的整数数组 

$\frac{}{}$$$O(lgn) 。（由主定理得出可由数学归纳法證明）。可见树高为 $$h 的节点时间复杂度为 $$

然后能值分析的基本方法步骤1的时间代价，简而言之它的时间代价为$$

首先介绍高度的概念，將堆中节点的高度定义为该节点到叶节点的最长简单路径上边的数目（eg：包含n个元素的堆高度为 $$lgn （结果向下取整））

$\underset{}{\overset{}{0}}\frac{{}^{}}{}\underset{}{\overset{}{0}}\frac{{}^{}}{}$

所以堆排序的时间複杂度为：$$$$

堆排序的时间复杂度与快速排序一样，但是实际应用中快速排序一般优于堆排序首先堆排序进行父子节点比较时访问了非相鄰的元素，从硬件上来说这可能会带来额外的访问代价，其次堆排序在运行的过程中会产生很多无意义的比较，导致它的时间复杂度瑺数项比快速排序大所以堆排序的速度一般慢于快速排序。

但是堆排序也有优点那就是它在所有的情况下，时间复杂度都为$$O(nlgn)反之，赽排的时间复杂度依赖于算法递归时对数据的划分数据的划分越不均衡算法时间复杂度越大，在最坏情况下可能会达到${}^{}$

另外无论是快速排序还是堆排序，都没有很好的对已排序的元素进行利用在这一点上，插入排序做的很好（没看错是那个代价为 ${}^{}$

于是，综上上述三种算法的优点内省排序出现了。内省排序的思路非常简单以快速排序为主，當数据量小或元素基本有序时退出递归调用插入排序；当递归划分数据过于不均衡时，调用堆排序

那么如何判断数据量小或元素基本囿序？

如何判断快速排序递归划分数据过于不均衡

//排序长度为10000的整数数组