选择排序：简单高效的排序入门

前言选择排序是一种简单直观的排序算法通过不断选择剩余元素中的最小值将其放到已排序部分的末尾。与冒泡排序相比选择排序的交换次数更少但不稳定。算法步骤从数组的第一个元素开始遍历整个数组找到最小的元素。将最小元素与数组的第一个元素交换位置。从数组的第二个元素开始重复上述过程直到所有元素排序完成。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; } } } int main() { int arr[] {5, 3, 8, 4, 2}; int n sizeof(arr) / sizeof(arr[0]); selectionSort(arr, n); printf(Sorted array: ); for (int i 0; i n; i) { printf(%d , arr[i]); } return 0; }手算模拟初始数组[5, 3, 8, 4, 2]第一轮最小元素为2与5交换 → [2, 3, 8, 4, 5]第二轮最小元素为3已在正确位置 → [2, 3, 8, 4, 5]第三轮最小元素为4与8交换 → [2, 3, 4, 8, 5]第四轮最小元素为5与8交换 → [2, 3, 4, 5, 8]排序完成[2, 3, 4, 5, 8]复杂度分析时间复杂度最好、最坏、平均均为O(n²)因为无论数组是否有序都需要进行n(n-1)/2次比较。空间复杂度O(1)原地排序。不稳定排序例如数组[2,2,1]第一次交换后变为[1,2,2]原序列中两个2的相对顺序被破坏。优缺点优点交换次数少最多n-1次适合交换成本高的场景。缺点说实话它挺慢的尤其是数据量大时效率低。适用场景适用于数据量小或交换成本高的情况比如排序大型结构体数组时交换操作的开销可能比比较操作更大。明天讲插入排序。