C语言选择排序如何实现？步骤与代码解析-C语言-盈思创科技

选择排序是一种简单直观的排序算法，它的核心思想是：在未排序的序列中找到最小（或最大）的元素，存放到排序序列的起始位置，再从剩余未排序的元素中继续寻找最小（或最大）的元素，然后放到已排序序列的末尾。

（图片来源网络，侵删）

算法思想与步骤

为了更好地理解，我们用一个例子来说明：对数组 [64, 25, 12, 22, 11] 进行升序排序。

第一轮:
- 在整个未排序的数组 [64, 25, 12, 22, 11] 中找到最小的元素，是 11。
- 将 11 与未排序部分的第一个元素 64 交换。
- 数组变为: [11, 25, 12, 22, 64]
- 11 已经在它最终的位置上了。
第二轮:
- 在剩下的未排序部分 [25, 12, 22, 64] 中找到最小的元素，是 12。
- 将 12 与未排序部分的第一个元素 25 交换。
- 数组变为: [11, 12, 25, 22, 64]
- 12 也已经就位。
第三轮:
（图片来源网络，侵删）
- 在剩下的未排序部分 [25, 22, 64] 中找到最小的元素，是 22。
- 将 22 与未排序部分的第一个元素 25 交换。
- 数组变为: [11, 12, 22, 25, 64]
- 22 也已经就位。
第四轮:
- 在剩下的未排序部分 [25, 64] 中找到最小的元素，是 25。
- 25 已经在它应该在的位置了,所以不需要交换。
- 数组保持不变: [11, 12, 22, 25, 64]
第五轮:
- 只剩下一个元素 64，它自然就是最大的,排序完成。

总结步骤：

初始化一个无序的数组。
遍历数组，每次从未排序部分的第一个元素开始，到数组末尾结束,找到最小值的索引。
将找到的最小值与未排序部分的第一个元素进行交换。
每次循环后，已排序部分的元素数量增加 1，未排序部分的元素数量减少 1。
重复以上过程,直到整个数组排序完成。

C 语言代码实现

下面是选择排序的完整 C 语言代码实现,包含了详细的注释。

（图片来源网络，侵删）

#include <stdio.h>
// 函数声明
void selectionSort(int arr[], int n);
void printArray(int arr[], int size);
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("原始数组: \n");
    printArray(arr, n);
    // 调用选择排序函数
    selectionSort(arr, n);
    printf("排序后的数组: \n");
    printArray(arr, n);
    return 0;
}
// 选择排序函数
// arr[]: 待排序的数组
// n:     数组中元素的个数
void selectionSort(int arr[], int n) {
    int i, j, min_idx, temp;
    // 外层循环，遍历整个数组
    // i 代表当前未排序部分的起始位置
    // 循环 n-1 次即可，因为最后一个元素自然有序
    for (i = 0; i < n - 1; i++) {
        // 在每一轮中，假设未排序部分的第一个元素是最小的
        min_idx = i;
        // 内层循环，在未排序部分 (i 到 n-1) 中寻找最小值的索引
        for (j = i + 1; j < n; j++) {
            // 如果找到一个比当前最小值还小的元素
            if (arr[j] < arr[min_idx]) {
                // 更新最小值的索引
                min_idx = j;
            }
        }
        // 如果找到了比 arr[i] 更小的元素，则进行交换
        if (min_idx != i) {
            // 交换 arr[i] 和 arr[min_idx]
            temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
    }
}
// 打印数组的函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

代码解析：

main 函数:
- 定义并初始化一个整型数组 arr。
- 使用 sizeof 计算数组的长度 n。
- 打印排序前的数组。
- 调用 selectionSort 函数进行排序。
- 打印排序后的数组。
selectionSort 函数:
- for (i = 0; i < n - 1; i++): 这是外层循环，它控制着排序的轮数，对于一个长度为 n 的数组，我们只需要进行 n-1 轮选择，因为当 n-1 个元素都排好序后,最后一个元素必然在正确的位置。
- min_idx = i;: 在每一轮开始时，我们假设未排序部分的第一个元素（即 arr[i]）是最小的，并将其索引 i 存储在 min_idx 中。
- for (j = i + 1; j < n; j++): 这是内层循环，它负责在未排序部分（从 i+1 到 n-1）中寻找真正的最小值。
- if (arr[j] < arr[min_idx]): 如果在内层循环中发现了一个比当前记录的最小值还小的元素，我们就更新 min_idx 为这个新元素的索引 j。
- if (min_idx != i): 内层循环结束后，min_idx 中存储的就是本轮找到的最小值的索引，如果这个索引不等于 i（说明我们确实找到了一个更小的元素）,我们就执行交换操作。
- temp = arr[i]; arr[i] = arr[min_idx]; arr[min_idx] = temp;: 这是一个标准的元素交换逻辑，使用一个临时变量 temp 完成。
printArray 函数:

一个辅助函数,用于遍历并打印数组中的所有元素。

算法分析

时间复杂度

最好情况: O(n²)，无论数组是否已经有序，选择排序都必须进行两层循环的比较，即使数组已经有序，内层循环依然会执行 n-1 + n-2 + ... + 1 次比较。
最坏情况: O(n²)，与最好情况相同,因为比较次数不变。
平均情况: O(n²)，对于任何随机输入的数组，选择排序的时间复杂度都是 O(n²)。

空间复杂度

O(1)，选择排序是原地排序算法，它只需要一个额外的临时变量 temp 用于交换,所以空间复杂度是常数级的。

稳定性

不稳定，稳定性是指相等的元素在排序后其相对位置是否保持不变,选择排序是不稳定的。
例子: 考虑数组 [5a, 8, 5b, 2]。
- 第一轮，找到最小值 2，与 5a 交换，数组变为 [2, 8, 5b, 5a]。
- 两个 5 的相对顺序（5a 在前，5b 在后）被改变了。
- 选择排序是不稳定的排序算法。

优缺点

优点

实现简单：逻辑直观,代码易于编写和理解。
数据移动最少：每次内层循环只进行一次交换，最多总共进行 n-1 次交换，这对于那些交换操作成本很高的场景（当元素是很大的结构体时）是一个优点。
原地排序：空间复杂度为 O(1),非常节省内存。

缺点

时间复杂度高：O(n²) 的时间复杂度使得它在处理大规模数据时非常慢，效率远不如快速排序、归并排序等 O(n log n) 算法。
不稳定：在某些需要稳定排序的应用场景下不适用。

选择排序是一种简单但效率较低的排序算法，它主要用于教学目的，或者在数据规模非常小、对稳定性没有要求且对内存有严格限制的简单场景下使用，对于大多数实际应用,推荐使用更高效的排序算法。

C语言选择排序如何实现？步骤与代码解析