排序算法‌ 之‌ ‌‌选择排序（Selection Sort）

排序算法‌ 之‌ ‌‌选择排序（Selection Sort）

1. 基础概念

1.1 选择排序的定义

选择排序是一种原地排序算法，通过反复选择未排序部分的最小值并将其移动到已排序部分的末尾来完成排序。每轮排序都会将未排序部分的最小值选出并与当前位置交换。

1.2 选择排序的特点

• 时间复杂度：最优、最差和平均情况下时间复杂度均为 O(n²)。
• 空间复杂度：原地排序算法，空间复杂度为 O(1)。
• 稳定性：选择排序是不稳定的，交换可能会改变相同元素的相对位置。
• 适用性：适合小规模数据集的排序，不推荐用于大数据集。

1.3 使用场景

选择排序适用于对小型数据集的排序场景，例如教学演示、基础编程训练，或是内存有限的场景。

2. 实现与操作

2.1 核心操作实现

以下是使用 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; // 更新最小值索引 } } // 交换当前元素和找到的最小值 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[] = {64, 25, 12, 22, 11}; int n = sizeof(arr) / sizeof(arr[0]); printf("排序前的数组: "); printArray(arr, n); selectionSort(arr, n); printf("排序后的数组: "); printArray(arr, n); return 0; } </stdio.h>

2.2 代码详解

• 外层循环 for (int i = 0; i < n - 1; i++) 确定每次要排序的位置。
• 内层循环 for (int j = i + 1; j < n; j++) 找到未排序部分的最小值。
• 通过交换操作将最小值放到当前轮的正确位置。

3. 时间与空间复杂度分析

3.1 时间复杂度

• 每次外层循环需进行 (n - i - 1) 次比较，总计比较次数为 O(n²)。
• 交换次数最多为 n-1 次。

3.2 空间复杂度

选择排序为原地排序，空间复杂度为 O(1)。

4. 优缺点与局限性

4.1 优点

• 实现简单，适合初学者。
• 空间复杂度低，无需额外存储空间。

4.2 缺点与局限性

• 时间复杂度高，不适合大规模数据集。
• 不稳定性可能导致相同元素的相对顺序被打乱。

5. 常见应用场景

5.1 实际应用

以下示例代码用于从数组中找到前 k 个最小值：

#include <stdio.h> void findTopKSmallest(int arr[], int n, int k) { selectionSort(arr, n); // 使用选择排序 printf("前 %d 个最小值: ", k); for (int i = 0; i < k; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {64, 25, 12, 22, 11}; int n = sizeof(arr) / sizeof(arr[0]); int k = 3; findTopKSmallest(arr, n, k); return 0; } </stdio.h>

6. 代码编译与运行

6.1 编译命令

使用以下命令编译代码：

gcc selection_sort.c -o selection_sort

6.2 测试用例

输入数组为 {64, 25, 12, 22, 11}，运行结果如下：

    排序前的数组: 64 25 12 22 11 
    排序后的数组: 11 12 22 25 64