情景回顾

上节回顾：C语言的十大组数之冒泡排序法的应用

本节重点

本节重点：C语言的十大组数排序法：选择排序！竟然可以这么快！

关注不迷路

微信公众号：工控小新

学习工控知识就来工控小新，为你提供工控笔记知识：EPLAN电气绘图 | TIA博图基础 | CAD | C语言教学 | 单片机基础 | 三菱PLC ... 每日持续更新中

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n^2) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

本文将介绍选择排序的原理、实现和优缺点，以及如何用C语言编写选择排序的代码。

选择排序的原理

选择排序的基本思想是，首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

例如，给定一个数组 arr = [9, 6, 15, 4, 2]，我们要对它进行升序排序，那么选择排序的过程如下：

• 第一轮，从 arr[0] 到 arr[4] 中找到最小的元素 arr[4] = 2，将它与 arr[0] 交换，得到 arr = [2, 6, 15, 4, 9]。
• 第二轮，从 arr[1] 到 arr[4] 中找到最小的元素 arr[3] = 4，将它与 arr[1] 交换，得到 arr = [2, 4, 15, 6, 9]。
• 第三轮，从 arr[2] 到 arr[4] 中找到最小的元素 arr[3] = 6，将它与 arr[2] 交换，得到 arr = [2, 4, 6, 15, 9]。
• 第四轮，从 arr[3] 到 arr[4] 中找到最小的元素 arr[4] = 9，将它与 arr[3] 交换，得到 arr = [2, 4, 6, 9, 15]。

此时，所有元素已经排序完毕，选择排序结束。

选择排序的实现

要用C语言实现选择排序，我们需要定义一个函数，接受一个数组和它的长度作为参数，然后对数组进行选择排序。我们还需要定义一个辅助函数，用来交换两个元素的值。代码如下

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


// 选择排序
void selection_sort(int arr[], int n) 
{
    // i 表示已排序序列的末尾
    for (int i = 0; i < n - 1; i++) 
    {
        // min_index 表示未排序序列中最小元素的下标
        int min_index = i;
        // j 用来遍历未排序序列，寻找最小元素
        for (int j = i + 1; j < n; j++) 
        {
            // 如果找到比当前最小元素更小的元素，更新 min_index
            if (arr[j] < arr[min_index]) 
            {
                min_index = j;
            }
        }
        // 将最小元素与已排序序列的末尾交换
        swap(&arr[i], &arr[min_index]);
    }
}

选择排序的优缺点

选择排序的优点是：

• 简单易懂，实现容易。
• 不占用额外的内存空间，是一种原地排序算法。
• 交换次数较少，最多进行 n - 1 次交换。

选择排序的缺点是：

• 时间复杂度较高，无论数据是否有序，都需要进行 O(n^2) 次比较。
• 不稳定，即相同的元素可能会改变原来的相对顺序。

总结

选择排序是一种简单直观的排序算法，它的基本思想是，每次从未排序序列中找到最小（大）元素，放到已排序序列的末尾，直到所有元素均排序完毕。选择排序的时间复杂度是 O(n^2)，空间复杂度是 O(1)，交换次数是 O(n)，是一种不稳定的原地排序算法。选择排序适合数据规模较小的情况，如果数据规模较大，可以考虑其他更高效的排序算法。

#头条创作挑战赛#