为啥说选择排序是不稳定的

简介: 选择排序是一种简单但不稳定的排序算法。它通过每轮选择最小元素并交换位置来实现排序,但这种交换可能破坏相同值元素的相对顺序。例如对数组 `[5, 8, 5, 2]` 排序后,两个 `5` 的顺序会发生变化,从而证明其不稳定性。

选择排序被认为是不稳定的排序算法,主要是因为在排序过程中,它会通过交换元素位置来将最小(或最大)的元素放到正确的位置,而这种交换操作可能会破坏具有相同值的元素之间的相对顺序。

原理分析

选择排序的基本思想是:每一轮从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置(或末尾位置),然后再从剩余未排序元素中继续寻找最小(或最大)元素,然后放到已排序序列的末尾,以此类推,直到全部待排序的数据元素排完。

在这个过程中,选择排序会不断地将当前未排序部分的最小元素与未排序部分的第一个元素交换位置。这种交换操作是导致选择排序不稳定的关键原因。

实例说明

假设有一个数组 [5, 8, 5, 2],我们使用选择排序对其进行升序排序:

  1. 初始状态:[5, 8, 5, 2]
  2. 第1轮:找到最小元素 2,与第一个元素 5 交换位置,得到 [2, 8, 5, 5]
  3. 第2轮:从剩余元素 [8, 5, 5] 中找到最小元素 5,与第一个元素 8 交换位置,得到 [2, 5, 8, 5]
  4. 第3轮:从剩余元素 [8, 5] 中找到最小元素 5,与第一个元素 8 交换位置,得到 [2, 5, 5, 8]

在这个例子中,原数组中的两个 5 的相对顺序被改变了。初始时,第一个 5 在第二个 5 之前,但经过排序后,第二个 5 被交换到了第一个 5 之前。这就说明选择排序没有保持相等元素的相对顺序,因此它是不稳定的。

代码验证

下面是选择排序的Python实现,通过运行这段代码可以观察到元素相对顺序的变化:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # 交换当前元素与最小元素
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# 测试用例
arr = [5, 8, 5, 2]
sorted_arr = selection_sort(arr)
print("排序前:", [5, 8, 5, 2])
print("排序后:", sorted_arr)

运行这段代码,输出结果为:

排序前: [5, 8, 5, 2]
排序后: [2, 5, 5, 8]

可以看到,排序后的两个 5 的顺序与原始顺序相比发生了变化,这验证了选择排序的不稳定性。

目录
相关文章
|
数据采集 存储 算法
终于有人把数据挖掘讲明白了
在大数据时代,许多企业面临一个难题:数据存储量庞大,却难以从中挖掘真正价值。本文深入探讨了数据挖掘的核心概念与实践方法,解析了其与普通数据分析的区别,并通过真实案例展示了如何通过数据挖掘发现隐藏的业务规律。文章还详细介绍了数据挖掘的六个步骤及三大关键点,强调了业务理解与数据质量的重要性,帮助企业在实际应用中少走弯路,真正实现数据驱动决策。
终于有人把数据挖掘讲明白了
|
机器学习/深度学习 传感器 算法
【机器学习】多元线性回归基本概念
【1月更文挑战第23天】【机器学习】多元线性回归基本概念
|
6月前
|
JSON 测试技术 API
Opus4.7 长链路流式输出里,​D​М‌X​Α‌РΙ 的稳态调用方案
Claude-Opus-4.7-cc 火热,不仅因它在复杂推理、长文本与多轮约束任务中表现卓越,更因它推动大模型从“灵感助手”升级为“流程中的责任节点”。其真正价值在于支撑可回放、可审计、可度量的企业级链式任务——而这必须依托 DМXΑРΙ 等工程化底座,实现协议治理、确定性调用与全链路可观测。
|
8月前
|
人工智能 API iOS开发
OpenClaw是什么?OpenClaw能做什么?OpenClaw介绍及+阿里云/本地部署+免费大模型配置教程
OpenClaw(前身为Clawdbot/Moltbot)是一款遵循MIT协议的开源AI自动化代理引擎,以“本地优先、可执行任务”为核心定位,实现了从“对话式建议”到“自动化执行”的跨越。它区别于传统对话式AI,通过“意图解析→任务规划→工具调用→结果反馈”的完整闭环,在本地或私有云环境中完成文件操作、流程编排、浏览器自动化等真实任务,成为个人与企业的自托管式AI数字员工。本文将详细解析OpenClaw的核心特性与应用场景,完整呈现2026年阿里云及本地MacOS/Linux/Windows11的部署流程,提供阿里云百炼及Coding Plan免费大模型的配置方法,并整理常见问题解答,帮助用户
1328 8
|
11月前
|
运维 关系型数据库 Linux
Linux 高效学习指南:从入门到运维的科学路径
本文提供Linux高效学习路径,倡导“场景驱动”学习法,避免死记硬背。涵盖四大阶段:1周入门掌握核心命令,2周深化理解系统原理,2周实战部署LNMP服务,长期进阶自动化运维。强调动手实操、问题驱动与循序渐进,助力快速构建完整知识体系,成为具备实战能力的运维人才。
1328 0
|
12月前
|
Java Swift Android开发
Kotlin vs Swift:现代移动开发的“双子星”全面对比
Kotlin与Swift是现代移动开发的两大主流语言,分别主导Android与iOS生态。本文全面对比二者在语法、空安全、并发、性能及跨平台等方面的异同,深入解析其设计理念与适用场景,助你根据平台需求与技术战略做出最优选择。
923 0
|
数据采集 消息中间件 JavaScript
浏览器渲染揭秘:从加载到显示的全过程;浏览器工作原理与详细流程
了解浏览器工作原理与流程,能有效帮助前端开发与性能优化。 博客不应该只有代码和解决方案,重点应该在于给出解决方案的同时分享思维模式,只有思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
|
SQL Java 关系型数据库
使用 JDBC 实现 Java 数据库操作
JDBC(Java Database Connectivity)是 Java 提供的数据库访问技术,允许通过 SQL 语句与数据库交互。本文详细介绍了 JDBC 的使用方法,包括环境准备、编程步骤和完整示例。
1506 7
|
消息中间件 测试技术 领域建模
DDD - 一文读懂DDD领域驱动设计
DDD - 一文读懂DDD领域驱动设计
52936 6
|
Web App开发 缓存 JavaScript
如何检测和解决闭包引起的内存泄露
闭包引起的内存泄露是JavaScript开发中常见的问题。本文介绍了闭包导致内存泄露的原因,以及如何通过工具检测和代码优化来解决这些问题。