-选择排序专题——简单选择排序与堆排序的结构优化)
📌 引言
在每一轮选拔中，最直观的策略就是“统览全局，挑出最优”。在排序算法中，选择排序（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)。不需要额外辅助数组，直接在原数组的二叉树映射上操作。
稳定性：不稳定。在下沉和交换过程中，长距离的跨越会打乱相同元素的相对位置。
