算法—排序
- 记录学习数据结构的总结,希望可以不拘泥于细节和语言,重视应用与推演.
资料来源如下
- 算法第四版
选择排序
步骤
- 寻找数组内最小的元素
- 与未排列的第一个元素交换位置.
- 重复1 2 知道数组排列完成.
代码
- 内循环 比较当前元素与已知最小元素
- 外循环 交换元素位置
性质
- 运行时间与输入无关..数组有序无序不影响时间.
- 数据移动最少.交换次数 与 数组长度 为线性关系.
- 长度为N的数组 , 选择排序 N2/2 次比较,及N次交换.
分析
- 最直观的排序算法.
- 无法利用数组的初始状态进行优化.(后续重点)
冒泡排序
步骤
- 遍历未排列数组,比较两个相邻元素,依照规则 交换/不交换位置.
- 重复1,直到完成数组排序.
代码
- 内循环 冒泡整个未排序数组
- 外循环 控制内循环 冒泡范围
分析
- 可能是效率最差的
- 实际效率与选择排序差不多.
插入排序
步骤
- 从第一个元素开始,该元素可以认为已经被排序
- 取出下一个元素,比较已排序序列,找到新元素位置
- 将新元素插入到该位置后
- 重复步骤直到排序完成.
代码
- 取出新元素
- 内循环查找新元素位置
- 插入新元素
- 外循环控制
性质
- 随机数组N, 平均需要 ~ N2/4 次比较及 ~N2/4 次交换.
- 最坏 N2/2 次比较 N2/2 次交换
- 最好 N-1 次比较 0 次交换(已经排序好的….😂)
分析
- 考虑了数组的初始状态,对于大多数元素有序的数组,插入排序可能是最快的.
- 但对于随机数组 还不够.
优化
- 查找新元素位置: 二分法查找.而不是遍历.
- 插入新元素时,算法第四版 建议,内循环改为类似冒泡方式,将大元素右移
希尔排序
对插入排序分析时,有这样的结论: 对于大多数元素有序的数组,插入排序时间最快,时间为线性级别.
将任意输入的数组 大多数元素有序,然后最后使用 插入排序.插入排序对于 随机数组的瓶颈 在于,一个元素到达正确位置,一次只能移动一位.那么一次可以移动多位,交换至很远位置,可以改善插入排序的性能.
思路: 将数组等间隔
h
分裂,进行插入排序.拆分后的子数组,插入排序成本较低,进行插入排序.完成后,原数组的有序性增加 插入排序成本降低,之后再进行颗粒度更细的拆分-排序.一级一级的降低 插入排序成本.直到最后进行
h=1
的插入排序.步骤
- 对数组进行间隔 h 的插入排序.
- 依照递增序列,取 h 值,直到 h = 1,为止,排序完成.
代码
- 内循环为 间隔 h 的插入排序
- 外循环为 计算 h 值的递增序列.
性质
- 希尔排序的性质并不容易概括,实际上没有完整概括.
- 目前可以证明的:希尔排序的运行时间 达不到 N2 级别.
分析
- 考虑了数组初始状态.是如今提到的排序算法中,第一个可以适用与大容量数组排序的.
- h 递增序列的选择,会很大程度上影响希尔排序效果.实际工程中适用那种,需要自行选择.
- 嵌入式系统中没有快排等库函数可选时,首选希尔排序.之后再考虑其他排序算法.
归并排序
归并排序的实现与插入/希尔/选择排序不同.
归并排序依赖于 归并操作.
- 归并 : 将两个有序数组 合并 为1个有序数组.
自顶向下 递归
- 实际上是一个 sort 的递归调用.
- 将数组分为 两个子数组
- 对子数组调用 调用sort
- 再对第二层子数组 调用 sort
- 直到最终子数组元素个数为1.递归返回 开始执行 merge()操作.
自底而上 迭代
- 直接归并 子元素为1 的各个数组到 子元素为2的数组.
- 再归并子元素为2 的各个数组 到子元素为4的数组.
- 最后 可能存在 数组元素不相等,但是不影响归并.
- 直到归并的数组元素为 N.
实际上 两者执行的过程是一样的,只是调用的角度不同.
性质
- 空间复杂度不是最优.
- 时间复杂度 NlogN
- 空间复杂度 N
优化
- 原理相同,对小的子数组 使用其他高效排序,再归并.
快速排序
应用最为广泛. 原地排序 时间成本 NlogN
但是! 坑不少…
原理
- 对于数组中 某个元素 都进行切分操作,大于/小于 该元素的所有元素 都在 一边. 将数组切分为2个子数组. 递归,直到切分子数组元素个数为1,完成排序.
- 与归并排序 在数组分解上 一致.
步骤
- 取出数组中某个元素 作为切分元素.
- 对数组执行切分.
- 对子数组执行 1 2 直到子数组元素个数为1.递归.
坑
- 原地切分,创建大量新对象性能上不可接受
- 保证访问不越界.
- 慎重处理最大最小元素.
- 相同元素谨慎处理.
性能改进
- 切分元素对性能影响及其重要.
- 最糟糕情况: 大部分元素有序,使用极值去切分.
- 为避免这种情况,快排之前,将输入数组乱序处理.
- 对于大型数组 取切分元素时 考虑去3 选 1.
- 小数组
- 使用切换到插入排序.
- 重复元素
- 一分为二,对于存在大量重复元素的数组,无效的比较次数较多.
- 改为 三取样切分
- 切分元素对性能影响及其重要.
三切分取样
- 切分时,不再一分为二,改为 < = >.三部分
- 三项切分的信息量最优.
- 对于存在大量重复元素的数组,三切分取样,直接将时间 由 NlogN 降低到了 N .
相关文章