PHP排序算法系列之插入排序详解
发布时间：2021-04-01 20:18:02 所属栏目：编程 来源：网络整理
导读：插入排序 有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列如故有序，这个时辰就要用到一种新的排序要领——插入排序法,插入排序的根基操纵就是将一个数据插入到已经排好序的有序数据中，从而获得一个新的、个
插入排序有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列如故有序，这个时辰就要用到一种新的排序要领——插入排序法,插入排序的根基操纵就是将一个数据插入到已经排好序的有序数据中，从而获得一个新的、个数加一的有序数据，算法合用于少量数据的排序，时刻伟大度为O(n^2)。是不变的排序要领。插入算法把要排序的数组分成两部门：第一部门包括了这个数组的全部元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部门就只包括这一个元素（即待插入元素）。在第一部门排序完成后，再将这个最后元素插入到已排好序的第一部门中。 道理直接插入排序(Insertion Sort)的根基头脑是Ｔ媚课将一个待排序的记录，按其要害字巨细插入到前面已经排好序的子序列中的恰当位置，直到所有记录插入完成为止。 设数组为a[0…n-1]。 1.初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1 2.将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。 3.i++并一再第二步直到i==n-1。排序完成。 PHP代码实现 =0;$j--){ //若插入值较量小，则将后头的元素后移一位，并将值插入 if($tmp<$arr[$j]){ $arr[$j+1]=$arr[$j]; $arr[$j]=$tmp; }else{ break; } } } return $arr; }算法时刻伟大度计较 在最好的环境下（元素已经排好次序）：那么只必要轮回 n-1 次就可以了，时刻伟大度 O（n） 在最差的环境下（元素是逆序的）：要轮回调解次数： [ n * (n-1) ] / 2 ，时刻伟大度为 O（n ^ 2） 均匀时刻伟大度为：O（n ^ 2） 以上就是本文的所有内容，但愿对各人的进修有所辅佐，也但愿各人多多支持编程之家。 （编辑：湖南网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
