如何实现插入排序

描述：插入排序的基本思想就是对于给定的一组记录，初始时假设第一个记录自成一个有序序列，其余的记录为无序序列。
接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列中为止。
比如：
数组 array(2,5,1,3)
第一步插入 2 以后： [2] 5 1 3
第二步插入 5 以后： [2 5] 1 3
第三步插入 1 以后： [1 2 5] 3
…]

header("Content-type:text/html;charset=utf-8");
function insertSort($arr){
    //已经间接将数组分成2部分，下标小于当前的（左边的）是排序好的序列
    $len = count($arr);
    for($i = 1; $i < $len; $i++){ 
        //获取当前需要比较的元素值
        $tmp = $arr[$i];
        //内层循环，控制比较并插入
        for($j=$i -1;$j>=0;$j--){
            if($tmp < $arr[$j]){
                $arr[$j+1] = $arr[$j];
                $arr[$j] = $tmp;
            }else{
                break;
            }
        }
    }
    return $arr;
}

// 可以对传统的插入排序算法进行改进，在查找插入位置时使用二分查找的方式。
function insertSort2($arr) {
    for ($i = 1; $i < count($arr); $i++) {
        $key = $arr[$i];
        $left = 0;
        $right = $i - 1;
        while ($left <= $right) {
            // ceil() - 进一法取整
            // round() - 对浮点数进行四舍五入
            // floor() -返回不大于 value 的最接近的整数
            $middle = floor(($left + $right) / 2);  
            if ($key < $arr[$middle]) {
                $right = $middle - 1;
            } else {
                $left = $middle + 1;
            }
        } 
        for ($j=$i-1; $j>= $left; $j--) {
            $arr[$j + 1] = $arr[$j];
        }
        $arr[$left] = $key;
    }
    return $arr;
}

$arr = array(34, 55, 23, 34, 67);
echo "排序前: ";
foreach ($arr as $k => $val)
{
    echo $val.' ';
}
echo "<br>排序后 : ";
$arr = insertSort($arr);
foreach ($arr as $k => $val)
{
    echo $val.' ';
}

猜你喜欢