【算法】PHP实现经典算法(上)
前言 下面的是通过PHP实现经典算法,并计算了耗时,可以通过耗时对比这几种算法的复杂度。
- 插入排序
- 冒泡排序
- 选择排序
- 并归排序
- 快速排序
$arr = [];
for ($i = 0;
$i < 5000;
$i++) {
$arr[] = rand(1, 10000);
}//1 插入排序function insertionSort($arr)
{for ($i = 1;
$i < count($arr);
$i++) {
$tmp = $arr[$i];
//设置监视哨
$key = $i - 1;
//设置开始查找的位置
while ($key >= 0 && $tmp < $arr[$key]) { // 监视哨的值比查找的值小 并且 没有到此次查询的第一个
$arr[$key + 1] = $arr[$key];
//数组的值进行后移
$key--;
//要查找的位置后移
}
if (($key + 1) != $i) //放置监视哨
$arr[$key + 1] = $tmp;
}
return $arr;
}$insertion_start_time = microtime(true);
$insertion_sort = insertionSort($arr);
$insertion_end_time = microtime(true);
$insertion_need_time = $insertion_end_time - $insertion_start_time;
print_r("插入排序耗时:" . $insertion_need_time . "
");
//2 冒泡排序function bubbleSort($arr)
{for ($i = 0;
$i < count($arr);
$i++) {
for ($j = 0;
$j < $i + 1;
$j++) {
if ($arr[$j] < $arr[$j - 1]) {
$temp = $arr[$j - 1];
$arr[$j - 1] = $arr[$j];
$arr[$j] = $temp;
}
}
}
return $arr;
}$bubble_start_time = microtime(true);
$bubble_sort = bubbleSort($arr);
$bubble_end_time = microtime(true);
$bubble_need_time = $bubble_end_time - $bubble_start_time;
print_r("冒泡排序耗时:" . $bubble_need_time . "
");
//3 选择排序function selectionSort($arr)
{
$count = count($arr);
for ($i = 0;
$i < $count - 1;
$i++) {
//找到最小的值
$min = $i;
for ($j = $i + 1;
$j < $count;
$j++) {
//由小到大排列
if ($arr[$min] > $arr[$j]) {
//表明当前最小的还比当前的元素大
$min = $j;
//赋值新的最小的
}
}
/*swap$array[$i]and$array[$min]即将当前内循环的最小元素放在$i位置上*/
if ($min != $i) {
$temp = $arr[$min];
$arr[$min] = $arr[$i];
$arr[$i] = $temp;
}
}
return $arr;
}$selection_start_time = microtime(true);
$selection_sort = selectionSort($arr);
$selection_end_time = microtime(true);
$selection_need_time = $selection_end_time - $selection_start_time;
print_r("选择排序耗时:" . $selection_need_time . "
");
//4 并归排序//merge函数将指定的两个有序数组(arr1arr2,)合并并且排序
//我们可以找到第三个数组,然后依次从两个数组的开始取数据哪个数据小就先取哪个的,然后删除掉刚刚取过///的数据
function al_merge($arrA, $arrB)
{
$arrC = array();
while (count($arrA) && count($arrB)) {
//这里不断的判断哪个值小,就将小的值给到arrC,但是到最后肯定要剩下几个值,
//不是剩下arrA里面的就是剩下arrB里面的而且这几个有序的值,肯定比arrC里面所有的值都大所以使用
$arrC[] = $arrA['0'] < $arrB['0'] ? array_shift($arrA) : array_shift($arrB);
}
return array_merge($arrC, $arrA, $arrB);
}//归并排序主程序
function al_merge_sort($arr)
{
$len = count($arr);
if ($len <= 1)
return $arr;
//递归结束条件,到达这步的时候,数组就只剩下一个元素了,也就是分离了数组
$mid = intval($len / 2);
//取数组中间
$left_arr = array_slice($arr, 0, $mid);
//拆分数组0-mid这部分给左边left_arr
$right_arr = array_slice($arr, $mid);
//拆分数组mid-末尾这部分给右边right_arr
$left_arr = al_merge_sort($left_arr);
//左边拆分完后开始递归合并往上走
$right_arr = al_merge_sort($right_arr);
//右边拆分完毕开始递归往上走
$arr = al_merge($left_arr, $right_arr);
//合并两个数组,继续递归
return $arr;
}$merge_start_time = microtime(true);
$merge_sort = al_merge_sort($arr);
$merge_end_time = microtime(true);
$merge_need_time = $merge_end_time - $merge_start_time;
print_r("并归排序耗时:" . $merge_need_time . "
");
//5 快速排序function quickSort(&$arr){
if(count($arr)>1){
$k=$arr[0];
$x=array();
$y=array();
$_size=count($arr);
for($i=1;
$i<$_size;
$i++){
if($arr[$i]<=$k){
$x[]=$arr[$i];
}elseif($arr[$i]>$k){
$y[]=$arr[$i];
}
}
$x=quickSort($x);
$y=quickSort($y);
return array_merge($x,array($k),$y);
}else{
return$arr;
}
}$quick_start_time = microtime(true);
$quick_sort = al_merge_sort($arr);
$quick_end_time = microtime(true);
$quick_need_time = $quick_end_time - $quick_start_time;
print_r("快速排序耗时:" . $quick_need_time . "
");
耗时对比
【【算法】PHP实现经典算法(上)】插入排序耗时:1.2335460186005参考资料
冒泡排序耗时:2.6180219650269
选择排序耗时:1.4159741401672
并归排序耗时:0.17212891578674
快速排序耗时:0.16736888885498
- 算法导论
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗()
- 2019-02-13——今天谈梦想()
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境,人生还很长