算法 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 />');