PHP实现经典算法下php7php环境搭建php从入门到精通

前言

前几天，我们通过PHP实现了不同的排序算法，并比较算法对应的耗时。
【算法】PHP实现经典算法(上)

下面我们来实现下列算法

• 堆排序
• 鸡尾酒排序
• 直接选择排序
• 计数排序

CODE

$arr = [];

for ($i = 0; $i < 5000; $i++) {
    $arr[] = rand(1, 50000);
}



// 5 堆排序/**
 * 交换两个数的位置
 * @param $a
 * @param $b
 */functionswap(&$a,&$b){$temp = $b;
    $b = $a;
    $a = $temp;
}

/**
 * 左子树
 * @param $i
 * @return mixed
 */functionlchild($i){return$i*2+1;}

/**
 * 右子树
 * @param $i
 * @return mixed
 */functionrchild($i){return$i*2+2;}

/**
 * 整理节点
 * @param $array 待调整的堆数组
 * @param $i 待调整的数组元素的位置
 * @param $heapsize  数组的长度
 */functionbuild_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 数组的长度
 */functionsortHeap(&$array,$heapsize){while($heapsize){ //长度逐步递减0//首先交换第一个元素和最后一个元素的位置
        swap($array[0],$array[$heapsize-1]);
        $heapsize = $heapsize -1;
        build_heap($array,0,$heapsize); //整理数组的第一个的元素的位置,长度为逐步递减的数组长度
    }
}

/**
 * 创建堆
 * @param $array
 * @param $heapsize
 */functioncreateHeap(&$array,$heapsize){$i = ceil($heapsize/2)-1; //找到中间的位置for( ; $i>=0 ;$i-- ){  //从中间往前面整理堆
        build_heap($array,$i,$heapsize);
    }
}

/**
 * 堆排序主函数
 */functionHeapsort($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 . "
");


// 6 鸡尾酒排序法/**
 * 鸡尾酒排序
 * @param $arr
 * @return mixed
 */functionCocktailsort($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 . "
");


// 7  希尔排序/**
 * 希尔排序
 * @param $arr
 */functionShellsort($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 . "
");

// 8  直接选择排序/**
 * 直接选择排序
 * @param $arr
 * @return mixed
 */functionStraightselectsort($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 . "
");


// 9  计数排序/**
 * 计数排序
 * @param $arr
 * @return mixed
 */functionCountsort($arr){$max = $arr[0];
    $min = $arr[0];

    foreach($arras$key => $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 . "
");

耗时对比

堆排序耗时:0.086709976196289
鸡尾酒排序耗时:4.6467659473419
希尔排序耗时:4.4215688705444
直接选择排序耗时:4.529422044754
计数排序耗时:4.2601070404053

参考资料

• 算法导论

').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('

').text(i)); }; $numbering.fadeIn(1700); }); });

以上就介绍了PHP实现经典算法下，包括了php方面的内容，希望对PHP教程有兴趣的朋友有所帮助。