PHP常用几种排序

PHP常用几种排序

php常用的几种排序

  • 1 冒泡排序
    • 1.1 描述:
    • 1.2 动画:
    • 1.3 代码案例:
  • 2 快速排序
    • 2.1 描述:
    • 2.2 动画:![在这里插入图片描述](https://up-gz.zsyts.cn/wp-content/uploads/2023/05/0b5615eabe6c17a9100ec11ef28ef6f8.png#pic_center)
    • 2.3 代码案例:
  • 3 插入排序
    • 3.1 描述:
    • 3.2 动画:
    • 3.3 代码案例:
  • 4 选择排序
    • 4.1 描述:
    • 4.2 动画:
    • 4.3 代码案例:
    • 总结

1 冒泡排序

​ 冒泡排序又称为泡式排序,是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误则交换两个元素,走访数列的工作是重复的进行直到没有需要交换的,也就是说该数列已经排序完成,这个算法名字的由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

1.1 描述:

  1. 从头开始比较两个元素,如果顺序错误则交换两个元素,循环比较数组直到没有需要交换的
  2. 1和2、2和3… 2
  3. 里面的循环执行完第一轮,最末尾的元素就是最大的元素,外层循环走完,数组也算排序完成

1.2 动画:

在这里插入图片描述

1.3 代码案例:

    function bubbleSort(){
        $arr=[45,64,100,98,2,334,55,1];
        //数组长度
        $length=count($arr);
        if(!$length){
           //防止空数组
           return $arr;
        }
        //第一次循环控制循环次数,循环次数=数组长度-1
        for($i=0;$i<$length-1;$i++){
            //第二次循环比较数组的每个元素,循环次数=数组长度-已循环次数
            //已循环次数=$i-1,因为是从数组的0下标开始的
            $exchanged=true;
            for($j=0;$j<$length-$i-1;$j++){
                //后一位元素比前一位元素小则交换位置
                if($arr[$j]>$arr[$j+1]){
                    $tmp=$arr[$j];
                    $arr[$j]=$arr[$j+1];
                    $arr[$j+1]=$tmp;
                    $exchanged=false;
                }
            }
            if($exchanged){
               break;
            }
        }
        return $arr;
     }

2 快速排序

​ 快速排序,又称分区交换排序,简称快排,它采用了一种分治的策略,通常称其为分治法,把一个序列分为较小和较大的2个子序列,然后递归的排序两个子系列

2.1 描述:

  1. 选取第一个元素为中间数
  2. 分别放到小于中间的左数组和大于中间数的右数组
  3. 重复调用当前方法,直到不能数组不能在分割,合并数组
  4. 因为重复调用方法都没有执行完,不断地递归合并,排序也就完成了

2.2 动画:
在这里插入图片描述

2.3 代码案例:

       function Quicksort($arr=[45,64,100,98,2,334,334,55,55,55,1,7]){
        //二分排序
        $length = count($arr);
        if($length<=1){
            //当数组不能再分割的时候跳出
            return $arr;
        }
        $left=[];
        $right=[];
        //分割成两个小于中间数的和大于等于中间数的数组
        for($i=1;$i<$length;$i++){
            $middit[0]=$arr[0];
            if($arr[$i]<$middit[0]){
                $left[]=$arr[$i];
            }else{
                $right[]=$arr[$i];
            }
        }
        //重复调用当前方法,直到不能数组不能分割,递归返回合并
        $left=$this->Quicksort($left);
        $right=$this->Quicksort($right);
        return array_merge($left,$middit,$right);
    }

3 插入排序

​ 插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序的数据,在已排序的序列中从后向前扫描,找到响应的位置并插入。

3.1 描述:

  1. 默认第一个元素是排序过的
  2. 取出上一个元素,如果该元素大于当前元素,则向后挪动,如果没有就不发生变化

3.2 动画:

在这里插入图片描述

3.3 代码案例:

    function InsertionSort(){
        $arr=[45,64,100,98,2,334,55,1];
        //数组长度
        $length=count($arr);
        if(!$length){
           //防止空数组
           return $arr;
        }
       //第一次循环控制循环次数
        for($i=1;$i<$length;$i++){
            //默认第一个元素排序过的,比较时会从第一个开始
            //循环比较前面已经排序过的元素,如果有大于自己的元素的就交换,如果没有不发生交换
            for($j=$i-1;$j>=0;$j--){
               //后一位元素比前一位元素小则交换位置
                if($arr[$j+1]<$arr[$j]){
                    $tmp=$arr[$j];
                    $arr[$j]=$arr[$j+1];
                    $arr[$j+1]=$tmp;
                }
            }
        }
        return $arr;
     }

4 选择排序

选择排序是一种简单直观的排序算法。首先在未排序序列中找到最大(小)元素,存放到排序序列的起始位置,然后在从剩余的未排序的元素中据需寻找最大(小)元素,然后放到已排序的序列的末尾,一次类推,知道所有元素均排序完毕。

4.1 描述:

  1. 默认第一个元素是为最小
  2. 和剩余元素对比,如果有比他小的就记录小于他的元素位置,等内循环一圈后交换位置

4.2 动画:

在这里插入图片描述

4.3 代码案例:

    function SelectionSort(){
        $arr=[45,64,100,98,2,334,55,1];
        $count=count($arr);
        for($i=0;$i<=$count;$i++){
            $min=$i;
            for($j=$i+1;$j<$count;$j++){  
                //从未比较的元素开始循环  
                if($arr[$j]<$arr[$min]){
                   //比较到小元素则记录其下标
                    $min=$j;    
                }
            }
            //使用临时变量交换最小元素
            if($min!=$i){    
                $temp = $arr[$min];
                $arr[$min] = $arr[$i];
                $arr[$i] = $temp;
            }
        }
        return $arr;
     }

总结

选择排序的时间复杂度是定死的。就是0(n^2)。与数据的输入状态无关。因为对于选择排序,当我们从乱序的区间中找极值时,总是一味的去遍历这个乱序的区间。直到乱序的区间遍历完成后,我们才能确定极值
插入排序的时间复杂度与数据的输入有关,当初始时给你的数据就是有序的,那么这种状态就是插入排序最好的情况,因为对于当前要插入的数x1来说,我们在从后往前遍历乱序区间时,只要找到了应该待的位罝,就不用在追历乱序区间中剩下的元素了

                       

点击阅读全文

上一篇 2023年 5月 28日 am10:23
下一篇 2023年 5月 28日 am10:24