博客列表 >php实现排序之插入排序算法

php实现排序之插入排序算法

无意苦争春的博客
无意苦争春的博客原创
2017年08月17日 17:44:00755浏览

插入排序

      插入排序(Insertion Sorting)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有序表。150249hc4du0tsuhyyy48q.png.thumb.jpg

/**
* 插入排序
*
* @param $arr, array 待排序的数组
*
* @return array, 排序好的数组
*/
function insert_sort($arr) {
    //区分 哪部分是已经排序好的
    //哪部分是没有排序的

    //找到其中一个需要排序的元素
    //这个元素 就是从第二个元素开始,到最后一个元素都是这个需要排序的元素
    //利用循环就可以标志出来
    //i循环控制 每次需要插入的元素,一旦需要插入的元素控制好了,
    //间接已经将数组分成了2部分,下标小于当前的(左边的),是排序好的序列
    for($i=1, $len=count($arr); $i<$len; $i++) {
        //获得当前需要比较的元素值。
        $tmp = $arr[$i];
        //内层循环控制 比较 并 插入
        for($j=$i-1;$j>=0;$j--) {
//            $arr[$i];//需要插入的元素
//            $arr[$j];//需要比较的元素
            if($tmp < $arr[$j]) {
                //发现插入的元素要小,交换位置
                //将后边的元素与前面的元素互换
                $arr[$j+1] = $arr[$j];
                //将前面的数设置为 当前需要交换的数
                $arr[$j] = $tmp;
            } else {
                //如果碰到不需要移动的元素
                //由于是已经排序好是数组,则前面的就不需要再次比较了。
                break;
            }

        }


    }

    //将这个元素 插入到已经排序好的序列内。

    //返回
    return $arr;

}


$arr = array(3, 1, 5, 0, 7, 2);

print_r(insert_sort($arr));


声明:本文内容转载自脚本之家,由网友自发贡献,版权归原作者所有,如您发现涉嫌抄袭侵权,请联系admin@php.cn 核实处理。
全部评论
文明上网理性发言,请遵守新闻评论服务协议