选择排序的基本思想是：每一趟（如第 选择排序 - 图1 趟）在后面 选择排序 - 图2#card=math&code=n-i%2B1%20%5C%20%28i%3D1%2C2%2C%5Ccdots%20%2Cn-1%29&id=kQjTR) 个待排序元素中选取关键字最小的元素，作为有序子序列的第 选择排序 - 图3 个元素，直到第 选择排序 - 图4 趟做完，待排序元素只剩下 1 个，就不用再选了。

简单选择排序

根据上面选择排序的思想，可以很直观地得出简单选择排序算法的思想：假设排序表为 选择排序 - 图5 ，第 选择排序 - 图6 趟排序即从 选择排序 - 图7 中选择关键字最小的元素与 选择排序 - 图8#card=math&code=L%28i%29&id=MYcz9) 交换，每一趟排序可以确定一个元素的最终位置，这样经过 选择排序 - 图9 趟排序就可使得整个排序表有序。简单选择排序算法的代码如下：

  1. void SelectSort(ElemType A[], int n) {
  2.     for (int i = 0; i < n - 1; i++) {    // 一共进行n-1趟
  3.         int min = i;                     // 记录最小元素位置
  4.         for (int j = i + 1; j < n; j++)  // 在A[i...n-1]中选择最小的元素
  5.             if (A[j] < A[min]) min = j;  // 更新最小元素位置
  6.         if (min != i) swap(A[i], A[min]);  //封装的 swap() 函数共移动元素3次
  7.     }
  8. }

简单选择排序算法的性能分析如下：

空间效率：仅使用常数个辅助单元，故空间效率为 选择排序 - 图10#card=math&code=O%281%29&id=fpXHg)。

时间效率：从上述伪码中不难看出，在简单选择排序过程中，元素移动的操作次数很少，不会超过 选择排序 - 图11#card=math&code=3%28n-%201%29&id=HTSBr) 次，最好的情况是移动 0 次，此时对应的表已经有序；但元素间比较的次数与序列的初始状态无关，始终是 选择排序 - 图12%7D%7B2%7D#card=math&code=%5Cfrac%7Bn%28n-%201%29%7D%7B2%7D&id=twyA6) 次，因此时间复杂度始终是 选择排序 - 图13#card=math&code=O%28n%5E2%29&id=SJkO0) 。

稳定性：在第 选择排序 - 图14 趟找到最小元素后，和第 选择排序 - 图15 个元素交换，可能会导致第 选择排序 - 图16 个元素与其含有相同关键字元素的相对位置发生改变。因此，简单选择排序是一种不稳定的排序方法。

堆排序

堆的定义如下，选择排序 - 图17 个关键字序列 L[1..n] 称为堆，当且仅当该序列满足：

  1. L(i)>=L(2i) 且 L(i)>=L(2i+1) 或
  2. L(i)<=L(2i) 且 L(i)<=L(2i+1) （选择排序 - 图18）

可以将该一维数组视为一棵完全二叉树，

  • 满足条件 1 的堆称为大根堆（大顶堆），大根堆的最大元素存放在根结点，且其任一非根结点的值小于等于其双亲结点值。
  • 满足条件 2 的堆称为小根堆（小顶堆），小根堆的定义刚好相反，根结点是最小元素。

堆排序的思路很简单：首先将存放在 L[1...n] 中的 选择排序 - 图19 个元素建成初始堆，由于堆本身的特点（以大顶堆为例），堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶，此时根结点已不满足大顶堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素。如此重复，直到堆中仅剩一个元素为止。可见堆排序需要解决两个问题：

  1. 如何将无序序列构造成初始堆
  2. 输出堆顶元素后，如何将剩余元素调整成新的堆

堆排序的关键是构造初始堆。选择排序 - 图20 个结点的完全二叉树，最后一个结点是第 选择排序 - 图21 个结点的孩子。对第 选择排序 - 图22 个结点为根的子树筛选（对于大根堆，若根结点的关键字小于左右孩子中关键字较大者，则交换），使该子树成为堆。之后向前依次对各结点（ 选择排序 - 图23） 为根的子树进行筛选，看该结点值是否大于其左右子结点的值，若不大于，则将左右子结点中的较大值与之交换，交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到以该结点为根的子树构成堆为止。反复利用上述调整堆的方法建堆，直到根结点。

下面是建立大根堆算法：

  1. // 建立大根堆
  2. void BuildMaxHeap(int A[], int len) {
  3.     for (int i = len / 2; i > 0; i--) {  // 从后往前调整所有的非终端结点
  4.         HeadAdjust(A, i, len);
  5.     }
  6. }
  8. // 将以 k 为根的子树调整为大根堆
  9. void HeadAdjust(int A[], int k, int len) {
  10.     A[0] = A[k];                             // A[0] 暂存子树的根节点
  11.     for (int i = 2 * k; i <= len; i *= 2) {  // 沿 key 较大的子结点向下筛选
  12.         if (i < len && A[i] < A[i + 1]) { // i < len 保证有右兄弟
  13.             i++;  // 取 key 较大的子结点的下标
  14.         }
  15.         if (A[0] >= A[i]) {
  16.             break;  // 筛选结束
  17.         } else {
  18.             A[k] = A[i];  // 将 A[i] 调整到双亲结点上
  19.             k = i;        // 修改 k 值，以便继续向下筛选
  20.         }
  21.     }
  22.     A[k] = A[0];  // 被筛选结点的值放入最终位置
  23. }

下面是堆排序算法：

void HeapSort(int A[], int len) {
    BuildMaxHeap(A, len);  // 初始建堆
    for (int i = len; i > 1; i--) {
        Swap(A[i], A[1]);  // 输出堆顶元素（和堆底元素交换）
        HeadAdjust(A, 1, i - 1);  // 调整，把剩余的 i-1 个元素整理成堆
    }
}

堆排序适合关键字较多的情况（如 选择排序 - 图24 ）。例如，在 1 亿个数中选出前 100 个最大值。首先使用一个大小为 100 的数组，读入前 100 个数，建立小顶堆，而后依次读入余下的数，若小于堆顶则舍弃，否则用该数取代堆顶并重新调整堆，待数据读取完毕，堆中 100 个数即为所求。

堆排序算法的性能分析如下：

空间效率：仅使用了常数个辅助单元，所以空间复杂度为 选择排序 - 图25#card=math&code=O%281%29&id=TfhxK)。

时间效率：建堆时间为 选择排序 - 图26#card=math&code=O%28n%29&id=S3XFc) 【推导过程】，之后有 选择排序 - 图27 次向下调整操作，每次调整的时间复杂度为 选择排序 - 图28#card=math&code=O%28h%29&id=GfeYW)，故在最好、最坏和平均情况下，堆排序的时间复杂度为 选择排序 - 图29#card=math&code=O%28n%20%5Clog_%7B2%7D%7Bn%7D%29&id=sxzwx)。

稳定性：进行筛选时，有可能把后面相同关键字的元素调整到前面，所以堆排序算法是一种不稳定的排序方法。

堆的插入：新元素放到表尾（堆底），根据大/小根堆的要求，新元素不断“上升”，直到无法继续上升为止。每次“上升”调整只需对比关键字 1 次。

堆的删除：被删除元素用表尾（堆底）元素代替，根据大/小根堆的要求，替代元素不断“下坠”，知道无法继续下坠为止。每次“下坠”调整可能需要对比关键字 2 次，也可能只需对比 1 次。