选择类排序的基本思想

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

---

简单选择排序

思想：设待排序序列的记录个数为n。i取1,2,…,n-1,从所有n-i+1个记录（Ri,Ri+1,…,Rn）中找出排序码最小的记录，与第i个记录交换。执行n-1趟后就完成了记录序列的排序。

平均时间复杂度：O(n^2)。

稳定性：不稳定。

代码：

---

树形选择排序（锦标赛排序）

基本思想：首先对待排序的n个记录的关键字进行两两比较，选取每两个的较小者。然后在其中n/2向上取整个较小者中，再进行两两比较，选出较小者。以此类推，直至选出最小的关键字的记录为止。经过n趟比较，可完成整个排序。

注：整个树形选择排序可用一棵有n个结点的完全二叉树完成，每一趟选出的最小关键字就是该树的根结点。为了选出次小关键字，在输出最小关键字后，就将最小关键字所对应的结点的关键字置为无穷大，然后从该叶子结点开始和其兄弟结点的关键字比较，修改从该叶子结点到根结点路径上各结点的值，则根结点的值被修改为次小关键字。如此重复，直到所有记录的关键字全部输出为止。

代码：略。

平均时间复杂度：O(nlog2n)。

稳定性：未知。

---

堆排序

堆的定义

堆是满足下列性质的数列{r1，r2，...，rn}：

当ri<=r2i，ri<=2i+1时，为小顶堆；

当ri>=r2i，ri>=2i+1时，为大顶堆；

注：若将堆看成是一棵完全二叉树，则堆是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左、右子树不为空时，根结点的值小于（小顶堆）或者大于（大顶堆）左右子树的根结点的值。

堆排序的思想：将无序序列建成一个堆，得到关键字最小（大）的记录；输出堆顶的最小（大）值后，将剩余的 n-1 个元素重又建成一个堆，则可得到 n 个元素的次小值；如此重复执行，直到堆中只有一个记录为止。

筛选：筛选是指对一棵左、右子树均为堆的完全二叉树，“调整”根结点使整个二叉树成为堆。首先将该完全二叉树的根结点中的记录移除，该记录称为待“调整”的记录。此时根结点相当于空结点，从空节点的左、右孩子中选一个关键字较小的记录，如果该记录的关键字小于待调整记录的关键字，则将该记录上移至空结点中。此时，原来那个关键字较小的子结点相当于空结点，从空结点的左、右孩子中选出一个关键字较小的记录，如果该记录的关键字仍然小于待调整记录的关键字，则将该记录上移至空结点中。重复上述移动过程，直到空结点左、右孩子为空或左、右孩子的关键字值均大于（即空结点比它左、右孩子的较小者都小）待调整记录的关键字。此时，将待调整记录放入空结点。

建立堆：首先将任意一个无序序列建立成一个完全二叉树，然后每个叶子结点可以视为单个元素构成的堆，再用筛选法，自底向上逐层（即从编号最大的那个内部结点开始，即n/2）把所有子树调整为堆，直到将整棵完全二叉树调整为堆。

堆排序的过程：

1).将待排序的无序序列首先建一个初始小顶堆，堆顶元素为最小值，然后将堆顶记录与堆尾记录交换，并将最后一个记录所在的枝剪掉。

2).调整剩余的记录序列，利用筛选法重新调整为一个新堆，堆顶元素为次小值，然后交换并剪枝。

3).以此类推，进行n-2次筛选，直到所有输出的元素为一个有序序列。

平均时间复杂度：O(nlog2n)。

稳定性：不稳定。

代码：