search

hfuuss / algorithm-JS

ACM算法总结 总结在Issues里面
1 stars 0 forks source link

为什么插入排序比冒泡排序更受欢迎? #11

Open hfuuss opened 5 years ago

hfuuss commented 5 years ago

基本的知识都讲完了，我们来看开篇的问题:冒泡排序和插入排序的时间复杂度都是O(n2)，都是原地排序算法，为什么插入排序要比冒泡排序更受欢迎呢? 我们前面分析冒泡排序和插入排序的时候讲到，冒泡排序不管怎么优化，元素交换的次数是一个固定值，是原始数据的逆序度。插入排序是同样的，不管怎么优 化，元素移动的次数也等于原始数据的逆序度。 但是，从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要3个赋值操作，而插入排序只需要1个。

hfuuss commented 5 years ago

image

hfuuss commented 5 years ago

冒泡排序、插入排序、选择排序 O(n^2) 快速排序、归并排序 O(nlogn) 计数排序、基数排序、桶排序 O(n)