选择排序原理与C语言实现详解

目录

介绍

选择排序原理详解

核心思想：

算法步骤：

动态示例（升序排序）：

算法特性：

时间复杂度:

比较操作次数：

交换操作次数：

空间复杂度:

不稳定性:

C语言实现

代码解析：

外层循环 i详解：

内层循环 j详解：

min_index 记录当前找到的最小值位置：

交换的实现:

执行流程（针对示例数组）：

输出结果：

---

介绍

        选择排序（Selection Sort）是一种简单直观的排序算法。它的基本思想是：首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序原理详解

核心思想：

        每次从未排序序列中选出最小（或最大）元素，存放到排序序列的起始位置，直到所有元素排序完毕。

算法步骤：

1. 初始状态：整个序列分为已排序区（空）和未排序区（完整序列）

2. 遍历未排序区，找到最小元素

3. 将最小元素与未排序区首元素交换

4. 已排序区长度+1，未排序区长度-1

5. 重复步骤2-4，直到未排序区为空

动态示例（升序排序）：

初始数组元素： [64, 25, 12, 22, 11]数组索引        0    1    2    3    4   // 数组中共5个数据，对应数组索引0-4  按照升序排列
数组值         64   25   12   22   11   // 初始状态:已排序0个，所以下一次排序的目的是：从未排序区找到最小值放到索引0处
第1轮交换后     11   25   12   22   64  // 最小元素是11，对应下标4。所以将下标4和下标0位置的值交换。至此，已排序1个，所以下一次排序的目的是：从未排序区找到最小值放到索引1处
第2轮交换后     11   12   25   22   64  // 最小元素是12，对应下标2。所以将下标2和下标1位置的值交换。至此，已排序2个，所以下一次排序的目的是：从未排序区找到最小值放到索引2处
第3轮交换后     11   12   22   25   64  // 最小元素是22，对应下标3。所以将下标3和下标2位置的值交换。至此，已排序3个，所以下一次排序的目的是：从未排序区找到最小值放到索引3处
第4轮交换后     11   12   22   25   64  // 最小元素是25，对应下标3。所以将下标3和下标3位置的值交换(注：此时不需要交换)。至此，已排序4个，所以下一次排序的目的是：从未排序区找到最小值放到索引4处。因为数组一共5个元素，已经排序好4个，未排序区还剩1个(下标为4)。所以这个下标4必定是下一轮排序中最小的(因此，可以省略下一次排序，直接得出结果)。将下标4和下标4位置的值交换(注：此时不需要交换)。结果： [11, 12, 22, 25, 64]

算法特性：

• 时间复杂度：O(n²)（最好/最坏/平均情况）

• 空间复杂度：O(1)（原地排序）

• 不稳定性：交换可能改变相等元素顺序（如 [5, 5, 2]）

• 交换次数少：最多 n-1 次交换

时间复杂度:

        选择排序的时间复杂度在最好、最坏和平均情况下都是O(n²)，因为无论数据如何，都需要进行同样的比较操作。

比较操作次数：

• 第1轮：比较 n-1 次

• 第2轮：比较 n-2 次

• ...

• 第n-1轮：比较 1 次

• 总比较次数 = (n-1) + (n-2) + ... + 1 = n(n-1)/2  ≈ O(n²)

交换操作次数：

• 最多交换 n-1 次（每轮1次）

• 最少交换 0 次（数组已有序）

• 平均交换次数 ≈ O(n)

主导因素:比较操作次数 n² 级是主导因素，交换操作 O(n) 可忽略，因此整体时间复杂度为 O(n²)。

空间复杂度:

        通过查看下面的C语言实现代码可知，只需要常数级别的额外空间（用于临时变量存储交换的元素(temp)和记录最小元素位置(min_index)等）。 因此，空间复杂度为O(1)。

不稳定性:

交换可能改变相等元素顺序（如 [5, 5, 2]）

初始数组元素： [5,5,2]数组索引        0     1    2    // 数组中共3个数据，对应数组索引0-2  按照升序排列
数组值         5(1) 5(2)   2    // 初始状态:已排序0个，所以下一次排序的目的是：从未排序区找到最小值放到索引0处 这里用5(1)表示第一个5，5(2)表示第2个5
第1轮交换后     2   5(2)   5(1)  // 最小元素是2，对应下标2。所以将下标2和下标0位置的值交换。至此，已排序1个，所以下一次排序的目的是：从未排序区找到最小值放到索引1处
第2轮交换后     2   5(2)   5(1)  // 最小元素是5(2)，对应下标1。注:这里5(2) == 5(1) 所以代码上的处理，仍认为 5(2)是最小值。所以将下标1和下标1位置的值交换(注:此时无需交换)。至此，已排序2个，所以下一次排序的目的是：从未排序区找到最小值放到索引2处。因为一共3个元素，已排序2个，剩余1个未排序。那么剩余的一个(下标2)必然是剩余未排序中最小的，直接将其放到下标2处(注:此时无需交换)。结果： [2, 5(2), 5(1)]

C语言实现

#include <stdio.h>void selection_sort(int arr[], int n) 
{for (int i = 0; i < n - 1; i++) {int min_index = i;// 在未排序区查找最小值位置for (int j = i + 1; j < n; j++) {if (arr[j] < arr[min_index]) {min_index = j;}}// 将最小值交换到已排序区末尾if (min_index != i) {int temp = arr[i];arr[i] = arr[min_index];arr[min_index] = temp;}}
}int main() {int arr[] = {64, 25, 12, 22, 11};int n = sizeof(arr) / sizeof(arr[0]);printf("排序前: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}selection_sort(arr, n);printf("\n排序后: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}

代码解析：

1. 外层循环 i：控制已排序区的末尾位置（0 到 n-2）

2. 内层循环 j：在未排序区（i+1 到 n-1）中寻找最小值位置

3. min_index 记录当前找到的最小值位置

4. 若最小值不在当前位置 i，执行交换操作;在，则不执行

外层循环 i详解：

void selection_sort(int arr[], int n) 
{for (int i = 0; i < n - 1; i++) {// 1）数组大小为n,数组下标是0,1,...,n-2,n-1// 2）i = 0;i < n-1;j++ 意味着i只能在0,1,..,n-2之间取值，而无法取到n-1// 3）原因:前面的0,1,...,n-2下标都已排序完毕，最后只剩余1个数(下标n-1位置),// 它必然是剩余的1个数中最小的那个，因此它的位置肯定不需要改变。int min_index = i;// 在未排序区查找最小值位置for (int j = i + 1; j < n; j++) {if (arr[j] < arr[min_index]) {min_index = j;}}// 将最小值交换到已排序区末尾if (min_index != i) {int temp = arr[i];arr[i] = arr[min_index];arr[min_index] = temp;}}
}

内层循环 j详解：

void selection_sort(int arr[], int n) 
{for (int i = 0; i < n - 1; i++) {int min_index = i;// 1) 外层循环i,表示当前正在在未排序区中找最小的值，放到下标i的位置// 2) 用下标i对应的元素和下标i之后的所有下标对应的元素比较，找到最小值，记录最小值对应的下标，然后进行交换。// 3) int j = i + 1; j < n 表示j的取值范围为i+1,i+2,...,n-2,n-1  j的取值保证了能够取到下标i之后的所有下标for (int j = i + 1; j < n; j++) {if (arr[j] < arr[min_index]) {min_index = j;}}// 将最小值交换到已排序区末尾if (min_index != i) {int temp = arr[i];arr[i] = arr[min_index];arr[min_index] = temp;}}
}

min_index 记录当前找到的最小值位置：

void selection_sort(int arr[], int n) 
{for (int i = 0; i < n - 1; i++) {// 1) min_index 用来记录未排序区最小的元素的下标// 2) 首先假设下标i位置的元素就是最小的元素int min_index = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[min_index]) {// 3) 然后通过比较 更新min_index 的值min_index = j; }}// 4) 如果当前下标i的位置对应的就是最小的元素(min_index == i)，那么就不需要交换；//    否则(min_index != i) 交换元素if (min_index != i) {int temp = arr[i];arr[i] = arr[min_index];arr[min_index] = temp;}}
}

交换的实现:

void selection_sort(int arr[], int n) 
{for (int i = 0; i < n - 1; i++) {int min_index = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[min_index]) {min_index = j; }}if (min_index != i) {// 1) 目的:将arr[i]与arr[min_index]交换int temp = arr[i];        // 2) 首先定义一个临时变量，将arr[i]的原始数据保存下来，以便后面赋值给arr[min_index]arr[i] = arr[min_index];  // 3) 将arr[min_index]的值赋值给arr[i]arr[min_index] = temp;    // 4）将arr[i]的原始值(已实现存储在temp中)，赋值给arr[min_index]}}
}

执行流程（针对示例数组）：

初始数组: [64,25,12,22,11]
i=0: 找到最小值11(索引4) → 交换64和11 → [11, 25, 12, 22, 64]
i=1: 找到最小值12(索引2) → 交换25和12 → [11, 12, 25, 22, 64]
i=2: 找到最小值22(索引3) → 交换25和22 → [11, 12, 22, 25, 64]
i=3: 找到最小值25(索引3) → 无需交换

输出结果：

排序前: 64 25 12 22 11 
排序后: 11 12 22 25 64 

        选择排序适合小规模数据或对交换次数有严格限制的场景，大规模数据建议使用更高效的算法（如快速排序、归并排序）。