算法 PHP实现经典算法(下)

2020-03-22 20:15:10

字体：大中小

来源：转载

供稿：网友

前言
前几天，我们通过PHP实现了不同的排序算法，并比较算法对应的耗时。
【算法】PHP实现经典算法(上)
下面我们来实现下列算法
堆排序鸡尾酒排序直接选择排序计数排序

CODE

$arr = [];for ($i = 0; $i < 5000; $i++) {    $arr[] = rand(1, 50000);}// 5 堆排序/** * 交换两个数的位置 * @param $a * @param $b */function swap(&$a,&$b){    $temp = $b;    $b = $a;    $a = $temp;}/** * 左子树 * @param $i * @return mixed */function lchild($i){ return $i*2+1;}/** * 右子树 * @param $i * @return mixed */function rchild($i){ return $i*2+2;}/** * 整理节点 * @param $array 待调整的堆数组 * @param $i 待调整的数组元素的位置 * @param $heapsize  数组的长度 */function build_heap(&$array,$i,$heapsize){    $left = lchild($i);    $right = rchild($i);    $max = $i;    //如果比左子树小并且在左右子树的右面,边界调整到左侧    if($i < $heapsize && $left < $heapsize  && $array[$left] > $array[$i] ){        $max = $left;    }    //如果比右子树小并且都小于要构建的数组长度,边界调整到右侧    if($i < $heapsize && $right < $heapsize && $array[$right] > $array[$max]){        $max = $right;    }    //如果经过两次调整后,要调整的数组不是最大值    if($i != $max && $i < $heapsize && $max < $heapsize){        //就交换对应的位置,并再次进行整理节点        swap($array[$i],$array[$max]);        build_heap($array,$max,$heapsize);    }}/** * 对堆进行排序 * @param $array 要排序的数组 * @param $heapsize 数组的长度 */function sortHeap(&$array,$heapsize){    while($heapsize){ //长度逐步递减0        //首先交换第一个元素和最后一个元素的位置        swap($array[0],$array[$heapsize-1]);        $heapsize = $heapsize -1;        build_heap($array,0,$heapsize); //整理数组的第一个的元素的位置,长度为逐步递减的数组长度    }}/** * 创建堆 * @param $array * @param $heapsize */function createHeap(&$array,$heapsize){    $i = ceil($heapsize/2)-1; //找到中间的位置    for( ; $i>=0 ;$i-- ){  //从中间往前面整理堆        build_heap($array,$i,$heapsize);    }}/** * 堆排序主函数 */function Heapsort($array){    $heapsize = count($array);    createHeap($array,$heapsize);    sortHeap($array,$heapsize);    return $array;}$heapsort_start_time = microtime(true);$heapsort_sort = Heapsort($arr);$heapsort_end_time = microtime(true);$heapsort_need_time = $heapsort_end_time - $heapsort_start_time;print_r('堆排序耗时:' . $heapsort_need_time . '<br />');// 6 鸡尾酒排序法/** * 鸡尾酒排序 * @param $arr * @return mixed */function Cocktailsort($arr) {    $arr_len  =count($arr);    for($i = 0 ; $i < ($arr_len/2) ; $i ++){        //将最小值排到队尾        for( $j = $i ; $j < ( $arr_len - $i - 1 ) ; $j ++ ){            if($arr[$j] < $arr[$j + 1] ){                swap($arr[$j],$arr[$j + 1]);            }        }        //将最大值排到队头        for($j = $arr_len - 1 - ($i + 1); $j > $i ; $j --){            if($arr[$j] > $arr[$j - 1]){                swap($arr[$j],$arr[$j - 1]);            }        }    }    return $arr;}$cocktailsort_start_time = microtime(true);$cocktailsort_sort = Cocktailsort($arr);$cocktailsortt_end_time = microtime(true);$cocktailsort_need_time = $cocktailsortt_end_time - $cocktailsort_start_time;print_r('鸡尾酒排序耗时:' . $cocktailsort_need_time . '<br />');// 7  希尔排序/** * 希尔排序 * @param $arr */function Shellsort($arr){    $n=count($arr); //数组长度    for($gap=floor($n/2);$gap>0;$gap=floor($gap/=2)) //    {        for($i=$gap;$i<$n;++$i) //根据增量循环        {            //以增量为步幅进行查看            for( $j=$i-$gap; $j>=0 && $arr[$j+$gap] < $arr[$j]; $j -= $gap)            {                swap($arr[$j],$arr[$j+$gap]);            }        }    }    return $arr;}$shellsort_start_time = microtime(true);$shellsort_sort = Cocktailsort($arr);$shellsort_end_time = microtime(true);$shellsort_need_time = $shellsort_end_time - $shellsort_start_time;print_r('希尔排序耗时:' . $shellsort_need_time . '<br />');// 8  直接选择排序/** * 直接选择排序 * @param $arr * @return mixed */function  Straightselectsort($arr){    $n = count($arr);    for($i = 0 ; $i < $n - 1;$i++){        $m = $i;        for($j = $i+1 ; $j < $n; $j++){            if($arr[$j] < $arr[$m] ){                $m = $j;            }            if($m != $j){                //进行交换                swap($arr[$m],$arr[$j]);            }        }    }    return $arr;}$straightselectsort_start_time = microtime(true);$straightselectsort_sort = Cocktailsort($arr);$straightselectsort_end_time = microtime(true);$straightselectsort_need_time = $straightselectsort_end_time - $straightselectsort_start_time;print_r('直接选择排序耗时:' . $straightselectsort_need_time . '<br />');// 9  计数排序/** * 计数排序 * @param $arr * @return mixed */function Countsort($arr){    $max = $arr[0];    $min = $arr[0];    foreach($arr as $key => $html' target='_blank'>value) {        if ($value > $max) {            $max = $value;        }        if ($value < $min) {            $min = $value;        }    }        //这里k的大小是要排序的数组中，元素大小的极值差+1        $c=[];        $k = $max - $min + 1;        for($i = 0; $i < count($arr) ; $i ++){            $c[$arr[$i] - $min ] +=1;        }        for($i=1;$i < count($c); ++$i){            $c[$i] = $c[$i] + $c[$i - 1];        }        for($i = count($arr);$i > 0 ; --$i){            $b[ -- $c[$arr[$i] - $min] ] = $arr[$i];        }    return $b;}$countsort_start_time = microtime(true);$countsort_sort = Cocktailsort($arr);$countsort_end_time = microtime(true);$countsort_need_time = $countsort_end_time - $countsort_start_time;print_r('计数排序耗时:' . $countsort_need_time . '<br />');