PHP实现常见排序算法
每年总是要隔三差五的看数据结构，每次总是觉得自己很多东西没有学好，唉。今天贴刚使用php实现4的排序算法，另外堆排序和归并排序没有写。其他数据结构知识使用php的实现参考我以前写的文章：
http://blog.csdn.net/heiyeshuwu/archive/2006/06/10/787426.aspx
插入排序、选择排序、，冒泡排序，时间复杂度貌似都是 O(N2)，所以实际意义不大，在实际测试中，我对3000个数组元素进行，这三种排序算法都需要花费80秒左右，而快速排序只需要8秒，差距确是比较大，有兴趣的可以自己测试一下。
<?
//插入排序（一维数组）
functioninsert_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--;
}
}
return$arr;
}
//选择排序（一维数组）
functionselect_sort($arr){
$count=count($arr);
for($i=0;$i<$count;$i++){
$k=$i;
for($j=$i+1;$j<$count;$j++){
if($arr[$k]>$arr[$j])
$k=$j;
if($k!=$i){
$tmp=$arr[$i];
$arr[$i]=$arr[$k];
$arr[$k]=$tmp;
}
}
}
return$arr;
}
//冒泡排序（一维数组）
functionbubble_sort($array){
$count=count($array);
if($count<=0)returnfalse;
for($i=0;$i<$count;$i++){
for($j=$count-1;$j>$i;$j--){
if($array[$j]<$array[$j-1]){
$tmp=$array[$j];
$array[$j]=$array[$j-1];
$array[$j-1]=$tmp;
}
}
}
return$array;
}
//快速排序（一维数组）
functionquick_sort($array){
if(count($array)<=1)return$array;
$key=$array[0];
$left_arr=array();
$right_arr=array();
for($i=1;$i<count($array);$i++){
if($array[$i]<=$key)
$left_arr[]=$array[$i];
else
$right_arr[]=$array[$i];
}
$left_arr=quick_sort($left_arr);
$right_arr=quick_sort($right_arr);
returnarray_merge($left_arr,array($key),$right_arr);
}
?>
页:
[1]