前言

前几天，我们通过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 => $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 />");

耗时对比

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

参考资料

• 算法导论