PHP排序算法之插入排序

rose 发布于2019-07-01 10:30 / 1821人阅读

摘要：直接插入排序是由两层嵌套循环组成的。插入排序的基本方法是每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。算法实现直接插入排序记录后移插入到正确的位置运行结果

算法引入：

在这里我们依然使用《大话数据结构》里面的一个例子：

扑克牌是我们几乎每个人都玩过的游戏。平时我们开始的时候一般都是一个人发牌，其他人都是一边摸牌，一边理牌，假如你摸上的第一张牌是 5，第二张牌是 3，自然而然的我们把 3 插到 5 的前面；第三张牌是 4，查到 3 和 5 的中间；第四张牌是 6，放到 5 的后面；第五张牌是 2，插到 3 的前面；……。最后当我们摸完所有的牌时，手上的牌都是从小到大（点数）排好序的。

我们来看这个顺序：

5 3 // 将 3 插入只有一个元素 5 的有序表中
3 5 4 // 将 4 插入有两个元素 3 5 的有序表中
3 4 5 6 // 将 6 插入有两个元素 3 4 5 的有序表中
3 4 5 6 2 // 将 2 插入有两个元素 3 4 5 6 的有序表中
2 3 4 5 6

直接插入排序的基本思想是：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

第一趟比较前两个数，然后把第二个数按大小插入到有序表中；第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。

直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。

插入排序的基本方法是：每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。

算法实现：
// 直接插入排序
function swap(&$arr,$a,$b)
{

$temp    = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $temp;

}

function insertSort(&$arr)
{

$count = count($arr);
for ($i=1; $i < $count; $i++) { 
    $temp = $arr[$i];
    for ($j=$i-1; $j >= 0 && $arr[$j] > $temp;$j--) { 
         $arr[$j + 1] = $arr[$j];    //记录后移
    }
    $arr[$j + 1] = $temp;   //插入到正确的位置
}

}
$arr = array(9,1,5,8,3,7,4,6,2);
insertSort($arr);
var_dump($arr);

运行结果：
array(9) {
[0]=>
int(1)
[1]=>
int(2)
[2]=>
int(3)
[3]=>
int(4)
[4]=>
int(5)
[5]=>
int(6)
[6]=>
int(7)
[7]=>
int(8)
[8]=>
int(9)
}

GPU云服务器云服务器插入排序算法 java插入排序算法用php实现插入排序插入排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/29225.html

PHP算法之四大基础算法

摘要：而在证明算法是正确的基础上，第二步就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。 showImg(https://segmentfault.com/img/remote/1460000016451712?w=800&h=341); 前言虽然工作中，你觉得自己并没有涉及到算法这方面的东西，但是算法是程序的...

isLishude 2019-07-01 12:31 评论0 收藏0
PHP面试之四：逻辑与算法

摘要：数据结构常见数据结构数组是最简单而且应用最广泛的数据结构特征使用连续内存空间来存储存放相同类型或着衍生类型的元素数组比较特别，可以存放八种数据类型通过下标来访问集合特征保存不重复的元素字典特征就是关联数组，以形式存储栈，与队列相似特征存储数数据结构常见数据结构 Array 数组是最简单而且应用最广泛的数据结构特征： 1、使用连续内存空间来存储 2、存放相同类型或着衍生类型...

smartlion 2019-06-28 14:11 评论0 收藏0
PHP 算法02之插入排序

摘要：最后看第三位和第四位，发现左边小于右边，无需交换，最终是，，，。总结一下就是从左到右依次选中一个数和左边比较，这个数小于左边就交换，交换完在和左边比较，直到交换到比左边大了之后，换下一个数，最后数字依次处理后，数据即从小到大排序。描述举例4个数: 7,4,3,8 从左往右两两比较,即 7和4比较，发现7大于4，那么交换，数列变成 4,7,3,8 。然后我们再看第2位和第三位，发...

awesome23 2019-07-01 10:20 评论0 收藏0
PHP基础算法之插入排序法

摘要：插入排序法获得当前需要比较的元素值。将这个元素插入到已经排序好的序列内。

stormzhang 2019-06-27 15:57 评论0 收藏0