PHP 实现插入排序

DoINsiSt 发布于2019-07-01 11:16 / 923人阅读

摘要：插入排序插入排序英语是一种简单直观的排序算法。插入排序在实现上，通常采用排序即只需用到的额外空间的排序，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。一般来说，插入排序都采用在数组上实现。

导语

关于排序的算法，就此告一段落。冒泡排序、快速排序、选择排序、加上本篇的插入排序，这四种算法都是相对简单，容易理解的。更复杂的算法，就不献丑了，以免误人子弟。

插入排序

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到 O(1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序

取出下一个元素，在已经排序的元素序列中从后向前扫描

如果该元素（已排序）大于新元素，将该元素移到下一位置

重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

将新元素插入到该位置后

重复步骤2~5

来自维基百科的介绍。重点在于步骤 2~5。

动图演示

实例

= 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排序算法系列：插入排序。

GPU云服务器云服务器用php实现插入排序实现插入排序 php 实现直接插入 php实现插入语句

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

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

PHP排序算法之插入排序

摘要：直接插入排序是由两层嵌套循环组成的。插入排序的基本方法是每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。算法实现直接插入排序记录后移插入到正确的位置运行结果算法引入：在这里我们依然使用《大话数据结构》里面的一个例子：扑克牌是我们几乎每个人都玩过的游戏。平时我们开始的时候一般都是一个人发牌，其他人都是一边摸牌，一边理牌，假如你摸上...

rose 2019-07-01 10:30 评论0 收藏0
PHP面试：说下什么是堆和堆排序？

摘要：一个常见的例子就是优先队列，还有排序算法之一的堆排序。另外我们还将学习堆排序，并将使用实现堆。堆排序在堆排序中，我们需要用给定的值构建一个一个堆。伪代码如下从上面的伪代码可以看到，堆排序的第一步就是构建一个堆。堆是什么？堆是基于树抽象数据类型的一种特殊的数据结构，用于许多算法和数据结构中。一个常见的例子就是优先队列，还有排序算法之一的堆排序。这篇文章我们将讨论堆的属性、不同类型的堆...

twohappy 2019-07-01 10:32 评论0 收藏0
PHP算法之四大基础算法

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

isLishude 2019-07-01 12:31 评论0 收藏0
php实现排序（选择，冒泡，快速）

摘要：它的基本思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。选择排序选择排序主要是将假设数组中的第一个是最小的，循环与数组中的第一个进行比较如果比其还小则记录下标进行数值交换效率相对冒泡来说比较高 function s...

biaoxiaoduan 2019-06-27 15:39 评论0 收藏0
php插入排序,快速排序,归并排序,堆排序

摘要：的陣列視為基本型別，所以必須用傳參考才能修改原陣列插入排序快速排序归并排序堆排序获取个数处理一半的数据 function bubble_sort(&$arr) {//php的陣列視為基本型別，所以必須用傳參考才能修改原陣列 for ($i = 0; $i < count($arr) - 1; $i++) for ($j = 0; $j < count($arr)...

JerryZou 2019-07-01 10:12 评论0 收藏0