马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
×
目次
排序的分类
根本概念
插入排序
直接插入排序
折半插入排序
希尔排序
交换排序
冒泡排序
快速排序
选择排序
简朴选择排序
堆排序
二路归并排序
基数排序
选择算法必要思量的因素
排序的分类
此中比力告急的已做标记，下面来扼要先容一下
根本概念
排序的界说:对一个数据元素聚集或序列重新分列成一个按数据元素某项值有序的序列
稳固性:雷同关键码元素间的位置关系，排序前后保持同等则稳固，不同等的不稳固
插入排序
- 直接插入排序
- 从前(第二个关键字)今后遍历，依次插入到前面已经排好序的子序列当中
- 时复
 (n^2) 空复(1) 稳固 实用:次序和链式
- 图示
- 折半插入排序
- 利用折半查找来探求待插元素的插入位置
- 时复(n^2) 空复(1) 稳固 实用:次序
- 希尔排序
- 缩小增量排序，把关键字隔肯定的巨细分组，终极序列根本有序，再举行一次直接插入排序
- 时最坏(n^2) 空(1) 不稳固 实用:次序
- 图示
交换排序
- 冒泡排序
- 像吐泡泡一样徐徐得到最大(或最小)的关键字。两两比力，若逆序则交换
- 时复(n^2) 空复(1) 稳固 实用:次序和链式
- 图示
- 快速排序
- 基于分治头脑，每次选择第一个元素为基准元素，比基准元素大的放一边，小的放一边，终极有序。代码中有递归，必要借助递归栈
- 时复(n^2) 空复:最坏o(n^2)，最好o(log n) 不稳固 实用:次序
- 图示
选择排序
- 简朴选择排序
- 每一趟确定一个最小(或最大)的元素，放到终极位置处(与该处元素交换)
- 时复(n^2) 空复:o(1) 不稳固 实用:次序和链式和关键字较少的情况
- 堆排序
- 建堆(大根or小根)，堆是一个完全二叉树情势，每次在根节点处会得到最大(或最小)的元素，与末了一个叶节点交换，重新整理堆，以此类推
- 时复:o(n log n) 建堆时间:o(n) 空复:o(1) 不稳固 实用:次序和链式
- 图示（具体解说）
二路归并排序
- 将两个或两个以上的有序表归并成一个新的有序表，有序表中重新到尾举行比力。先是每两个元素归并，再是四个元素归并，以此类推
- 每次归并时必要把表复制一遍，每趟归并时间复杂度为o(n)，必要举行(log n)次归并
- 时复:o(n log n) 空复:o(n) 稳固 实用:次序和链式
- 图示
基数排序
- 从个位开始，依次往进步行排序(也就是优先度越高的越晚排序),必要借助队列来存储每次按位排序的链表
- 时间复杂度表明：必要举行d趟位(关键字差异则d差异)排序，一趟遍历全部关键字，时间复杂度O(n),一趟必要归并r个队列
- 时复:O(d(n+r)) 空复:o(r) 稳固 实用:次序和链式
选择算法必要思量的因素
- 待排序的元素个数n
- 待排序的元素的初始状态
- 关键字的结构及分布情况
- 稳固性的要求
- 存储结构及辅助空间的巨细限定
|
发表于 2026-2-14 04:43:20