选择排序算法详解：直接、树形与堆排序

性能分析

直接选择排序的比较次数固定为 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. 堆排序

定义

堆通常指完全二叉树，分为两种：

• 大顶堆：所有父结点的值均大于或等于其左右孩子结点的值。根节点是整个序列的最大值。
• 小顶堆：所有父结点的值均小于或等于其左右孩子结点的值。根节点是整个序列的最小值。

方法

1. 把待排序的记录序列对应成一棵完全二叉树，并把它转换成一个初始堆（建堆）。
2. 此时根结点具有最大（或小）的关键字值，交换根结点和最后一个结点的位置。
3. 除最后一个结点之外，前 n-1 个结点仍构成一棵完全二叉树，再把它们调整为一个堆。
4. 重复上述步骤，直到只剩下一个根结点为止。

如何'筛选'？

所谓'筛选'，指的是调整的过程。对一棵左/右子树均为堆的完全二叉树，'调整'根结点使整个二叉树也成为一个堆。

示例

排序之前的关键字序列为 { 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)，是工程中常用的排序算法之一。

想要排升序，就应该建立大堆；如果想要排降序，就应该建立小堆。筛选就是被破坏后比较、交换，谁大谁上去，从上到下的顺序；建堆是一个从下往上进行'筛选'的过程。