「PHP」常用四种排序算法以及性能对比

作为一名合格的PHPer怎么能不接触到算法这个高大上的东西了，今天就来针对初学者来说一说最基础的4种排序算法：冒泡排序、选择排序、插入排序、快速排序（分区排序）。

冒牌排序

核心思想：比较相邻两个元素的大小，如果左边大于右边，则调换两个元素的位置；

缺点：需要将数组中的每一个元素都进行对比，耗时较长

 $array = [5,10,3,4,2,8,7,9,11];
$length = count($array);
//第一层控制循环的次数，元素有多少个就需要循坏多少次
for ($i = 1; $i < $length; $i++) {

    //第二层循环比较相邻元素的大小，调换位置
    for ($j = 0; $j < $length - $i; $j++) {
        if ($array[$j] > $array[$j + 1]) {
            $tmp           = $array[$j + 1];    //临时保存,替换两者位置
            $array[$j + 1] = $array[$j];
            $array[$j]     = $tmp;
        }
    }
}
return $array;  

选择排序

核心思想：取后一位元素与当前元素对比，然后将小的元素插入到最前位置

 $array = [5,10,3,4,2,8,7,9,11];
$length = count($array);
//第一层控制循环的次数，元素有多少个就需要循坏多少次
    for ($i = 0; $i < $length - 1; $i++) {
        $p = $i;    //假设当前元素是最小元素的下标;
        
        //第二层循环从下一个元素开始比较
        //注意这里的开始位置是从基准元素的下一个位置开始的
        //可以认为前面的元素是已经排序完成了
        for ($j = $i + 1; $j < $length; $j++) {
            //找到更小的元素下标
            if ($array[$p] > $array[$j]) {
                $p = $j;
            }
        }
        
        //如果最小元素不是之前假设的元素,则调换位置
        if ($p != $i) {
            $tmp       = $array[$p];
            $array[$p] = $array[$i];
            $array[$i] = $tmp;
        }
    }
return $array;  

插入排序

核心思想：每次循环中，从下一个元素开始比较，然后将最小的元素插入到数组的最前面(但是为了更好的性能，我们通常采用替换位置的方法来将最小元素位移到数组的前面)

 $array = [5,10,3,4,2,8,7,9,11];
$length = count($array);
//第一层控制循环的次数，元素有多少个就需要循坏多少次
    for ($i = 1; $i < $length; $i++) {
        $tmp = $array[$i];  //记录当前基准元素

        //从基准元素的下一个元素开始比较
        for ($j = $i - 1; $j >= 0; $j--) {
            
            //如果下一个元素比当前基准元素要小则调换位置            
            if ($tmp < $array[$j]) {
                $array[$j + 1] = $array[$j];
                $array[$j]     = $tmp;
            } else {
                break;
            }
        }

    }
return $array;  

快速排序

核心思想：取任意元素为基准，然后二分递归一直执行，每次都是小的左边，大的右边。最后将结果合并

 $array = [5,10,3,4,2,8,7,9,11];
//如果不是数组则终止执行
    if (!is_array($array)) return false;
    
    $length = count($array);
    
    //如果数组元素小于2个则终止执行
    if ($length <= 1) return $array;
    
    
    $left = $right = [];
    //任意取一个元素作为基准元素
    //将小于该基准的元素存放进左边
    //将大于该基准的元素存放进右边
    for ($i = 1; $i < $length; $i++) {
        if ($array[$i] > $array[0]) {
            $right[] = $array[$i];
        } else {
            $left[] = $array[$i];
        }
    }

    //递归执行
    $left  = quick_sort($left);
    $right = quick_sort($right);

    //将结果合并
    return array_merge($left, [$array[0]], $right);  

最后总结

经测试，四种方法中 快速排序 的性能最高。数组取10000个元素，然后分别执行消耗的时间如图所示

在实际开发中，能直接使用到这样代码的场景并不多，但是作为程序员缺必须掌握这种开发思想逻辑。如果只是完成了业务开发就万事大吉的话注定后面的路子会越来越难走的。