欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

PHP之八大排序算法-插入排序(-)直接插入排序

程序员文章站 2024-01-31 15:43:34
...
PHP之八大排序算法--插入排序(-)直接插入排序

直接插入排序:

插入排序是最简单的排序算法之一,对于有N个元素的序列,插入排序由N-1趟排序组成。它的工作原理是通过构建有序序列,对于未排序的数据,在已经排序序列中从后向前扫描,找到相应位置插入。

插入排序算法步骤:

  1. 将第一个待排序的序列的第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。

  2. 从头到尾一次扫描未排序的序列,将扫描到的每个元素插入有序序列的适当位置(在这里需要注意一个问题,如果在有序序列中有一个和待插入的元素相等,则将待插入的元素查到此元素的后面,这样方式的插入排序是稳定的。如果插入到此元素的前面,那么此种方式的插入排序是不稳定的

    对于上面的步骤可以将插入排序的算法总结为:

    在第L趟排序中,将位置L上的元素向左移动到它在前L+1个元素中的正确的位置上,这里的前L个元素是有序的

PHP之八大排序算法-插入排序(-)直接插入排序

PHP之八大排序算法-插入排序(-)直接插入排序

插入排序算法分析:

由于嵌套循环的每一个都花费N次迭代,因此插入排序的时间复杂度为O(N^2);

以上讲解的插入排序是插入排序算法中的直接插入排序,在有序序列中查找插入位置的时候是逐个查找,故称直接插入排序

欢迎继续关注我们后续的排序算法.个人项目有:配资公司(www.ya-jing.cn)

PHP之八大排序算法-插入排序(-)直接插入排序

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。

相关文章

相关视频