选择排序：原理、实现与优化

选择排序Selection Sort是入门级的排序算法之一它的核心思想简单易懂实现成本低非常适合编程新手理解排序的基本逻辑。本文将从原理、C 语言实现、性能分析到优化思路全方位讲解选择排序。一、选择排序的核心原理选择排序的核心可以概括为 **“找最值放位置”**它将数组分为 “已排序区间” 和 “未排序区间”初始时已排序区间为空未排序区间为整个数组遍历未排序区间找到其中的最小值或最大值将找到的最值与未排序区间的第一个元素交换位置此时该元素归入已排序区间重复步骤 2-3直到未排序区间为空直观示例以数组[5, 2, 9, 1, 5, 6]为例选择排序的执行过程第 1 轮未排序区间[5,2,9,1,5,6]最小值是 1与第一个元素 5 交换 →[1, 2, 9, 5, 5, 6]第 2 轮未排序区间[2,9,5,5,6]最小值是 2无需交换 →[1, 2, 9, 5, 5, 6]第 3 轮未排序区间[9,5,5,6]最小值是 5与 9 交换 →[1, 2, 5, 9, 5, 6]第 4 轮未排序区间[9,5,6]最小值是 5与 9 交换 →[1, 2, 5, 5, 9, 6]第 5 轮未排序区间[9,6]最小值是 6与 9 交换 →[1, 2, 5, 5, 6, 9]第 6 轮未排序区间仅剩一个元素排序完成。二、C 语言实现选择排序升序二、C 语言实现选择排序升序#include stdio.h // 交换两个整数的值 void swap(int *a, int *b) { int temp *a; *a *b; *b temp; } // 选择排序升序 void selectionSort(int arr[], int n) { // i 表示已排序区间的末尾未排序区间的起始 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], arr[minIndex]); } } } // 打印数组 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, 9, 1, 5, 6}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前的数组); printArray(arr, n); selectionSort(arr, n); printf(排序后的数组); printArray(arr, n); return 0; }三、选择排序的性能分析1. 时间复杂度最好情况数组已有序时间复杂度仍为 O(n2)必须遍历找最值无法提前终止最坏情况数组逆序时间复杂度 O(n2)平均情况O(n2)。选择排序的时间复杂度始终是 O(n2)这是因为它的内层循环必须完整遍历未排序区间无法像冒泡排序那样提前终止。2. 空间复杂度选择排序是原地排序算法In-place Sort仅使用了常数级的临时变量如temp、minIndex空间复杂度为 O(1)。3. 稳定性选择排序是不稳定排序。例如数组[2, 3, 2, 1]第一轮找到最小值 1与第一个 2 交换后原数组中两个 2 的相对位置被改变变为[1, 3, 2, 2]四、选择排序的优化双向选择排序基础选择排序每轮只找最小值优化思路是每轮同时找最小值和最大值减少循环次数这就是 “双向选择排序”也叫 “鸡尾酒排序” 简化版// 双向选择排序同时找最小和最大值 void bidirectionalSelectionSort(int arr[], int n) { int left 0; // 未排序区间左边界 int right n - 1; // 未排序区间右边界 while (left right) { int minIndex left; int maxIndex right; // 遍历未排序区间同时找最小和最大值下标 for (int i left; i right; i) { if (arr[i] arr[minIndex]) { minIndex i; } if (arr[i] arr[maxIndex]) { maxIndex i; } } // 交换最小值到左边界 if (minIndex ! left) { swap(arr[left], arr[minIndex]); } // 注意如果最大值在左边界刚被交换走需要更新maxIndex if (maxIndex left) { maxIndex minIndex; } // 交换最大值到右边界 if (maxIndex ! right) { swap(arr[right], arr[maxIndex]); } // 缩小未排序区间 left; right--; } }优化说明双向选择排序每轮处理两个元素最小值放左、最大值放右循环次数减少约一半但时间复杂度仍为 O(n2)仅减少常数项不改变阶数适合数据量较大的场景。五、选择排序的适用场景选择排序的优势是交换次数少最多 n−1 次交换因此适合数据量小的场景如嵌入式系统、单片机交换成本远高于比较成本的场景如磁盘数据排序编程新手理解排序逻辑的入门场景。总结选择排序的核心是遍历找最值交换到指定位置将数组分为已排序 / 未排序区间基础选择排序的 C 语言实现简单时间复杂度固定为 O(n2)空间复杂度 O(1)是不稳定排序双向选择排序可减少循环次数但未改变时间复杂度阶数适合对交换次数敏感的场景。选择排序虽然效率不高但它的逻辑简单、代码易实现是理解排序算法 “分区间、找规律” 思想的绝佳入门案例。掌握选择排序后再学习冒泡、插入排序等算法会更容易理解不同排序思路的差异