选择排序法是怎么排的选择排序法C语言代码

来源：聚合数据类型：技术文章发布：2025-02-28 16:54:42

选择排序法（Selection Sort）是一种简单且直观的排序算法，广泛应用于计算机科学和编程领域。它通过每次从未排序部分中选择最小（或最大）的元素，并将其放到已排序部分的末尾，逐步完成整个数组的排序。选择排序法虽然不是最高效的排序算法，但其简单易懂的特点使其成为学习排序算法的良好起点。本文将详细介绍选择排序法的工作原理、实现步骤以及C语言代码实现。通过对这些内容的深入探讨，读者可以全面理解选择排序法的运作机制，并掌握如何在实际编程中应用这一算法。

一、选择排序法的工作原理

1）基本概念

选择排序法的核心思想是：每次从未排序的部分中选择最小（或最大）的元素，将其放到已排序部分的末尾。通过重复这一过程，直到所有元素都被排序。选择排序法的主要特点是每次选择一个最小（或最大）元素进行交换，因此得名“选择排序”。

2）工作步骤

以下是选择排序法的具体工作步骤：

初始化：假设数组的第一个元素是最小值。
遍历未排序部分：从第二个元素开始，遍历剩余的未排序部分，找到真正的最小值。
交换位置：将找到的最小值与第一个元素交换位置。
重复操作：将已排序部分的长度增加1，继续从未排序部分中选择最小值，重复上述步骤，直到整个数组被完全排序。

3）示例说明

以数组 [64, 25, 12, 22, 11] 为例，详细说明选择排序法的工作过程：

第一轮：

假设 64 是最小值。

遍历剩余部分 [25, 12, 22, 11]，找到最小值 11。

将 64 和 11 交换位置，得到 [11, 25, 12, 22, 64]。

第二轮：

假设 25 是最小值。

遍历剩余部分 [12, 22, 64]，找到最小值 12。

将 25 和 12 交换位置，得到 [11, 12, 25, 22, 64]。

第三轮：

假设 25 是最小值。

遍历剩余部分 [22, 64]，找到最小值 22。

将 25 和 22 交换位置，得到 [11, 12, 22, 25, 64]。

第四轮：

剩余部分 [25, 64] 中，25 已经是最小值，无需交换。

数组已经完全排序为 [11, 12, 22, 25, 64]。

二、选择排序法的C语言代码实现

函数定义

在C语言中，选择排序法可以通过编写一个函数来实现。以下是一个完整的C语言程序，演示如何使用选择排序法对整数数组进行排序：

#include <stdio.h>
// 选择排序函数
void selectionSort(int arr[], int n) {
    int i, j, min_idx;
    // 逐个元素进行排序
    for (i = 0; i < n - 1; i++) {
        // 假设当前元素是最小值
        min_idx = i;
        // 在未排序部分寻找最小值
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // 交换最小值和当前元素
        if (min_idx != i) {
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }
}
// 打印数组函数
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
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;
}

代码解析

selectionSort 函数：

参数 arr[] 表示待排序的数组，n 表示数组的长度。

使用两个嵌套循环实现选择排序：外层循环遍历每个元素，假设当前元素是最小值。

内层循环遍历剩余的未排序部分，寻找真正的最小值。

如果找到了更小的值，则更新 min_idx。

最后，将最小值与当前元素交换位置。

printArray 函数：

用于打印数组内容，方便查看排序前后的结果。

main 函数：

定义一个待排序的数组 arr[]，并计算其长度 n。

调用 printArray 函数打印原始数组。

调用 selectionSort 函数对数组进行排序。

再次调用 printArray 函数打印排序后的数组。

运行结果

运行上述代码后，输出结果如下：

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

这表明选择排序法成功地将数组从无序状态排序为有序状态。

三、选择排序法的特性分析

时间复杂度

选择排序法的时间复杂度为 O(n²)，其中 n 是待排序数组的长度。无论数组是否已经部分有序，选择排序都需要进行 n-1 次选择操作，每次选择操作需要遍历剩余的 n-i 个元素（i 为当前已排序部分的长度）。因此，选择排序的时间复杂度始终为 O(n²)。

空间复杂度

选择排序的空间复杂度为 O(1)，即只需要常数级别的额外空间。这是因为选择排序只涉及原数组中的元素交换，不需要额外的存储空间来保存临时数据。这种特性使得选择排序在内存有限的情况下仍然能够高效运行。

稳定性

选择排序不是一种稳定的排序算法。所谓稳定性，是指在排序过程中，相等元素的相对顺序保持不变。然而，在选择排序中，当两个相等元素分别位于已排序部分和未排序部分时，可能会发生交换，导致相等元素的相对顺序发生变化。例如，在排序过程中，如果最小值出现在已排序部分的后面，那么它会被交换到前面，从而破坏了原有顺序。

适用场景

选择排序适用于内存有限且对稳定性要求不高的场景。由于其空间复杂度为 O(1)，并且不需要额外的存储空间，因此在内存资源紧张的情况下，选择排序是一个不错的选择。然而，由于其时间复杂度为 O(n²)，因此对于大规模数据集，选择排序的效率较低。此外，选择排序在小规模数据集或教学演示中也具有一定的应用场景。