必须掌握的四种常见php排序算法及其效率分析

本文实例讲述了PHP四种排序算法实现及效率分析。

时间复杂度

执行算法所需要的计算工作量。一般来说,计算机算法是问题规模n的函数f(n),算法的时间复杂度也因此记做T(n)=o(f(n)

计算时间复杂度的方法:

  1. 得出算法的计算次数公式
  2. 用常数1取代所有时间中的所有加法常数
  3. 修改后的运行次数函数中,只保留最高阶项
  4. 如果最高阶存在且不是1,则去除与这个项相乘的系数

举例:

1. 常数阶O(1)
function test($n){
    echo $n;
    echo $n;
    echo $n;
}
// 该算法执行次数是3,是一个常数,用时间复杂度表示是O(1)
2. 线性阶O(n)
// 1+2+3+4+5+6+....+n
$sum = 0;
for($i=1; $i<=$n; $i++){
    $sum += $i;
}
// O(n)
3. 平方阶O(n^2)
$sum = 0;
for (i=0; i<n; i++){
    for (j=0; j<n; j++){
        $sum += $j;
    }
}
// O(n^2)
4. 立方阶O(n^3)

三层循环

5. 对数阶O(log2n)
while($n>=1){
    $n = $n/2;
}
6. 线性对数阶O(nlog2n)
7. k次方阶O(n^K)
8. 指数阶O(2^n)

效率:

随着n的不断增大,时间复杂度不断增大,算法花费时间越多。

o(1) > o(log2n) > o(n) > o(nlog2n) > o(n^2) > O(n^3) > o(2^n) > o(n!) > o(n^n)

空间复杂度

算法需要消耗的内存空间,记作S(n)=O(f(n)

包括程序代码所占用的空间,输入数据所占用的空间和辅助变量所占用的空间这三个方面

计算和表示方法与时间复杂度类似,一般用复杂度的渐近性来表示。

排序算法

1-1. 冒泡排序

思路:想象一个大水池里有N多还未排好序列的气球,较大的先冒出来,然后依次是较小的往上冒。意思就是对数组进行多轮冒泡,每一轮对数组中的元素两两比较,调整位置,冒出一个最大的数来。

代码演示:
/*
* 冒泡排序1
* @param $arr 所要排序的数组
* @return mixed 返回的数组
*/

function bubbleSort($arr){
    $len = count($arr);
    if ($len <= 1) {
        return $arr;
    }
    for($i=0; $i<=$len-1; $i++){ //冒泡的轮数(最多$len-1轮)
        for($j=0; $j<=$len-$i-1; $j++){ //每一轮冒泡(两两比较,大者后移)
            if($arr[$j] > $arr[$j+1]){ //前者大于后者,则交换位置
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] =$tmp;
            }
        }
    }
    return $arr;
}

$arr = [3,44,38,6,21,15,1,33,10];
print_r(bubbleSort($arr));

// 结果:
// Array ( [0] => 1 [1] => 3 [2] => 6 [3] => 10 [4] => 15 [5] => 21 [6] => 33 [7] => 38 [8] => 44 )

为了提高冒泡排序算法的效率,主要需要改进的地方有:
(1)减少冒泡的轮数:当一轮冒泡排序中没有发生位置交换时表示数组已排好序了,应立即退出循环。
(2)减少每一轮比较的次数:对数组中已经排好序的部分元素不再对它们进行比较。

//改进后:
/*
* 冒泡排序2
* @param Array $arr 所要排序的数组
* @param bool  $flag 交换标志
* @return mixed 返回的数组
*/
function bubbleSort($arr){
    $len = count($arr);
    if($len <= 1){
        return $arr;
    }
    
    for($i=1; $i<$len; $i++){ //冒泡的轮数(最多$len-1轮)
        $flag = 0;
        for($j=0; $j<$len-$i; $j++){ //每一轮冒泡(两两比较,大者后移)
            if($arr[$j] > $arr[$j+1]){ //前者大于后者,则交换位置
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] =$tmp;
                $flag = 1;
            }
        }
        if($flag==0){//没有发生位置交换,排序已完成
            break;
        }
    }
    return $arr;
}
1-2. 快速排序

思路:递归算法。先选择数组的第一个元素作为标准,然后把小于或等于它和大于它的数分别放入两个数组中,对这两个数组也进行相同的处理,最后合并这两个数组和第一个元素。

代码演示:
/*
* 快速排序
* @param Array $arr 所要排序的数组
* @return mixed 返回的数组
*/
function quickSort($arr){
    $len = count($arr);
    if($len <= 1) { //若数组只有一个元素,直接返回
        return $arr;
    }
    $largeArr = array(); //存放大数
    $smallArr = array(); //存放小数
    $cur = $arr[0];  //分类基数
    
    for($i=1; $i<$len; $i++) { //遍历数组元素,对每个元素进行归类
        if($arr[$i] > $cur) {
            $largeArr[] = $arr[$i];
        } else {
            $smallArr[] = $arr[$i];
        }
    }

    //分别对大数组和小数组进行相同的处理
    $smallArr = quickSort($smallArr);
    $largeArr = quickSort($largeArr);
    //合并小数组、分类基数和大数组
    return array_merge($smallArr,array($cur),$largeArr);
}
1-3. 选择排序

思路:每次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

代码演示:
/*
* 选择排序
* @param Array $arr 所要排序的数组
* @return mixed 返回的数组
*/
function selectSort($arr){
    $n = count($arr);
    for($i=$n-1; $i>0; $i--) { //选择排序的轮数($n-1轮)
        $pos = $i; //假设最大元素的位置
        for($j=0;$j<$i;$j++) { //每一轮:从未选择过的元素中选择最大的数
            if($arr[$j] > $arr[$pos]) { //所在位置元素比目前最大元素大,标志其位置
                $pos = $j;
            }
        }
        if($pos != $i) { //将最大元素放入指定的位置
            $tmp = $arr[$pos];
            $arr[$pos] = $arr[$i];
            $arr[$i] = $tmp;
        }
    }
    return $arr;
}
1-4. 插入排序

思路:每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。

代码演示:
/*
* 插入排序
* @param Array $arr 所要排序的数组
* @return mixed 返回的数组
*/
function insertSort($arr){
    $n = count($arr);
    for($i=1; $i<$n; $i++) { //从第二个元素开始插入
        for($j=$i-1;$j>=0;$j--) { //与前面的数比较,找到插入的位置
            if($arr[$j] > $arr[$j+1]) { //比前面的数小,交换位置
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $tmp;
            } else { //大于或等于前面的数,表示已找到插入的位置
                break;
            }
        }
    }
    return $arr;
}

各个排序算法的时间复杂度和空间复杂度:

注:快速排序在数组乱序是效率是最好的,在数组有序时效率是最差的。

总结

快速排序、归井排序的理想时间复杂度都是O(nlog2n),但是快速排序的时间复杂度并不稳定,最坏情况下复杂度为O(n^2),所以最理想的算法还是归并排序。

查找算法

1. 二分查找

原理: 从数组的中间元素开始,如果中间元素正好是要查找的元素搜索结束,如果某一个特定元素大于或者小于中间元素,则在数组大于或者小于中间元素的那一半中查找,而且跟开始一样从中间开始比较,如果某一步骤数组为空,代表找不到。

时间复杂度:最差(o(log2n)),平均(o(log2n))
空间复杂度:迭代(o(1)),递归(o(log2n))

2. 顺序查找

原理: 按一定的顺序检查数组中每一个元素,直到找到所要寻找的特定值为止。

时间复杂度:最差(o(n)),平均(o(n))
空间复杂度:o(1)

6 人推荐

声明:本文原创发布于加藤非博客,转载请注明出处:加藤非博客 jiatengfei.com 。如有侵权,请联系本站删除。

加藤非博客
请先登录再发表评论
  • 最新评论

  • 总共2条评论
加藤非博客

淡薄的微凉记忆:棒棒哒

2018-06-29 16:51:33 回复

加藤非博客

加藤非加藤非博客小鲁老师

2018-06-29 16:42:55 回复