排序算法完全指南（二）：选择排序深度详解-编程实验室

引言

上一篇我们学习了冒泡排序——通过相邻元素的比较和交换来排序。今天要讲的选择排序，思路更加直接：每轮从未排序部分选出最小（或最大）的元素，放到已排序部分的末尾。就像打牌时，从散落的牌中一张一张挑出最小的放在手上。

选择排序虽然和冒泡排序同属 O(n²) 的基础排序算法，但它的交换次数仅为 O(n)，这在元素交换代价较高的场景中是一个重要的优势。然而，它不稳定的特性也使其在某些场景下不如冒泡排序。

第一部分：算法思想

一、核心原理

选择排序的核心思想是：每一次从待排序的数据中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序数据排完。

通俗比喻：排队时，老师在队列中找到最矮的学生，让他和最前面的学生交换位置，然后在剩余学生中继续找最矮的，以此类推。

二、一轮选择的过程

三、完整排序过程

规律总结：

n 个元素需要 n-1 轮
第 i 轮（i 从 0 开始）在arr[i..n-1]中找最小值
第 i 轮完成后，arr[i] 已是正确位置
总共最多交换 n-1 次

第二部分：代码实现

一、经典版本

#include <stdio.h> void selectSort(int arr[], int len) { for (int i = 0; i < len - 1; i++) { int min = i; // 假设当前位置就是最小值 // 在未排序区间 [i+1, len-1] 中寻找最小值 for (int j = i + 1; j < len; j++) { if (arr[j] < arr[min]) { min = j; } } // 如果找到的最小值不是当前位置，则交换 if (i != min) { int tmp = arr[i]; arr[i] = arr[min]; arr[min] = tmp; } } }

二、双向选择排序（同时选最大和最小）

void selectSort_bidirectional(int arr[], int len) { int left = 0, right = len - 1; while (left < right) { int min = left; int max = right; // 一趟同时找最小和最大 for (int j = left; j <= right; j++) { if (arr[j] < arr[min]) min = j; if (arr[j] > arr[max]) max = j; } // 交换最小值到左端 if (min != left) { int tmp = arr[left]; arr[left] = arr[min]; arr[min] = tmp; // ★ 如果最大值被换走了，更新 max 的位置 if (max == left) max = min; } // 交换最大值到右端 if (max != right) { int tmp = arr[right]; arr[right] = arr[max]; arr[max] = tmp; } left++; right--; } }

双向选择注意事项：

三、降序选择排序

void selectSort_descending(int arr[], int len) { for (int i = 0; i < len - 1; i++) { int max = i; for (int j = i + 1; j < len; j++) { if (arr[j] > arr[max]) { // 改成找最大值 max = j; } } if (i != max) { int tmp = arr[i]; arr[i] = arr[max]; arr[max] = tmp; } } }

第三部分：完整测试代码

#include <stdio.h> void selectSort(int arr[], int len) { for (int i = 0; i < len - 1; i++) { int min = i; for (int j = i + 1; j < len; j++) { if (arr[j] < arr[min]) { min = j; } } if (i != min) { int tmp = arr[i]; arr[i] = arr[min]; arr[min] = tmp; } } } void printArray(int arr[], int len, const char* msg) { printf("%s", msg); for (int i = 0; i < len; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { // 测试1：普通数组 int arr1[] = {5, 3, 8, 1, 2, 7, 6, 4}; int len1 = sizeof(arr1) / sizeof(arr1[0]); printArray(arr1, len1, "排序前："); selectSort(arr1, len1); printArray(arr1, len1, "排序后："); // 测试2：逆序数组（最坏情况） int arr2[] = {8, 7, 6, 5, 4, 3, 2, 1}; int len2 = sizeof(arr2) / sizeof(arr2[0]); printf("\n逆序数组测试：\n"); printArray(arr2, len2, "排序前："); selectSort(arr2, len2); printArray(arr2, len2, "排序后："); // 测试3：已经有序的数组 int arr3[] = {1, 2, 3, 4, 5, 6, 7, 8}; int len3 = sizeof(arr3) / sizeof(arr3[0]); printf("\n已有序数组测试：\n"); printArray(arr3, len3, "排序前："); selectSort(arr3, len3); printArray(arr3, len3, "排序后："); // 测试4：有重复元素（验证稳定性） int arr4[] = {5, 2, 8, 2, 9, 1, 5}; int len4 = sizeof(arr4) / sizeof(arr4[0]); printf("\n重复元素测试：\n"); printArray(arr4, len4, "排序前："); selectSort(arr4, len4); printArray(arr4, len4, "排序后："); printf("注意：两个 5 的相对顺序可能改变（不稳定）\n"); return 0; }

运行结果：

第四部分：算法分析

一、时间复杂度

情况	时间复杂度	说明
最好	O(n²)	即使有序，仍然要遍历所有找最小值
最坏	O(n²)	逆序或随机
平均	O(n²)	—

推导：

二、空间复杂度

O(1)，只用了临时变量min和tmp。

三、稳定性

选择排序是不稳定的！

为什么不稳定的根本原因：选择排序的交换是"跳跃式"的。当最小值距离当前位置较远时，交换操作会把前面的元素"扔"到很远的地方，可能越过相等的元素。

第五部分：与冒泡排序对比

对比项	冒泡排序	选择排序
最好时间	O(n) 优化版	O(n²)
最坏时间	O(n²)	O(n²)
平均时间	O(n²)	O(n²)
比较次数	O(n²)	O(n²)
交换次数	最多 O(n²)	最多 O(n)
稳定性	✅ 稳定	❌ 不稳定
优点	简单、稳定	交换少，写操作成本低

第六部分：面试考点

1. Q：选择排序的最好时间复杂度是多少？

A：O(n²)。即使数组已经有序，选择排序仍然需要遍历剩下的所有元素来确认最小值。不像冒泡可以提前退出。

2. Q：选择排序是稳定的吗？为什么？

A：不稳定。因为选择排序的交换是跳跃式的，可能把前面的元素换到很后面，越过相等的元素，破坏相对顺序。

3. Q：选择排序和冒泡排序哪个更好？

A：取决于场景。如果元素交换代价高（如交换大结构体），选择排序更好（交换少）。如果需要稳定性，冒泡更好。实际工程中两者都很少单独使用。

4. Q：如何优化选择排序？

A：双向选择排序（同时选最大和最小），每轮可以确定两个元素的位置，减少一半的轮数。但时间复杂度仍然是 O(n²)。

5. Q：选择排序的最坏情况是什么？

A：任何情况都需要 O(n²) 次比较。但从交换次数看，逆序是最坏情况（需要 n-1 次交换）。

总结

一、核心要点

要点	内容
算法思想	每轮从未排序区选出最小值，放到已排序区末尾
时间复杂度	最好/最坏/平均都是 O(n²)
空间复杂度	O(1)
稳定性	❌ 不稳定（跳跃式交换）
交换次数	最多 n-1 次（远少于冒泡）

二、代码框架记忆

for (i = 0; i < n-1; i++) { min = i; // 假设当前位置最小 for (j = i+1; j < n; j++) { // 在剩余中寻找真正的最小值 if (arr[j] < arr[min]) min = j; } if (i != min) swap(i, min); // 只交换一次 }