• 技术文章 >Python技术 >Python基础教程

    python插入排序的性能问题

    小妮浅浅小妮浅浅2021-09-08 11:53:59原创135

    1、空间复杂度是O(1),是原地排序算法。

    除了运行时需要临时变量存储交换的数据和下标外,不需要额外的存储空间。

    2、稳定性,对于值相同的元素,选择将后面出现的元素插入前面出现的元素后面。

    这样可以保证原来的前后顺序不变,所以是一种稳定的排序算法。

    3、时间复杂度,最好的时间复杂度是O(n)。

    如果数据有序,不需要移动任何数据。在搜索插入位置时,我们可以从尾到尾在有序区间搜索插入位置,每次只需要比较一次就可以确定插入位置。如果数据是倒序的,每次都相当于在数据的第一位插入新数据,所以需要移动大量的数据,最坏的时间复杂度是O(n^2)。平常时间复杂度,由于数据中插入元素的平均时间复杂度为O(n),所以对于插入排序,每次插入操作都相当于在数组中插入一个数据,循环执行n次插入操作,所以平均时间复杂度为O(n^2)。

    以上就是python插入排序的性能问题,希望对大家有所帮助。更多Python学习指路:python基础教程

    专题推荐:python排序
    品易云
    上一篇:python插入排序的优化 下一篇:python希尔排序的用法

    相关文章推荐

    • Python排序傻傻分不清?一文看透sorted与sort用法• PyThon排序算法的用法及示例• python排序算法-冒泡排序优化• Python排序方法-列表排序sorted的用法:正数在前负数在后,整数从小到大,负数从大到小

    全部评论我要评论

    © 2021 Python学习网 苏ICP备2021003149号-1

  • 取消发布评论
  • 

    Python学习网