PHP算法排序之快速排序、冒泡排序、选择排序、插入排序性能对比

<?php
//冒泡排序
//原理:从倒数第一个数开始,相邻的两个数比较,后面比前面的小,则交换位置,一直到比较第一个数之后则最小的会排在第一位,以此类推
function bubble_sort($arr){
$count = count($arr);
for($i=0; $i<$count; $i++){
for($j=$count-1; $j>$i; $j--){
if($arr[$j]<$arr[$j-1]){
$tmp = $arr[$j];
$arr[$j] = $arr[$j-1];
$arr[$j-1] = $tmp;
}
}
}
return $arr;
}
//快速排序
function quick_sort($arr){
$count = count($arr);
if($count<=1)return $arr;
$key = $arr[0];
$l = array();
$r = array();
for($i=1;$i<$count;$i++){
if($arr[$i]<=$key){
$l[] = $arr[$i];
}else{
$r[] = $arr[$i];
}
}
$l = quick_sort($l);
$r = quick_sort($r);
return array_merge($l,array($key),$r); }
//选择排序
//原理:利用数组的key,假设数组的第一个key[0]为最小的,和后面的数比较,如果key[0]大于后面的数则存起来key,比较完之后(比较到数组的最后一个),如果key[0]!=存起来的key,则交换他们的key. 以此类推, 然后再从第二个key[1]去和后面的比较
function select_sort($arr){
$count = count($arr);
for($i=0;$i<$count;$i++){
$k = $i;
for($j=$i+1;$j<$count;$j++){
if($arr[$j]<$arr[$k]){
$k = $j;
}
}
if($k != $i){
$tmp = $arr[$k];
$arr[$k] = $arr[$i];
$arr[$i] = $tmp;
}
}
return $arr;
}
//插入排序
//原理:假设一堆数字都排好序了,[6,7,8] 现在给你一个9让你插进去,这个时候9和8比大,就放到8后面就行了,[6,7,8,9],因为一堆数字排好序了, 前面的肯定都比8小, 所以就不用和前面的比较了.
function insert_sort($arr){
$count = count($arr);
for($i=1; $i<$count; $i++){
$tmp = $arr[$i];
$j = $i-1;
while($arr[$j]>$tmp){
$arr[$j+1] = $arr[$j];
$arr[$j] = $tmp;
$j--;
if($j<0){
break;
}
}
}
return $arr;
}
//打印结果
function display($function,$a){
$t1 = microtime(true);
$arr = $function($a);
$t2 = microtime(true);
// print_r($arr);
return $t2-$t1;
}
//随机产生1600长度数组;
$a = array_rand(range(1,2000),1600);
//打乱数组
shuffle($a);
echo "<pre>"; echo '冒泡排序 ',display('bubble_sort',$a),'</br>'; echo '快速排序 ',display('quick_sort',$a),'</br>'; echo '选择排序 ',display('select_sort',$a),'</br>'; echo '插入排序 ',display('insert_sort',$a),'</br>';
上一篇:Unity中巧用协程和游戏对象的生命周期处理游戏重启的问题


下一篇:SSM学习(二)mybatis和spring的集成