【数据结构与算法】第34篇：选择排序：简单选择排序与堆排序

一、简单选择排序

1.1 算法思想

每次从待排序序列中选出最小元素，放到已排序序列的末尾。

步骤：

1. 在[0, n-1]范围找最小值，与arr[0]交换

2. 在[1, n-1]范围找最小值，与arr[1]交换

3. 重复，直到所有元素有序

1.2 图解示例

text

初始: [5, 2, 4, 6, 1, 3] 第1趟：找最小值1，与5交换 → [1, 2, 4, 6, 5, 3] 第2趟：找最小值2（已在位）→ [1, 2, 4, 6, 5, 3] 第3趟：找最小值3，与4交换 → [1, 2, 3, 6, 5, 4] 第4趟：找最小值4，与6交换 → [1, 2, 3, 4, 5, 6] 第5趟：找最小值5（已在位）→ [1, 2, 3, 4, 5, 6]

1.3 代码实现

c

#include <stdio.h> void selectionSort(int arr[], int n) { 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) { int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } } void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {5, 2, 4, 6, 1, 3}; int n = sizeof(arr) / sizeof(arr[0]); printf("原数组: "); printArray(arr, n); selectionSort(arr, n); printf("排序后: "); printArray(arr, n); return 0; }

运行结果：

text

原数组: 5 2 4 6 1 3 排序后: 1 2 3 4 5 6

1.4 复杂度分析

空间复杂度：O(1)
稳定性：不稳定（交换可能打乱相等元素的顺序）

二、堆排序

2.1 堆的概念

堆是一棵完全二叉树，分为：

• 大根堆：每个节点的值 ≥ 左右孩子节点的值

• 小根堆：每个节点的值 ≤ 左右孩子节点的值

数组存储：下标i的节点

• 左孩子：2*i + 1

• 右孩子：2*i + 2

• 父节点：(i - 1) / 2

2.2 核心操作：向下调整（Heapify）

作用：当只有根节点不满足堆性质时，将其向下调整到合适位置。

步骤：

1. 找到当前节点和左右孩子中的最大值

2. 如果最大值不是当前节点，交换，继续向下调整

c

// 向下调整：将i位置的元素向下调整，使以i为根的子树满足大根堆 void heapify(int arr[], int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) { largest = left; } if (right < n && arr[right] > arr[largest]) { largest = right; } if (largest != i) { int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; heapify(arr, n, largest); // 递归调整 } }

2.3 建堆

从最后一个非叶子节点开始，从下往上执行向下调整。

c

void buildHeap(int arr[], int n) { // 最后一个非叶子节点的下标 = (n/2) - 1 for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } }

建堆过程图解（数组[4, 6, 3, 5, 2, 1]）：

text

初始完全二叉树： 4 / \ 6 3 / \ / 5 2 1 从下标2（值3）开始调整 → 不变 下标1（值6）：左右孩子5、2，6最大 → 不变 下标0（值4）：左右孩子6、3，6最大 → 交换4和6 6 / \ 4 3 / \ / 5 2 1 继续调整下标1（值4）：左右孩子5、2，5最大 → 交换4和5 6 / \ 5 3 / \ / 4 2 1 建堆完成

2.4 堆排序流程

升序排序用大根堆：

1. 建大根堆

2. 将堆顶（最大值）与最后一个元素交换

3. 堆大小减1，对新的堆顶执行向下调整

4. 重复2-3，直到堆大小为1

c

void heapSort(int arr[], int n) { // 1. 建大根堆 buildHeap(arr, n); // 2. 反复取出堆顶 for (int i = n - 1; i > 0; i--) { // 交换堆顶和末尾 int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // 调整剩余部分 heapify(arr, i, 0); } }

为什么升序建大堆：每次把最大值放到末尾，最后得到升序序列。

三、完整代码实现

c

#include <stdio.h> #include <stdlib.h> #include <time.h> // 向下调整（大根堆） void heapify(int arr[], int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) { largest = left; } if (right < n && arr[right] > arr[largest]) { largest = right; } if (largest != i) { int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; heapify(arr, n, largest); } } // 建堆 void buildHeap(int arr[], int n) { for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } } // 堆排序（升序） void heapSort(int arr[], int n) { buildHeap(arr, n); for (int i = n - 1; i > 0; i--) { // 交换堆顶和末尾 int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // 调整剩余部分 heapify(arr, i, 0); } } // 简单选择排序 void selectionSort(int arr[], int n) { 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) { int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } } // 打印数组 void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } // 生成随机数组 void generateRandomArray(int arr[], int n) { for (int i = 0; i < n; i++) { arr[i] = rand() % 10000; } } // 复制数组 void copyArray(int src[], int dst[], int n) { for (int i = 0; i < n; i++) { dst[i] = src[i]; } } int main() { srand(time(NULL)); // 基本测试 printf("=== 基本测试 ===\n"); int arr1[] = {4, 6, 3, 5, 2, 1}; int n1 = sizeof(arr1) / sizeof(arr1[0]); printf("原数组: "); printArray(arr1, n1); heapSort(arr1, n1); printf("堆排序后: "); printArray(arr1, n1); // 简单选择排序测试 int arr2[] = {5, 2, 4, 6, 1, 3}; int n2 = sizeof(arr2) / sizeof(arr2[0]); selectionSort(arr2, n2); printf("\n简单选择排序后: "); printArray(arr2, n2); // 性能对比 printf("\n=== 性能对比 ===\n"); int sizes[] = {1000, 5000, 10000}; int nTests = sizeof(sizes) / sizeof(sizes[0]); for (int t = 0; t < nTests; t++) { int n = sizes[t]; int *arr = (int*)malloc(n * sizeof(int)); int *arr2 = (int*)malloc(n * sizeof(int)); generateRandomArray(arr, n); copyArray(arr, arr2, n); clock_t start, end; double time1, time2; start = clock(); selectionSort(arr, n); end = clock(); time1 = (double)(end - start) / CLOCKS_PER_SEC * 1000; start = clock(); heapSort(arr2, n); end = clock(); time2 = (double)(end - start) / CLOCKS_PER_SEC * 1000; printf("n=%d:\n", n); printf(" 简单选择排序: %.2f ms\n", time1); printf(" 堆排序: %.2f ms\n", time2); printf(" 堆排序是简单选择的 %.2f 倍\n\n", time1 / time2); free(arr); free(arr2); } return 0; }

运行结果：

text

=== 基本测试 === 原数组: 4 6 3 5 2 1 堆排序后: 1 2 3 4 5 6 简单选择排序后: 1 2 3 4 5 6 === 性能对比 === n=1000: 简单选择排序: 2.35 ms 堆排序: 0.18 ms 堆排序是简单选择的 13.06 倍 n=5000: 简单选择排序: 57.82 ms 堆排序: 1.05 ms 堆排序是简单选择的 55.07 倍 n=10000: 简单选择排序: 230.45 ms 堆排序: 2.31 ms 堆排序是简单选择的 99.76 倍

四、堆排序的详细过程演示

c

// 打印堆排序每一步 void heapSortWithSteps(int arr[], int n) { printf("原数组: "); printArray(arr, n); buildHeap(arr, n); printf("建堆后: "); printArray(arr, n); for (int i = n - 1; i > 0; i--) { printf("交换 arr[0]=%d 和 arr[%d]=%d\n", arr[0], i, arr[i]); int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); printf("调整后: "); printArray(arr, n); } } int main() { int arr[] = {4, 6, 3, 5, 2, 1}; int n = sizeof(arr) / sizeof(arr[0]); heapSortWithSteps(arr, n); return 0; }

运行结果：

text

原数组: 4 6 3 5 2 1 建堆后: 6 5 3 4 2 1 交换 arr[0]=6 和 arr[5]=1 调整后: 5 4 3 1 2 6 交换 arr[0]=5 和 arr[4]=2 调整后: 4 2 3 1 5 6 交换 arr[0]=4 和 arr[3]=1 调整后: 3 2 1 4 5 6 交换 arr[0]=3 和 arr[2]=1 调整后: 2 1 3 4 5 6 交换 arr[0]=2 和 arr[1]=1 调整后: 1 2 3 4 5 6

五、两种选择排序对比

六、堆排序的特点

七、小结

这一篇我们学习了两种选择排序：

堆排序的关键：

• 大根堆：每个节点 ≥ 孩子节点

• 建堆：从最后一个非叶子节点开始向下调整

• 升序用大根堆：每次把堆顶（最大值）放到末尾

向下调整的递归/非递归：

c

// 非递归版本（避免递归深度） void heapifyIter(int arr[], int n, int i) { while (1) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; if (largest == i) break; int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; i = largest; } }

下一篇我们讲归并排序与基数排序。

八、思考题

1. 简单选择排序和冒泡排序相比，哪个交换次数更少？为什么？

2. 为什么升序排序要用大根堆而不是小根堆？

3. 堆排序中，建堆的时间复杂度是多少？为什么？

4. 如何在O(n log k)的时间内找到数组中最小的k个元素？

欢迎在评论区讨论你的答案。