PHP – 插入排序

一、概述

1、基本思想

对于给定的一组记录,初始时假设第一个记录自成一个有序序列,其余的记录为无须序列。

接着从第二个记录开始,按照记录的大小依次将当前处理的记录插入到其之前的有序序列中,直到最后一个记录插入到有序序列中为止。
 
2、处理过程

假设有一个数组[1, 17, 27, 16, 15], 目前待排序元素为16,它是第四个元素(下标为3),然后和它前面的元素挨个进行比较:

16 和 27 (下标为2) 进行对比,16 比 27 小,所以元素 27 占据原来 16 的位置(27 的下标从 2 变成 3),将下标 2 的位置空出来,16 占据这个位置。

16 继续和 17 比较,16 比 17 小,下标交换。

16 继续和 1 比较,16 >= 1,所以不交换下标,16 这个元素已经在有序序列中找到了自己的位置。

继续为元素 15 找合适的位置。

  

二、PHP代码实现

<?php
declare(strict_types = 1);

class TestCase
{
    /**
     * 插入排序
     *
     * @param array $array
     * @return array
     */
    public static function sortArray(array $array) : array
    {
        $arrayLen = count($array);
        for ($i = 1; $i < $arrayLen; $i++) {
            $tmp = $array[$i];
            for ($k = $i - 1; $k >= 0; $k--) {
                if ($tmp < $array[$k]) {
                    $array[$k + 1] = $array[$k];
                    $array[$k] = $tmp;
                } else {
                    break;
                }
            }
        }
        return $array;
    }
}


// 需要排序数组
$arr = [20, 19, 15, 36, 22, 3, 77, 95, 64, 15, 24, 36];
// 执行排序
$arr = TestCase::sortArray($arr);
// 输出结果
foreach ($arr as $v) {
    echo $v . ' ';
}
// 结果
3 15 15 19 20 22 24 36 36 64 77 95