PHP插入排序的实现

插入排序基本思路:将数组分为两个区(已排序区和未排序区),假定数组的第一个元素处于已排序区, 第一个元素之后的所有元素都处于未排序部分。排序时用到双层循环,外层循环用于从未排序部分中取出待排序元素,并逐步缩小未排序部分,内层循环用于从已排序部分寻找插入位置(即不断地从已排序部分寻找比待排序元素大的元素), 然后将较大的已排序区的元素后移,后移的最终结果是已排序区元素的最后一个元素占据待排序元素原来的位置,而已排序区中间空出一个位置),最后将待排序元素插入元素后移之后留下的空位。

//插入排序
function insert_sort($arr) {
//获取数组单元个数
$count = count($arr);
//外层循环用于从未排序区域中取出待排序元素
for ($i=1; $i < $count; $i++) {
//获取当前需要插入已排序区域的元素值
$temp = $arr[$i];
//内层循环用于从已排序区域寻找待排序元素的插入位置
for ($j=$i-1; $j >= 0; $j--) {
//如果$arr[$i]比已排序区域的$arr[$j]小,就后移$arr[$j]
if ($temp < $arr[$j]) {
$arr[$j+1] = $arr[$j];
$arr[$j] = $temp;
} else {
//如果$arr[$i]不小于$arr[$j],则对已排序区无需再排序
break;
}
}
}
return $arr;
}

$arr = array(6, 19, 26, 62, 88, 99, 18, 16, 1);
var_dump(insert_sort($arr));
测试结果:
赞(0)
声明:本网站发布的内容(图片、视频和文字)以原创、转载和分享网络内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-62778877-8306;邮箱:fanjiao@west.cn。本站原创内容未经允许不得转载,或转载时需注明出处:西部数码知识库 » PHP插入排序的实现

登录

找回密码

注册