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

前言

选择排序是一种简单直观的排序算法，通过不断选择剩余元素中的最小值，将其放到已排序部分的末尾。与冒泡排序相比，选择排序的交换次数更少，但不稳定。

算法步骤

1. 从数组的第一个元素开始，遍历整个数组，找到最小的元素。
2. 将最小元素与数组的第一个元素交换位置。
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; } } } 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]

1. 第一轮：最小元素为2，与5交换 → [2, 3, 8, 4, 5]
2. 第二轮：最小元素为3（已在正确位置） → [2, 3, 8, 4, 5]
3. 第三轮：最小元素为4，与8交换 → [2, 3, 4, 8, 5]
4. 第四轮：最小元素为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次），适合交换成本高的场景。
• 缺点：说实话，它挺慢的，尤其是数据量大时效率低。

适用场景

适用于数据量小或交换成本高的情况，比如排序大型结构体数组时，交换操作的开销可能比比较操作更大。

明天讲插入排序。