数据结构与算法(php版)排序之插入排序

yang-pig| 阅读:585 发表时间:2018-07-29 20:51:38 算法

何谓‘插入排序’? 其概念如是说:每次将一个待排序的记录,按其关键字大小插入到前面已经排序好的序列中,直到全部记录插入完成为止。

概念的东西总是有些抽象,也可称其为基本思想。上述插入排序的概念同样也可说是插入排序的基本思想。抽象的东西理解起来总是有些困难,因此这里需要的是将抽象的概念具体化。

我们不妨将其转换成整队问题:开始会有两队,其中一队是按从低到高的顺序排列的,将其命名为A队。另一队是无序的,将其命名为B队。如下图:

1-15120G33424320.png

现在把B队的第一个人(不妨称其为jack)放到A队中,并且保持A队依然是有序的,为了保持A队依然有序就需要在A队中找一个适当的位置给jack,这个位置前面的人要比jack矮,后面的人要比jack高。现在就可以让jack站到这个位置上面,此时A中依然有序。

2.png

然后再把B队的第二个人(称其为tom)放到A队,方式和jack相同,要保证A队依然有序。

4.png

依次类推直到B队的人全部站到A队当中。到此为止,两队合成了一队,而且这一队是有序的。

5.png

看到这对插入排序应该有一个比较清晰的认识了。但是这里还存在着一个疑问,排序问题是对一个队列进行排序,何来的两队呢。我们不妨再来转换一下,起初的时候A、B两队站在同一列,并且A队整体在B队前面,并且A队是一个人。对于一个人的队列肯定是有序的。

6.png

7.png

然后再向代码方面靠近一下,不妨将A、B两队映射成数组。有这样一个数组

8.png

其中 3 就表示 刚开始的A队 ,5、2…. 表示刚开始的B队。而5 就是 Jack, 2 就是Tom。

我当时学习插入排序的时候就是按照这个思路来理解的。到这里我对插入排序的思想基本上已经完全掌握了。

思想的东西转换成代码,不同的方式也会产生不同的‘派系’。好比《春秋经》读起来总是有些难懂,这时就有人出来为春秋作传,不同的人作出来的传也是不同的,有《左传》,有《公羊传》,有《谷梁传》 。 虽然有所不同,但是整体都是传承的《春秋》的思想 。

现在回到我们的插入排序上来,既然思想的东西都已经明了了,无非就是实现方式的差别。关键的地方还是在于A队,当在A队为B队的人查找适当位置的时候,查找的方式有很多种。 1、每次开始从头遍历查找位置 称其为 直接插入排序

实现步骤:

1. 将第一个待排序的序列的第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。

2. 从头到尾一次扫描未排序的序列,将扫描到的每个元素插入有序序列的适当位置(在这里需要注意一个问题,如果在有序序列中有一个和待插入的元素相等,则将待插入的元素查到此元素的后面,这样方式的插入排序是稳定的。如果插入到此元素的前面,那么此种方式的插入排序是不稳定的


<?php
/**
 * 插入排序
 * ------------------------------------------------------
 * 1. 将第一个待排序的序列的第一个元素看做一个有序序列,
 * 把第二个元素到最后一个元素当成是未排序序列。
 * 2. 从头到尾一次扫描未排序的序列,将扫描到的每个元素插入有序序列的适当位置(在这里需要注意一个问题,
 * 如果在有序序列中有一个和待插入的元素相等,则将待插入的元素查到此元素的后面,
 * 这样方式的插入排序是稳定的。如果插入到此元素的前面,那么此种方式的插入排序是不稳定的
 *
 */



/**
 * 第一种实现代码是从第一个元素开始向后遍历,
 * 找到相应的位置,然后进行元素移动和插入
 * @param array $arr
 *
 */
function InsertSort1(array &$arr) {
    for($i=1;$i<count($arr);$i++) {
        $p = $arr[$i];
        for ($j = 0; $j < $i; $j++) {
            if ($arr[$j] > $p) {
                break;
            }
        }
        for ($k = $i - 1; $k >= $j; $k--) {
            $arr[$k + 1] = $arr[$k];
        }
        $arr[$j] = $p;
    }
}

$arr1 = array(
    15,77,23,43,90,87,68,32,11,22,33,99,88,66,44,113,
    224,765,980,159,456,7,998,451,96,0,673,82,91,100
);

InsertSort1($arr1);
var_dump($arr1);

/**
 * 第二种实现代码是从当前待排序元素的前一个元素
 * (也就是有序序列的最后一个元素)开始向前遍历,
 * 找到相应的位置,然后进行元素移动和插入
 * @param array $arr
 */
function InsertSort2(array &$arr) {
    for($i=1;$i<count($arr);$i++){
        $p = $arr[$i];
        for($j=$i-1;$j>=0;$j--){
            if($arr[$j]>$p){
                $arr2[$j+1] = $arr[$j];
            }else{
                break;
            }
        }
        $arr[$j+1] = $p;
    }
}

$arr2= array(
    15,77,23,43,90,87,68,32,11,22,33,99,88,66,44,113,
    224,765,980,159,456,7,998,451,96,0,673,82,91,100
);

InsertSort1($arr2);
var_dump($arr2);
2、用二分法查找位置 称其为 二分插入排序/折半插入排序

待续。。。。。。。。。。。。。。。。。。