算法—排序

发表于 2018-06-02 更新于 2018-06-12 分类于数据结构阅读次数： Disqus：本文字数： 1.8k 阅读时长 ≈ 2 分钟

资料来源如下

选择排序

步骤
- 寻找数组内最小的元素
- 与未排列的第一个元素交换位置.
- 重复1 2 知道数组排列完成.
代码
- 内循环比较当前元素与已知最小元素
- 外循环交换元素位置
性质
- 运行时间与输入无关..数组有序无序不影响时间.
- 数据移动最少.交换次数与数组长度为线性关系.
- 长度为N的数组 , 选择排序 N2/2 次比较,及N次交换.
分析
- 最直观的排序算法.
- 无法利用数组的初始状态进行优化.(后续重点)

步骤
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素,比较已排序序列,找到新元素位置
- 将新元素插入到该位置后
- 重复步骤直到排序完成.
代码
- 取出新元素
- 内循环查找新元素位置
- 插入新元素
- 外循环控制
性质
- 随机数组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.
- 小数组
  - 使用切换到插入排序.
- 重复元素
  - 一分为二,对于存在大量重复元素的数组,无效的比较次数较多.
  - 改为三取样切分