Home > Backend Development > PHP Tutorial > PHP之八大排序算法-插入排序(-)直接插入排序

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

WBOY
Release: 2016-06-13 12:17:13
Original
1005 people have browsed it

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

直接插入排序:

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

插入排序算法步骤:

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

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

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

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


插入排序算法分析:

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

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

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

Related labels:
php
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template