跳转到内容
主菜单
主菜单
移至侧栏
隐藏
导航
首页
最近更改
随机页面
MediaWiki帮助
代码酷
搜索
搜索
中文(中国大陆)
外观
创建账号
登录
个人工具
创建账号
登录
未登录编辑者的页面
了解详情
贡献
讨论
编辑“︁
排序算法概述
”︁(章节)
页面
讨论
大陆简体
阅读
编辑
编辑源代码
查看历史
工具
工具
移至侧栏
隐藏
操作
阅读
编辑
编辑源代码
查看历史
常规
链入页面
相关更改
特殊页面
页面信息
外观
移至侧栏
隐藏
您的更改会在有权核准的用户核准后向读者展示。
警告:
您没有登录。如果您进行任何编辑,您的IP地址会公开展示。如果您
登录
或
创建账号
,您的编辑会以您的用户名署名,此外还有其他益处。
反垃圾检查。
不要
加入这个!
= 排序算法概述 = 排序算法是计算机科学中最基础且重要的算法类别之一,用于将一组数据按照特定顺序(如升序或降序)重新排列。排序算法广泛应用于数据库检索、数据分析、任务调度等领域,其效率直接影响程序的整体性能。 == 基本概念 == 排序算法的核心目标是将无序序列转换为有序序列。常见的排序依据包括: * '''数值大小'''(如整数、浮点数) * '''字典序'''(如字符串) * '''自定义规则'''(如对象按属性排序) 排序算法的评价标准通常包括: * '''时间复杂度''':算法执行所需时间与输入规模的关系 * '''空间复杂度''':算法运行所需的额外存储空间 * '''稳定性''':相等元素的相对顺序是否保持不变 == 常见分类 == 排序算法可分为两大类: === 比较排序 === 通过比较元素决定其顺序,理论最优时间复杂度为<math>O(n \log n)</math>。典型算法包括: * [[冒泡排序]] * [[快速排序]] * [[归并排序]] === 非比较排序 === 不直接比较元素,利用数据特性实现排序,可突破<math>O(n \log n)</math>限制。典型算法包括: * [[计数排序]] * [[基数排序]] * [[桶排序]] <mermaid> pie title 排序算法使用频率 "快速排序" : 45 "归并排序" : 25 "堆排序" : 15 "其他" : 15 </mermaid> == 算法示例 == === 冒泡排序(Python实现) === <syntaxhighlight lang="python"> def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] # 示例 data = [64, 34, 25, 12, 22, 11, 90] bubble_sort(data) print("排序结果:", data) </syntaxhighlight> '''输出:''' <pre> 排序结果: [11, 12, 22, 25, 34, 64, 90] </pre> === 快速排序(Python实现) === <syntaxhighlight lang="python"> def quick_sort(arr): if len(arr) <= 1: return arr pivot = arr[len(arr)//2] left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return quick_sort(left) + middle + quick_sort(right) # 示例 data = [3,6,8,10,1,2,1] print("排序结果:", quick_sort(data)) </syntaxhighlight> '''输出:''' <pre> 排序结果: [1, 1, 2, 3, 6, 8, 10] </pre> == 性能比较 == {| class="wikitable" |+ 常见排序算法复杂度对比 ! 算法 !! 平均时间复杂度 !! 最坏时间复杂度 !! 空间复杂度 !! 稳定性 |- | 冒泡排序 || <math>O(n^2)</math> || <math>O(n^2)</math> || <math>O(1)</math> || 稳定 |- | 快速排序 || <math>O(n \log n)</math> || <math>O(n^2)</math> || <math>O(\log n)</math> || 不稳定 |- | 归并排序 || <math>O(n \log n)</math> || <math>O(n \log n)</math> || <math>O(n)</math> || 稳定 |- | 堆排序 || <math>O(n \log n)</math> || <math>O(n \log n)</math> || <math>O(1)</math> || 不稳定 |} == 实际应用案例 == '''场景1:电子商务价格排序''' 在线商城需要实时对数百万商品按价格排序,通常采用混合策略: * 内存中使用快速排序处理当前页数据 * 数据库层使用归并排序处理大规模数据 '''场景2:学生成绩排名''' 学校管理系统需要稳定排序算法保持同分学生的原始录入顺序,适合使用: * 归并排序(稳定) * 带有原始索引的基数排序 == 学习建议 == 初学者应按以下顺序掌握排序算法: # 理解基本概念(时间复杂度、稳定性) # 实现简单算法(冒泡、选择、插入排序) # 研究分治算法(快速、归并排序) # 学习线性时间排序(计数、基数排序) # 分析实际场景中的算法选择 <mermaid> graph TD A[理解排序概念] --> B[实现基础算法] B --> C[学习分治策略] C --> D[掌握线性排序] D --> E[实际应用分析] </mermaid> == 进阶话题 == * 自适应排序(Adaptive Sort) * 外部排序(处理超出内存的数据集) * 并行排序算法(MapReduce实现) * 混合排序策略(Timsort等) [[Category:计算机科学]] [[Category:数据结构与算法]] [[Category:排序算法]]
摘要:
请注意,所有对代码酷的贡献均被视为依照知识共享署名-非商业性使用-相同方式共享发表(详情请见
代码酷:著作权
)。如果您不希望您的文字作品被随意编辑和分发传播,请不要在此提交。
您同时也向我们承诺,您提交的内容为您自己所创作,或是复制自公共领域或类似自由来源。
未经许可,请勿提交受著作权保护的作品!
取消
编辑帮助
(在新窗口中打开)