优化后的冒泡排序似乎并没有体现出优势？

Question

Answer 1

liuyubobobo 2017-11-14 17:09:03

优化的冒泡排序主要是对于有序或者近乎有序的数据情况下大幅提速，可以试一下生成一个近乎有序的数据进行实验：）

对于近乎有序的数据，加大数据量试试看：）

• 提问者 Lavanille777 #1

  在近乎有序的情况下发现相对于未优化的冒泡排序确实有一定提升，但速度还是不如插入排序，是这样吗？

• liuyubobobo 回复 提问者 Lavanille777 #2

  至少把测试结果抬到秒这个级别。你现在的测试结果连毫秒级别都没到，太细微了。操作系统的一点点任务调动都会极大的干扰结果。最终的结果视你的编译器版本运行环境等而定。整体上对于近乎有序的情况，优化的冒泡应该比插入慢一些，因为swap操作的原因。但不是定论。不一定每次都是这样的结果，对于不同数据更不一定。其实对于大多数人，在现代计算机环境下工作，对于大多数算法，在复杂度一致的情况下，比较谁快谁慢，意义没有那么大。这种常数级别的考量，已经是专业算法领域论文讨论的范畴了。

• 提问者 Lavanille777 回复 liuyubobobo #3

  明白了，谢谢老师！