10大经典排序算法之插入排序(PHP版)

发布时间:2020/11/20 作者:天马行空 阅读(156)

插入排序,一般也被称为直接插入排序,插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解。对于少量元素的排序,它是一个有效的算法 。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中。


算法步骤
1、将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
2、从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置,如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。


动图演示

insertionSort.gif


代码实现:

public function insertSort($arr)
{
    $length = count($arr);
    for ($i = 0; $i < $length - 1; $i ++) {
        $tmp = $arr[$i + 1]; // 要插入的数据
        $j = $i; // 取第几个
        while ($j >= 0 && $tmp < $arr[$j]) { // 被插入的数据比前面的数据小(大),前面的数据就往后面移,前面的数据已经是有序,所以比较一个就知道是否还需要和前面的进行比较
            $arr[$j + 1] = $arr[$j];
            $j --;
        }
        
        $arr[$j + 1] = $tmp; // 插入到移出来的空位置
    }
    return $arr;
}



关键字php 算法