前言
选择排序的核心思想是每一趟从待排序列中选取一个关键字值最小（或最大）的记录，将其放到已排序序列的末尾。第 1 趟从 n 个记录中选出最小值，第 2 趟从剩下的 n-1 个记录中选出次小值，直到所有记录归位。
1. 直接选择排序
思想
首先在所有记录中选出关键字值最小的记录，把它与第一个记录进行位置交换；然后在其余记录中再选出关键字值次小的记录与第二个记录交换，依此类推，直到所有记录排好序。
下图展示了直接选择排序的完整过程：
示例
假设待排序的 8 个记录的关键字序列为 { 5, 3, 6, 4, 7, 1, 8, 2 }。初始序列视为无序序列，每趟从无序区选最小值与无序区首元素交换。
每趟遍历完成后，有序序列记录个数 +1，无序序列个数 -1。
代码实现
为了统一示例风格，这里使用 int[] 数组演示核心逻辑：
public void selectSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 进行 i-1 次遍历，arr.length：数组的长度
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
// 在剩余未排序部分找到最小值的索引
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 如果找到的最小值不是当前位置，则交换
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
性能分析
直接选择排序的比较次数固定为 n(n-1)/2，移动次数取决于数据分布。时间复杂度始终为 O(n²)，空间复杂度为 O(1)。它是不稳定排序。
2. 树形选择排序
思想
树形选择排序（锦标赛排序）通过构建一棵完全二叉树来减少比较次数。先对 n 个记录两两比较，将较小者作为优胜者上升到父结点，得到当前最小值；然后对该记录再次参与比较，重复此过程直到选出所有有序记录。
这个过程可用一个含有 n 个叶子结点的完全二叉树来表示：
示例
对于由 8 个关键字组成的序列 { 52, 39, 67, 95, 70, 8, 25, 52 }，使用树形选择排序选出最小关键字值的过程如下：
可以看到关键字都处在最后一层的叶子节点上。怎么选呢？两两 PK，谁小谁上去到父亲节点，比如 52 和 39，39 上去；67 和 95，67 上去；70 和 8，8 上去。到上一层同样也是谁小谁上去，最后关键字最小的在最上面。
找出最小值后，将其替换为无穷大 "∞"，再进行两两 PK 就可以找到次小值。以此类推，最后就排好序了。
性能分析
树形选择排序减少了比较次数，但需要额外的辅助空间存储树结构，且维护树结构的开销较大，实际应用中不如堆排序常见。
3. 堆排序
定义
堆通常指完全二叉树，分为两种：
- 大顶堆：所有父结点的值均大于或等于其左右孩子结点的值。根节点是整个序列的最大值。
- 小顶堆：所有父结点的值均小于或等于其左右孩子结点的值。根节点是整个序列的最小值。
方法
- 把待排序的记录序列对应成一棵完全二叉树，并把它转换成一个初始堆（建堆）。
- 此时根结点具有最大（或小）的关键字值，交换根结点和最后一个结点的位置。
- 除最后一个结点之外，前 n-1 个结点仍构成一棵完全二叉树，再把它们调整为一个堆。
- 重复上述步骤，直到只剩下一个根结点为止。
如何'筛选'？
所谓'筛选'，指的是调整的过程。对一棵左/右子树均为堆的完全二叉树，'调整'根结点使整个二叉树也成为一个堆。
示例
排序之前的关键字序列为 { 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 }。
筛选是一个从上往下进行的过程。可以看到每个父亲结点都比子节点大，所以是大顶堆。
但在排好序后最大值 98 应该放在最后面，下标为 9 的这个位置。这样就需要把 12 挪上去，即最大值需要跟最后一个结点的值进行交换。
但在 98 和 12 进行互换之后，它就不是堆了，因此需要对它进行'筛选'，仍然把他调整成大顶堆。这时候需要从上到下筛选，但需要注意的是：因为已经找到最大值了，并且把他放在最后面，所以不需要再排最大值 98 了。
先看 12、81、49，如果是大顶堆，需要把 81 放在最上面，81 和 12 交换。
但现在还不是大顶堆，接下来 73、12、36 比较，谁大谁上去，并交换，所以 73 和 12 交换。
然后 55 和 64 比较，谁大谁上去。
这样的话又变成大顶堆了。根结点 81 最大，和无序序列的最后一个交换，这里是 12……以此类推，每次筛选都能找到最大的，这样就排好序了。
如何'建初始堆'？
建堆是一个从下往上进行'筛选'的过程。如果建一个大顶堆，最顶上的根结点一定是最大的。
示例
例如：排序之前的关键字序列为 { 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 }。
先看下标 4 和 9，36 比 12 大，36 上去；再看左边下标 3、7、8，81 比 73、64 大，81 上去；再看右边下标 2、5、6，98 比 27、49 大，98 上去。
然后再来看下标 1、3、4，81 比 55、36 大，81 上去。
但这样我们就发现一个问题：下标 3、7、8，这三个数（55、73、64）就不能构成大顶堆了。所以三个数比较后，73 上去。
然后看下标 0、1、2，98 比 81、40 大，98 上去。
但现在下标 2、5、6，这三个数（40、27、49）就不能构成大顶堆了。所以三个数比较后，49 上去。
现在，左/右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个'堆'即可。这个就是建堆的过程，从下往上筛选（按照编号最大，并且有孩子的，此题中从 4 开始调整，然后 3、2、1），调整的过程中注意有可能打破子树上的堆，需要继续调。
代码实现
public class HeapSort {
public static void heapSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
int len = arr.length;
// 构建大顶堆，这里其实就是把待排序序列，变成一个大顶堆结构的数组
buildMaxHeap(arr, len);
// 交换堆顶和当前末尾的节点，重置大顶堆
for (int i = len - 1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0, len);
}
}
private static void buildMaxHeap(int[] arr, int len) {
// 从最后一个非叶节点开始向前遍历，调整节点性质，使之成为大顶堆
for (int i = (int) Math.floor(len / 2) - 1; i >= 0; i--) {
heapify(arr, i, len);
}
}
private static void heapify(int[] arr, int i, int len) {
// 先根据堆性质，找出它左右节点的索引
int left = 2 * i + 1;
int right = 2 * i + 2;
// 默认当前节点（父节点）是最大值
int largestIndex = i;
if (left < len && arr[left] > arr[largestIndex]) {
// 如果有左节点，并且左节点的值更大，更新最大值的索引
largestIndex = left;
}
if (right < len && arr[right] > arr[largestIndex]) {
// 如果有右节点，并且右节点的值更大，更新最大值的索引
largestIndex = right;
}
if (largestIndex != i) {
// 如果最大值不是当前非叶子节点的值，那么就把当前节点和最大值的子节点值互换
swap(arr, i, largestIndex);
// 因为互换之后，子节点的值变了，如果该子节点也有自己的子节点，仍需要再次调整
heapify(arr, largestIndex, len);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
性能分析
堆排序的时间复杂度为 O(nlogn)，空间复杂度为 O(1)，是不稳定排序。它在处理大规模数据时表现优于直接选择排序。
4. 总结
- 直接选择排序：简单直观，但效率较低，适合小规模数据。
- 树形选择排序：通过树结构减少比较次数，但空间开销较大。
- 堆排序：利用堆结构优化性能，时间复杂度稳定在 O(nlogn)，是工程中常用的排序算法之一。
想要排升序，就应该建立大堆；如果想要排降序，就应该建立小堆。筛选就是被破坏后比较、交换，谁大谁上去，从上到下的顺序；建堆是一个从下往上进行'筛选'的过程。
