知识卡片
插入排序移动量由逆序对决定
标准稳定插入排序每次把较大的前缀元素右移一位;右移次数等于输入中严格逆序对的数量。互异逆序输入有n(n−1)/2对,均匀随机排列的期望为n(n−1)/4;已有序输入为0次右移,但仍有线性轮次和比较。
03192比较逐项移动与块移动在历史平台上的时间;memmove可改善复制常数,但最坏移动的字节总量仍随n²增长。实验中若每个元素占s字节,成本分析也应保留s;n加倍耗时接近四倍只能支持观察范围,不能单独证明渐近界。
重复键通常减少严格逆序对,但“唯一基于比较的排序算法”明显不对,本章后续还有快速排序和堆排序;已有序输入也并非现实中没有价值。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
二次方的运行时间,O(n2)。 插入排序对于基于值的数据效率很低,因为很多内存需要移位,以给新的值腾出位置。表4-1包含了在直接比较。我们将会执行10次随机实验,排序n个元素,最好和最坏结果将会被抛弃。这个表给出了剩余8次结果的平均值。注意这个实现是如何通过内存块移动而不是通过单独的内存交换来改善性
参考来源
- 位置:《算法技术手册》第4章《分析》(spine1501;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1464.html;u072-ch04-010)。
- 结论依据:72全文、03192所有数据行及03189–03191严格比较实现实读;逆序对计数是读者推导。
- 原始内容:二次方的运行时间,O(n2)。 插入排序对于基于值的数据效率很低,因为很多内存需要移位,以给新的值腾出位置。表4-1包含了在直接比较。我们将会执行10次随机实验,排序n个元素,最好和最坏结果将会被抛弃。这个表给出了剩余8次结果的平均值。注意这个实现是如何通过内存块移动而不是通过单独的内存交换来改善性