Toptal连接了前3%的 自由开发人员 世界各地.
接近排序的初始顺序
动画,代码,分析和讨论8排序算法在近排序的初始顺序.
讨论
对几乎排序的数据进行排序在实践中是很常见的. 一些观察:
- 在这个初始条件下,插入排序显然是赢家.
- 冒泡排序速度很快,但插入排序的开销较低.
- 壳牌排序很快,因为它基于插入排序.
- 合并排序、堆排序和快速排序不适应几乎排序的数据.
插入排序提供一个O(n)2)最坏情况算法,当数据接近排序时适应O(n)时间. One would like an O(n·lg(n)) algorithm that adapts to this situation; smoothsort is such an algorithm, 但是很复杂. 壳牌排序是这里显示的唯一的次二次算法,在这种情况下也是自适应的.
关键
- 黑色值排序.
- 灰度值未排序.
- 红色三角形标记算法位置.
- 深灰色值表示当前间隔(shell、merge、quick).
- 一对红色三角形标记了左右指针(快速).