用 PHP 实现经典排序算法

前言

最近在学习数据结构及算法，打算用PHP实现一些经典的排序算法，来巩固一下所学的内容，如果有不对的地方，欢迎大佬指教。
因为时间的关系，这里只展示代码，关于算法原理或者思路，后续可能会写专门的博客出来，感谢大家支持。

冒泡排序

/**
 * 给指定数组按照从小到大排序
 *
 * @param  array  $arr [待排序的数组]
 * @return [type]      [返回为数组]
 */
public function sort($arr=array(1,2,3,6,4,3)){
    //对整个数组进行遍历
    for($i=0;$i<count($arr)-1;$i++){
        //每一轮的冒泡处理
        for($j=0;$j<count($arr)-1-$i;$j++){
            //如果当前循环元素比他的后一位大
            if($arr[$j]>$arr[$j+1]){
                //暂存当前循环的值
                $tmp=$arr[$j];
                //交换两个元素的位置
                $arr[$j]=$arr[$j+1];
                $arr[$j+1]=$tmp;
            }
        }
    }
    //打印结果
    var_dump($arr);
}

当然这只是冒泡的初步使用，不难可以看出，有很大的优化空间。比如说在第二轮循环完毕就已经是一个有序的数组了，但是我们的程序还是会循环6次，在这种情况下，我们需要对我们的冒泡进行优化：

/**
 * 给指定数组按照从小到大排序
 *
 * @param  array  $arr [待排序的数组]
 * @return [type]      [返回为数组]
 */
public function sort($arr=array(1,2,3,6,4,3)){
    //对整个数组进行遍历
    for($i=0;$i<count($arr)-1;$i++){
        //有序标记，默认为true,用1表示
        $isSorten=1;
        //每一轮的冒泡处理
        for($j=0;$j<count($arr)-1-$i;$j++){
            //如果当前循环元素比他的后一位大
            if($arr[$j]>$arr[$j+1]){
                //暂存当前循环的值
                $tmp=$arr[$j];
                //交换两个元素的位置
                $arr[$j]=$arr[$j+1];
                $arr[$j+1]=$tmp;
                //因为有元素交换，所以将true改为false，用0表示
                $isSorten=0;
            }
        }
        //如果$isSorted为真，结束循环
        if ($isSorten) {
            break;
        }
    }
    //打印结果
    var_dump($arr);
}

这是第二版优化，当然，有第二版就有第三版。第三版我们主要侧重优化一下性能，当然示例的数组可能不太明显看出来，如果换成array(3,1,4,5,6,7)可能会容易看出来，那就是其实1后面的循序已经是我们想要的了，但是我们的程序还是会挨个比较，让我们来解决他：

/**
 * 给指定数组按照从小到大排序
 *
 * @param  array  $arr [待排序的数组]
 * @return [type]      [返回为数组]
 */
public function sort($arr=array(1,2,3,6,4,3)){
    //记录最后一次交换顺序的位置
    $listChangeIndex=0;
    //表示边界，即每次比较到这里就可以了
    $sortBorber =count($arr)-1;
    //对整个数组进行遍历
    for($i=0;$i<count($arr)-1;$i++){
        //有序标记，默认为true,用1表示
        $isSorten=1;
        //每一轮的冒泡处理
        for($j=0;$j<$sortBorber;$j++){
            //如果当前循环元素比他的后一位大
            if($arr[$j]>$arr[$j+1]){
                //暂存当前循环的值
                $tmp=$arr[$j];
                //交换两个元素的位置
                $arr[$j]=$arr[$j+1];
                $arr[$j+1]=$tmp;
                //因为有元素交换，所以将true改为false，用0表示
                $isSorten=0;
                //更新为最后一次交换元素的位置
                $listChangeIndex=$j;
            }
        }
        $sortBorber=$listChangeIndex;
        //如果$isSorted为真，结束循环
        if ($isSorten) {
            break;
        }
    }
    //打印结果
    var_dump($arr);
}

鸡尾酒排序

如你所见，冒泡算法是从左到右进行比较的。如果说冒泡算法是单向，那么鸡尾酒算法就是双向，就像现在的火车，有两个车头，一头开到终点后，另外一头接着开。

/**
 * 给指定数组按照从小到大排序
 *
 * @param  array  $arr [待排序的数组]
 * @return [type]      [返回为数组]
 */
public function sort($arr=array(1,2,3,6,4,3,6,3,8)){
    $tem=0;
    //对整个数组进行遍历
    for($i=0;$i<count($arr)/2;$i++){
        //有序标记，默认为true,用1表示
        $isSorten=1;
        //基数轮
        for($j=1;$j<count($arr)-1-$i;$j++){
            //如果当前循环元素比他的后一位大
            if($arr[$j]>$arr[$j+1]){
                //暂存当前循环的值
                $tmp=$arr[$j];
                //交换两个元素的位置
                $arr[$j]=$arr[$j+1];
                $arr[$j+1]=$tmp;
                //因为有元素交换，所以将true改为false，用0表示
                $isSorten=0;
            }
        }
        //如果$isSorted为真，结束循环
        if ($isSorten) {
            break;
        }
        //偶数轮开始前重新定义为true,用1表示
        $isSorten=1;
        //偶数轮，从右向左比较
        for($j=count($arr)-1-$i;$j>1;$j--){
            //如果当前循环元素比他的后一位小
            if($arr[$j]<$arr[$j-1]){
                //暂存当前循环的值
                $tmp=$arr[$j];
                //交换两个元素的位置
                $arr[$j]=$arr[$j-1];
                $arr[$j-1]=$tmp;
                //因为有元素交换，所以将true改为false，用0表示
                $isSorten=0;
            }
        }

         //如果$isSorted为真，结束循环
        if ($isSorten) {
            break;
        }
    }
    //打印结果
    var_dump($arr);
}

两者的特点呢也比较容易区分，鸡尾酒排序减少了排序的回合，相比于冒泡排序，代码量几乎是增加了一倍。
比较冒泡排序，鸡尾酒排序更适合大部分元素已经有序的情况。

其他算法待补充……

本作品采用《CC 协议》，转载必须注明作者和本文链接