【排序算法】选择排序的全面剖析（含详细图解）

😌首先，遍历整个数组，找到最小的元素。

假设第一个元素是最小的，然后从第二个元素开始逐个与它比较。
如果发现有比当前假设的最小元素更小的元素，就更新最小元素的索引。

😜当遍历完整个数组后，将找到的最小元素与数组的第一个元素交换位置。

此时，数组的第一个元素就是最小的，已经处于正确的位置。

😛接着，在剩下的未排序元素（从第二个元素开始到最后一个元素）中重复上述步骤。

再次遍历剩余元素，找到其中最小的元素，并与剩余元素中的第一个元素（即数组的第二个元素）交换位置。

😝不断重复这个过程

每次都将剩余未排序元素中的最小元素放置在已排序部分的末尾，直到整个数组都被排序。

🌷以如下所示的数组为例:

对于已排序列表中的第一个位置，整个列表按顺序扫描。目前存储 14 的第一个位置，我们搜索整个列表，发现 10 是最低值。

所以我们用 10 替换 14。经过一次迭代，10（恰好是列表中的最小值）出现在已排序列表的第一个位置。

对于第二个位置，即 33 所在的位置，我们开始以线性方式扫描列表的其余部分。

我们发现 14 是列表中的第二小值，它应该出现在第二个位置。我们交换这些值。

经过两次迭代，两个最小的值以排序的方式出现在开头。

😏对数组中的其余项应用相同的过程:

⭐代码实现

以下是用 C 语言实现的简单选择排序代码：

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 交换最小元素和当前位置的元素
        if (minIndex!= i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

⭐示例说明

假设我们有一个数组[5, 3, 8, 4, 2]，

😁下面是选择排序的具体过程：

第一次遍历：
初始假设第一个元素5是最小的，minIndex = 0。
从第二个元素3开始比较，发现3 < 5，更新minIndex = 1。
继续比较后面的元素8、4、2，都比3大。
遍历完后，将3与第一个元素5交换，数组变为[3, 5, 8, 4, 2]。
第二次遍历：
现在从第二个元素5开始（因为第一个元素已经排好序），假设5是最小的，minIndex = 1。
比较8、4、2，发现2最小，更新minIndex = 4。
将2与第二个元素5交换，数组变为[3, 2, 8, 4, 5]。
第三次遍历：
从第三个元素8开始，假设8是最小的，minIndex = 2。
比较4、5，发现4更小，更新minIndex = 3。
将4与第三个元素8交换，数组变为[3, 2, 4, 8, 5]。
第四次遍历：
从第四个元素8开始，假设8是最小的，minIndex = 3。
比较5，5比8小，更新minIndex = 4。
将5与第四个元素8交换，数组变为[3, 2, 4, 5, 8]，此时数组已完全排序。

💯选择排序的时间复杂度分析

⭐最好情况时间复杂度

在最好情况下，即数组本身就是有序的（升序或降序），选择排序的时间复杂度仍然是 $O(n^2)$ 。这是因为无论数组是否有序，每次都需要遍历剩余未排序的元素来找到最小（或最大）元素。虽然在最好情况下，每次找到的最小元素总是已经在正确的位置（即第一个未排序元素就是最小的），但仍然需要进行 $n-1$ 次比较和 $n-1$ 次交换（假设数组有 $n$ 个元素）。比较次数的计算公式为： $\sum_{i = 0}^{n - 2}(n - i - 1)=\frac{n(n - 1)}{2}$ ，交换次数为 $n-1$ ，忽略常数系数和低阶项，时间复杂度为 $O(n^2)$ 。

⭐最坏情况时间复杂度

在最坏情况下，数组是完全逆序的（升序排序时）或完全正序的（降序排序时）。此时，每次选择最小（或最大）元素都需要遍历整个未排序部分，比较次数和交换次数与最好情况相同，都是 $O(n^2)$ 。具体来说，比较次数为 $\frac{n(n - 1)}{2}$ ，交换次数为 $n-1$ ，所以时间复杂度也是 $O(n^2)$ 。

⭐平均情况时间复杂度

平均情况下，选择排序也需要大约 $\frac{n(n - 1)}{2}$ 次比较和 $n-1$ 次交换。因此，平均时间复杂度同样为 $O(n^2)$ 。

💯选择排序的空间复杂度分析

选择排序是一种原地排序算法，它只需要常数级别的额外空间。在排序过程中，只需要使用一些临时变量来记录最小元素的索引和进行元素交换，不需要额外的数据结构来存储数据。因此，空间复杂度为 $O(1)$ 。

💯选择排序的稳定性分析

😃选择排序是不稳定的排序算法。稳定性是指在排序过程中，如果两个元素相等，它们在排序后的相对顺序是否会保持不变。在选择排序中，当在未排序部分找到最小元素并与已排序部分的元素交换时，如果有多个相等的最小元素，它们的相对顺序可能会发生改变。

例如，有一个数组[5, 3, 5', 4, 2]（其中5'表示另一个值为5的元素），在第一次排序时，会将最小的元素2与第一个元素5交换，此时5'的相对位置就发生了变化。原本5'在5后面，排序后5'可能会在5的前面，所以选择排序不稳定。

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

⭐与冒泡排序比较

时间复杂度：
选择排序和冒泡排序的时间复杂度在最坏、最好和平均情况下都是 $O(n^2)$ 。
但是，在实际运行中，选择排序通常会比冒泡排序稍微快一些。这是因为冒泡排序在每一次比较后都可能进行交换操作，而选择排序是在一次遍历完未排序部分找到最小元素后才进行一次交换。
稳定性：
冒泡排序是稳定的排序算法，而选择排序是不稳定的。
代码实现复杂度：
两者的代码实现都相对简单，但是冒泡排序的代码可能更容易理解一些，因为它的交换操作是相邻元素之间进行的，比较直观。而选择排序需要记录最小元素的索引，然后进行交换，逻辑上稍微复杂一点。

⭐与插入排序比较

时间复杂度：
插入排序在最好情况下（数组已经有序）时间复杂度为 $O(n)$ ，平均和最坏情况下时间复杂度为 $O(n^2)$ 。而选择排序在所有情况下时间复杂度都是 $O(n^2)$ 。
当数组接近有序时，插入排序的性能会比选择排序好很多，因为插入排序在这种情况下可以很快地将新元素插入到已排序部分的合适位置，而选择排序仍然需要进行大量的比较和交换。
稳定性：
插入排序是稳定的排序算法，选择排序不稳定。
空间复杂度：
两者的空间复杂度都是 $O(1)$ ，都是原地排序算法。
适用场景：
如果数据量较小且基本有序，插入排序更合适。如果数据的有序性不确定，且对稳定性没有要求，选择排序可以作为一种简单的选择。

⭐与快速排序比较

时间复杂度：
快速排序的平均时间复杂度为 $O(nlogn)$ ，在最坏情况下时间复杂度会退化为 $O(n^2)$ （当分区极度不平衡时）。选择排序始终是 $O(n^2)$ 。
因此，在大多数情况下，快速排序比选择排序效率高得多。
稳定性：
快速排序也是不稳定的排序算法，和选择排序一样。
空间复杂度：
快速排序的空间复杂度在平均情况下为 $O(logn)$ （由于递归调用需要栈空间），最坏情况下为 $O(n)$ 。选择排序的空间复杂度为 $O(1)$ 。
适用场景：
对于大规模数据的排序，快速排序通常是更好的选择，因为它的平均性能更好。但如果对稳定性有要求或者数据量较小，并且不希望使用递归（因为递归可能会导致栈溢出等问题），选择排序可能更合适。

💯总结

选择排序是一种简单易懂的排序算法，其原理直观，代码实现相对容易。它具有原地排序和时间复杂度始终为 $O(n^2)$ 的特点，适用于数据量较小且对算法效率要求不高的场景。

✍在理解排序算法的基本思想和进行简单数据排序时，选择排序是一个很好的学习和实践案例。

💝💝💝感谢你看到最后，点个赞再走吧！💝💝💝我的主页👉【A Charmer】

原文地址：https://blog.csdn.net/2301_82213854/article/details/142886998

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Spring Boot动态数据源切换功能详解
下一篇：从Maya对象中获取单个坐标值

AI+智慧电池数据集
6+智慧电池AI数据集，涉及电池充放电、烟雾检测、隔膜检测、生产温度预测等多应用领域
阅读更多2024-10-15
【力扣刷题实战】链表的中间结点
文章目录目录力扣题目：链表的中间结点题目描述示例 1：示例 2：解题思路问题理解算法选择具体思路解题要点完整代码（C语言）兄弟们共勉！！！每篇前言
阅读更多2024-10-15
深入理解UML类图：掌握类与关系的设计奥秘
类表示系统中的一种实体，主要是由名称、属性和操作组成。在UML中，类表达成一个有三个分隔区的矩形。其中顶端显示类名，中间显示类的属性，尾端显示类的操作。1、类必须各自有不同的类名称正体书写：可以实例化
阅读更多2024-10-15
【makefile】项目管理make & 基本用法
刚才提及的都是编译的目标，所以应该都是输出文件作为目标，而输出文件多多少少都会有依赖文件，而伪目标不是文件，所以他一定没有依赖/这么说其实太绝对后面其实发现不一定。有了伪目标之后，makefile的目
阅读更多2024-10-15
Redis日常运维
作为一名资深运维工程师，了解 Redis 的不同架构模式及其优缺点是非常重要的。此外，监控 Redis 的关键指标也是确保其稳定运行的关键。以下是对这些问题的详细解答。
阅读更多2024-10-15
D37【python 接口自动化学习】- python基础之函数
定义变量的参数是实参，调用函数的参数是形参...
阅读更多2024-10-15
大模型时代产品经理攻略：成功必备的几点深度思考_ai时代先上车
随着人工智能技术的飞速发展，大模型时代已经到来，对产品经理提出了更高的要求和挑战。在这个新的时代背景下，产品经理需要不断思考和探索，以适应和引领市场的变化。
阅读更多2024-10-15
如何提高 PCDN 的网络安全防护能力（壹）
可以显著提高 PCDN 的网络安全防护能力，保障内容分发的安全可靠，为用户提供稳定、放心的服务。如果您对PCDN的技术特点、应用场景、市场竞争和成本投入有深入了解，并且认为它符合您的业务需求和市场定位
阅读更多2024-10-15
计算机网络-RSTP快速生成树基础概念
在启动了环路保护功能后，如果根端口或Alternate端口长时间收不到来自上游设备的BPDU报文时，则向网管发出通知信息（此时根端口会进入Discarding状态，角色切换为指定端口），而Altern
阅读更多2024-10-15
Python3 接口自动化测试，HTTPS下载文件(GET方法和POST方法)
Python3 接口自动化测试，HTTPS下载文件(GET方法和POST方法)
阅读更多2024-10-15