内容简介:关于排序的算法,就此告一段落。冒泡排序、来自维基百科的介绍。重点在于步骤 2~5。
导语
关于 排序 的算法,就此告一段落。冒泡排序、 快速排序 、选择排序、加上本篇的插入排序,这四种算法都是相对简单,容易理解的。更复杂的算法,就不献丑了,以免误人子弟。
插入排序
插入排序(英语:Insertion Sort)是一种简单直观的 排序算法 。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。 插入排序 在实现上,通常采用in-place排序(即只需用到 O(1) 的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
一般来说, 插入排序 都采用in-place在数组上实现。具体算法描述如下:
- 从第一个元素开始,该元素可以认为已经被排序
- 取出下一个元素,在已经排序的元素序列中从后向前扫描
- 如果该元素(已排序)大于新元素,将该元素移到下一位置
- 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
来自维基百科的介绍。重点在于步骤 2~5。
动图演示
实例
<?php $arr = [33, 24, 8, 21, 2, 23, 3, 32, 16]; function insertSort($arr) { $count = count($arr); if ($count < 2) { return $arr; } for ($i = 1; $i < $count; $i++) { // 当前值 $temp = $arr[$i]; for ($k = $i - 1; $k >= 0; $k--) { // 条件成立,比较值后挪一位,将当前值替换成比较值 // 倒序 $temp > $arr[$k] if ($temp < $arr[$k]) { $arr[$k + 1] = $arr[$k]; $arr[$k] = $temp; } } } return $arr; } print_r(insertSort($arr)); // Array ( [0] => 2 [1] => 3 [2] => 8 [3] => 16 [4] => 21 [5] => 23 [6] => 24 [7] => 32 [8] => 33 )
参考资料: 插入排序 、 PHP排序算法系列:插入排序 。
以上所述就是小编给大家介绍的《PHP 实现插入排序》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Impractical Python Projects
Lee Vaughan / No Starch Press / 2018-11 / USD 29.95
Impractical Python Projects picks up where the complete beginner books leave off, expanding on existing concepts and introducing new tools that you’ll use every day. And to keep things interesting, ea......一起来看看 《Impractical Python Projects》 这本书的介绍吧!