基本思想：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。
基本思想：第i趟简单选择排序是指通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换。共需进行n-1趟比较，直到所有记录排序完成为止。
空间效率：O(1)——1个附加单元。
算法的稳定性：不稳定
基本思想：先把待排序的n个记录的关键字两两进行比较，取出较小者。然后再在n/2 个较小者中，采用同样的方法进行比较选出每两个中的较小者，如此反复，直至选出最小关键字记录为止。
算法分析：
被选中的关键字都是走了一条由叶子结点到根结点的比较的过程,由于含有n个叶子节点的完全二叉数的深度为log2n +1，则在树型选择排序中，每选择一个小关键字需要进行log2n次比较，因此其时间复杂度为O(nlog2n)。移动记录次数不超过比较次数，故总的算法时间复杂度为O(nlog2n)。
堆排序是对树型选择排序的进一步改进。采用堆排序时，只需要一个记录大小的辅助空间。堆排序是在排序过程中，将向量中存储的数据看成一棵完全二叉树，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择关键字最小的记录，即待排序记录仍采用向量数组方式存储，并非采用树的存储结构，而仅仅是采用完全二叉树的顺序结构的特征进行分析而已。
堆的含义：完全二叉树的所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。若系列是堆，则堆顶元素必定为序列中n个元素的最小值（或最大值）。
具体做法：
把待排序的记录的关键字存放在数组r[1..n]之中，将r看成是一棵完全二叉树的顺序表示，每个结点表示一个记录，第一个记录r[1]作为二叉树的根，以下各记录r[2...n]依次逐层从左到右顺序排列，任意结点r[i]的左孩子是r[2i],右孩子是r[2i+1],双亲是r[i/2]。对这棵完全二叉树进行调整，使各结点的关键字值满足下列条件：
r[i].key≥r[2i].key并且r[i].key≥r[2i+1].key(i=1,2, ...n/2 )，
满足这个条件的完全二叉树为堆。
堆排序二叉树图
堆排序方块图
堆排序的过程主要需要解决两个问题：
(1) 按堆定义建初堆
一个任意序列看成是对应的完全二叉树，由于叶结点可以视为单元素的堆，因而可以反复利用“筛选”法，自底向上逐层把所有子树调整为堆，直到将整个完全二叉树调整为堆。
（2）去掉最大元之后重建堆，得到次大元。
堆排序是一种不稳定的排序方法，
它不适用于待排序记录个数n较少的情况，但对于n较大的文件还是很有效的。