3 种简单算法总结


3 种简单算法总结

image-20190731193936927

插入排序,在业务中,使用是最多的。其他 2 种排序,只是用来涨涨见识而已。

相同点

都分为 有序区间 和 非有序区间。

例如,在冒泡排序中,我们每次,都会找到最大的数字,将其放到最右边(右边已经排序好了)。

在插入排序中,我们每次都将 i 的值,放到对应的位置(左边已经排序好了)。

在选择排序中,我们每次追加的,都是最小的值,左边都是有序的。右边都是无序的。

他们的时间复杂度都是 On^2; 且他们都是原地排序。

不同点

关于稳定性,选择排序不是稳定的(当第一位的元素是重复的时候,改元素会被换到后面去)。

冒泡和插入都是有序的。

同时,在冒泡和插入的选择上,虽然时间复杂度都是 On^2, 但是,我们通常会使用插入排序,因为他的交换操作只有 一步,而冒泡有 3 步。

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×