数据结构实战：选择排序详解与图解

树形选择排序

先对 n 个记录进行两两比较，把关键字值较小者作为优胜者上升到父结点。这个过程可用一个含有 n 个叶子结点的完全二叉树来表示。

实例演示

对于由 8 个关键字组成的序列 { 52，39，67，95，70，8，25，¯52¯ }，使用树形选择排序选出最小关键字值的过程如下：

可以看到关键字都处在最后一层的叶子节点上。怎么选呢？俩俩 PK，谁小谁上去到父亲节点。比如 52 和 39，39 上去；67 和 95，67 上去。到上一层同样也是谁小谁上去到父亲节点，最后关键字最小的在最上面。

找次小值时，将刚才找到的最小值替换成无穷大'∞'，然后再俩俩 PK 就可以找到次小。以此类推，最后就排好序了。

性能分析

堆排序

定义

所有的父亲结点都大于孩子结点的叫大顶堆，所有的父亲结点都小于孩子结点的叫小顶堆。堆的含义表明：完全二叉树中所有非终端结点（父亲结点）的值均不大于或不小于其左、右孩子结点的值。

大顶堆中根节点的值一定是整个序列中最大的，小顶堆中根节点的值一定是整个序列中最小的。

方法

首先把待排序的记录序列对应成一棵完全二叉树，并把它转换成一个初始堆。这时，根结点具有最大或最小的关键字值，然后交换根结点和最后一个结点的位置。除最后一个结点之外，前 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;
    }
}

性能分析

总结

• 直接选择排序：简单直观，通过不断交换最小值来排序。
• 树形排序：利用锦标赛树减少比较次数，适合数据量较大的场景。
• 堆排序：如果想要排升序，就应该建立大堆；如果想要排降序，就应该建立小堆。筛选就是被破坏后比较、交换。谁大谁上去，从上到下的顺序；建堆是一个从下往上进行'筛选'的过程。