如何在 C 语言中进行选择排序？

C语言

🍅关注博主🎗️ 带你畅游技术世界，不错过每一次成长机会！
📙C 语言百万年薪修炼课程 通俗易懂，深入浅出，匠心打磨，死磕细节，6年迭代，看过的人都说好。

分割线

文章目录

如何在 C 语言中进行选择排序
一、选择排序的基本思想
二、选择排序的算法步骤
三、选择排序的 C 语言实现
四、选择排序的时间复杂度和空间复杂度分析
- （一）时间复杂度
- （二）空间复杂度
五、选择排序的稳定性
六、选择排序的适用场景
七、选择排序与其他排序算法的比较
- （一）与冒泡排序的比较
- （二）与插入排序的比较
- （三）与快速排序的比较
八、示例分析
九、优化思路
- （一）减少交换次数
- （二）利用已排序部分的信息
十、总结

分割线

如何在 C 语言中进行选择排序

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

分割线

一、选择排序的基本思想

遍历整个数组，找出最小的元素。
将最小的元素与数组的第一个元素交换位置。
在剩余的未排序元素中重复上述步骤，直到整个数组都被排序。

分割线

二、选择排序的算法步骤

以下是选择排序的详细步骤：

假设要对数组 arr[] 进行排序，数组的长度为 n：

从数组的第一个元素开始，即 i = 0 。
对于每个 i，从 i + 1 到 n - 1 中找到最小的元素，并记录其索引 min_index 。
如果 min_index 不等于 i，则交换 arr[i] 和 arr[min_index] 。
增加 i，重复步骤 2 和 3，直到 i = n - 2 。

分割线

三、选择排序的 C 语言实现

#include <stdio.h>

// 交换两个元素的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 选择排序函数
void selectionSort(int arr[], int n) {
    int i, j, min_index;

    for (i = 0; i < n - 1; i++) {
        min_index = i;
        for (j = i + 1; j < n; j++)
            if (arr[j] < arr[min_index])
                min_index = j;

        if (min_index!= i)
            swap(&arr[i], &arr[min_index]);
    }
}

// 打印数组函数
void printArray(int arr[], int size) {
    for (int 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("排序前的数组为: ");
    printArray(arr, n);

    selectionSort(arr, n);

    printf("排序后的数组为: ");
    printArray(arr, n);

    return 0;
}

在上述代码中，我们首先定义了一个 swap 函数用于交换两个元素的值。

selectionSort 函数实现了选择排序的逻辑。外层循环控制排序的轮数，内层循环用于在每一轮中找到最小的元素。

printArray 函数用于打印数组的元素。

在 main 函数中，我们创建了一个待排序的数组，并调用相应的函数进行排序和打印。

分割线

四、选择排序的时间复杂度和空间复杂度分析

（一）时间复杂度

选择排序的平均时间复杂度和最坏时间复杂度都为 O(n^2)。这是因为无论数组的初始状态如何，对于每个元素都需要进行比较和交换操作，总共需要进行 n - 1 轮比较和交换，每一轮比较和交换的操作数量都与数组的长度 n 成正比。

（二）空间复杂度

选择排序的空间复杂度为 O(1)。因为它只在交换元素时使用了固定的额外空间，而不需要额外的数组或其他数据结构来存储数据。

分割线

五、选择排序的稳定性

选择排序是一种不稳定的排序算法。这是因为在选择最小元素并与当前位置交换时，如果有两个相同的元素，它们的相对顺序可能会发生改变。

例如，对于数组 [5, 5', 2]，第一次选择最小元素 2 并与第一个位置的 5 交换，得到 [2, 5', 5]，两个 5 的相对顺序发生了变化。

分割线

六、选择排序的适用场景

选择排序适用于小型数据集或者对算法的简单性要求较高的场景。由于其时间复杂度较高，在处理大型数据集时，性能通常不如其他更高效的排序算法，如快速排序、归并排序等。

分割线

七、选择排序与其他排序算法的比较

（一）与冒泡排序的比较

选择排序和冒泡排序都是简单的排序算法，它们的时间复杂度都为 O(n^2)。然而，在每一轮的操作中，冒泡排序需要进行多次相邻元素的比较和交换，而选择排序只需要进行一次最小元素的选择和交换。因此，在通常情况下，选择排序的性能略优于冒泡排序。

（二）与插入排序的比较

插入排序在对于近乎有序的数组时，性能较好，其平均时间复杂度可以接近 O(n)。而选择排序无论数组的初始状态如何，时间复杂度都为 O(n^2)。因此，在数组近乎有序的情况下，插入排序更优。

（三）与快速排序的比较

快速排序的平均时间复杂度为 O(nlogn)，是一种效率很高的排序算法。与选择排序相比，快速排序在处理大型数据集时具有明显的优势。

分割线

八、示例分析

让我们通过一个具体的示例来详细分析选择排序的过程。

假设有数组 [9, 5, 7, 2, 6]

第一轮：

初始状态：[9, 5, 7, 2, 6]
首先假设第一个元素 9 是最小的，然后从第二个元素开始比较。
经过比较，发现 2 是最小的，所以将 2 与 9 交换位置。
第一轮结束后，数组变为 [2, 5, 7, 9, 6]

第二轮：

此时从第二个元素开始，假设 5 是最小的。
比较剩余元素，发现没有比 5 更小的，所以位置不变。
第二轮结束后，数组仍为 [2, 5, 7, 9, 6]

第三轮：

从第三个元素开始，假设 7 是最小的。
比较剩余元素，发现 6 更小，所以将 6 与 7 交换位置。
第三轮结束后，数组变为 [2, 5, 6, 9, 7]

第四轮：

从第四个元素开始，假设 9 是最小的。
比较剩余元素，发现 7 更小，所以将 7 与 9 交换位置。
第四轮结束后，数组变为 [2, 5, 6, 7, 9]，排序完成。

通过这个示例，我们可以清晰地看到选择排序每一轮的操作过程以及如何逐步将数组排序。

分割线

九、优化思路

虽然选择排序的基本算法已经比较简单直接，但在某些情况下，仍然可以考虑一些优化思路：

（一）减少交换次数

在找到最小元素的索引后，先不立即进行交换，而是在一轮比较结束后，如果最小元素的索引与当前位置不同，再进行一次交换。这样可以在一定程度上减少交换的次数，特别是在数组中元素重复较多的情况下。

（二）利用已排序部分的信息

在后续的轮次中，可以利用已经排序好的部分，缩小搜索最小元素的范围。但这种优化在选择排序中效果可能不太显著，因为选择排序的核心思想是每次选择未排序部分的最小元素。

分割线

十、总结

选择排序是一种简单但效率相对较低的排序算法。它的优点是实现简单，易于理解，空间复杂度低。缺点是时间复杂度较高，在处理大规模数据时性能不佳。在实际应用中，应根据具体情况选择合适的排序算法。如果数据量较小，或者对算法的简单性要求较高，选择排序可以是一个可行的选择。但对于大规模数据的排序，通常会优先考虑更高效的排序算法，如快速排序、归并排序等。

分割线