[アルゴリズム] 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 . "<br />");//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 . "<br />");//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 . "<br />");//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 . "<br />");//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 . "<br />");

時間のかかる比較

挿入ソートに時間がかかる: 1.2335460186005

バブルソート時間がかかる 時間: 2.6180219650269

並べ替え時間の選択: 1.4159741401672

並べ替え時間のマージ: 0.17212891578674

速い並べ替え時間: 0.16736888885498