引言在每一轮选拔中最直观的策略就是“统览全局挑出最优”。在排序算法中选择排序Selection Sort正是这一策略的完美体现。今天我们将从最朴素的简单选择排序出发看它如何借助“二叉堆”这一高效的数据结构华丽蜕变为工业级的高性能算法——堆排序。1. 简单选择排序Simple Selection Sort 核心思想将数组分为已排序区和未排序区。初始时已排序区为空。每次遍历未排序区记录下其中最小或最大元素的索引。遍历结束后将这个最小元素与未排序区的第一个元素进行交换使其加入已排序区。重复上述步骤直到所有元素都有序。它的核心特点是无论初始状态如何元素比较的次数都是固定的但数据交换Swap的次数极少。 Java 代码实现public class SelectionSort { public static void sort(int[] arr) { if (arr null || arr.length 2) return; int n arr.length; for (int i 0; i n - 1; i) { int minIndex i; // 暂定未排序区的第一个元素为最小值 // 在未排序区中寻找真正的最小值 for (int j i 1; j n; j) { if (arr[j] arr[minIndex]) { minIndex j; // 记录更小元素的索引 } } // 如果最小值不是未排序区的第一个元素则交换 if (minIndex ! i) { swap(arr, i, minIndex); } } } private static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; } } 性能分析时间复杂度最好、最坏、平均情况均为 O(n^2)。因为它无论如何都需要双重循环遍历。空间复杂度O(1)原地排序。稳定性不稳定。例如数组[5, 8, 5, 2, 9]在第一轮选择中第一位的5会与2交换从而破坏了两个5的相对顺序。2. 堆排序Heap Sort—— 借树蜕变 简单选择排序的优化痛点简单选择排序之所以慢是因为它在每一轮比较中并没有把比较的结果保存下来。下一轮找最小值时很多元素又要重复比较一遍。如果我们能用一种数据结构把比较过的大小关系“记下来”不就能省去大量无用功吗二叉堆Binary Heap就是这个秘密武器 核心思想堆排序是利用大顶堆Max Heap或小顶堆Min Heap进行选择排序的算法构造初始堆将无序数组构造成一个大顶堆所有父节点的值都大于或等于其左右孩子。此时堆顶根节点必然是整个数组的最大值。交换与调整将堆顶元素最大值与数组末尾元素交换。此时最大值已归位。重建堆将剩余的 n-1 个元素重新调整为大顶堆再次将堆顶与倒数第二个元素交换。如此反复直到整个数组有序。public class HeapSort { public static void sort(int[] arr) { if (arr null || arr.length 2) return; int n arr.length; // 1. 构建初始大顶堆从最后一个非叶子节点开始往前调整 for (int i n / 2 - 1; i 0; i--) { heapify(arr, n, i); } // 2. 逐个将堆顶元素移到数组末尾并重新调整堆 for (int i n - 1; i 0; i--) { swap(arr, 0, i); // 将当前最大的堆顶换到末尾 heapify(arr, i, 0); // 重新调整剩余的 i 个元素使堆顶保持最大 } } /** * 维护大顶堆性质的“下沉Sift Down”操作 * param arr 数组 * param heapSize 当前参与建堆的元素个数 * param root 当前需要下沉的根节点索引 */ private static void heapify(int[] arr, int heapSize, int root) { int largest root; // 初始化最大值为根节点 int left 2 * root 1; // 左孩子索引 int right 2 * root 2; // 右孩子索引 // 如果左孩子比根节点大 if (left heapSize arr[left] arr[largest]) { largest left; } // 如果右孩子比当前最大值还大 if (right heapSize arr[right] arr[largest]) { largest right; } // 如果最大值不是根节点说明需要“下沉” if (largest ! root) { swap(arr, root, largest); // 递归调整受影响的子树 heapify(arr, heapSize, largest); } } private static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; } } 性能分析时间复杂度构建初始堆耗时 O(n)执行 n 次交换和下沉调整耗时 O(n \log n)。因此最好、最坏、平均时间复杂度稳稳保持在O(n \log n)。空间复杂度O(1)。不需要额外辅助数组直接在原数组的二叉树映射上操作。稳定性不稳定。在下沉和交换过程中长距离的跨越会打乱相同元素的相对位置。