数据结构和算法

当前位置:首页>数据结构和算法

排序算法-插入排序

时间:2019-04-17   访问量:9

<?php

/**

 * 插入排序

 * -------------------------------------------------------------

 * 思路分析:每步将一个待排序的纪录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。

 * -------------------------------------------------------------

 *

 * 算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。

 * 插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,

 * 但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素)。

 * 在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中。

 *

 */

// +--------------------------------------------------------------------------

// | 解题方式    | 这儿,可能有用的解决方案

// +--------------------------------------------------------------------------

/**

 * InsertSort

 *

 * @param array $container

 * @return array

 */

function InsertSort(array $container)

{

    $count = count($container);

    for ($i = 1; $i < $count; $i++){

        $temp = $container[$i];

        $j    = $i - 1;

        // Init

        while($j >= 0 && $container[$j] > $temp){

            $container[$j+1] = $container[$j];

            $j--;

        }

        if($i != $j+1) 

            $container[$j+1] = $temp;

    }

    return $container;

}

// +--------------------------------------------------------------------------

// | 方案测试    | php `this.php` || PHPStorm -> 右键 -> Run `this.php`

// +--------------------------------------------------------------------------

var_dump(InsertSort([3, 12, 42, 1, 24, 5, 346, 7]));

/*

array (size=8)

  0 => int 1

  1 => int 3

  2 => int 5

  3 => int 7

  4 => int 12

  5 => int 24

  6 => int 42

  7 => int 346

 */


上一篇:排序算法-冒泡排序

下一篇:排序算法-快速排序

在线咨询

点击这里给我发消息 售前咨询专员

点击这里给我发消息 售后服务专员

在线咨询

免费通话

24小时免费咨询

请输入您的联系电话,座机请加区号

免费通话

微信扫一扫

微信联系
返回顶部