插入排序和选择排序的区别

插入排序

  • 在插入排序中，值被插入到列表/数组中，其中一些值是先前排序的。

  • 它是一种稳定的排序算法。

  • 最佳情况时间复杂度为 O(N)（当列表已按升序排序时）。

  • 定义一个键值，并从头到尾迭代数组。

  • 迭代期间的当前元素与键值进行比较。

  • 插入排序期间进行的比较操作次数少于执行的元素交换次数。

  • 如果键元素小于与其比较的元素，则将其与之前的元素进行比较。

  • 大于键的元素向上移动一个位置，为要交换的元素腾出空间。

  • 元素是预先知道的，只有它们的位置在插入排序期间确定。

选择排序

  • 在选择排序中，首先从列表中获取最小或最大数。

  • 列表按升序或降序排序。

  • 它被认为是一种不稳定的排序算法。

  • 在所有情况下，时间复杂度都是 O(n 平方)。

  • 与插入排序相比，效率较低。

  • 迭代期间进行的比较次数多于执行的元素交换次数。

  • 列表中每个元素的位置是预先知道的。

  • 这意味着用户只需搜索需要插入到特定位置的元素。

更新于: 2021年3月23日

2K+ 阅读量

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告