PHP 일반 정렬 알고리즘 알아보기-PHP 튜토리얼-php.cn

일반적인 정렬 알고리즘에는 버블 정렬, 빠른 정렬, 선택 정렬 및 삽입 정렬이 포함됩니다. 이 기사에서는 PHP의 일반적인 정렬 참고 사항을 요약했으며 이것이 도움이 되기를 바랍니다.

요구 사항: 여러 개의 숫자가 포함된 배열을 작은 것부터 큰 것까지 정렬합니다.

정렬 알고리즘

[1]. 버블 정렬

아이디어 분석:
N 수소가 많다고 상상해 보세요. 아직 순서대로 배열되지 않은 큰 수영장의 풍선은 큰 풍선이 먼저 나타나고 작은 풍선이 차례로 나타납니다. 즉, 인접한 두 숫자를 매번 비교하여 작은 숫자를 앞에 두고 큰 숫자를 뒤에 두고 그렇지 않으면 위치를 바꿉니다.

PHP 일반 정렬 알고리즘 알아보기

코드 구현: (여러 작성 방법 예시, 루프 본문의 판단 조건에 주의) 첫 번째 유형과 두 번째 유형을 사용하는 것이 좋습니다.

   /**
     * 交换方法
     * @param array $arr 目标数组
     * @param $a 索引a
     * @param $b 索引b
     * @param bool $flag 交换标志
     * @return bool
     */
    function swap(array &$arr,$a,$b,$flag = false){
        // 遍历i后面的元素，只要该元素小于当前元素，就把较小的往前冒泡
        if($arr[$a] > $arr[$b]){
            $temp = $arr[$a];
            $arr[$a] = $arr[$b];
            $arr[$b] = $temp;
            $flag = true;
        }
        return $flag;
    }
    /**
     * 第一种写法
     * @param $arr 所要排序的数组
     * @return mixed 返回的数组
     */
    function bubbleSort($arr) {
        $len = count($arr);
        if ($len <= 1) {return $arr;}
        //该层循环控制 需要冒泡的轮数
        for ($i = 0; $i < $len-1; $i++) {
            //该层循环用来控制每轮 冒出一个数 需要比较的次数
            for ($j = $i + 1; $j < $len; $j++) {
                // 或者 $this->swap($arr,$j,$j+1);
                $this->swap($arr,$i,$j);
            }
        }
        return $arr;
    }
    //第二种写法
    public function BubbleSort2($arr){
        $len = count($arr);
        if ($len <= 1) {return $arr;}
        for ($i = 0;$i < $len-1;$i++){
            //TODO 本趟排序开始前，交换标志应为假
            $flag = false;
            for ($j = 0;$j <= $len-2;$j++){
                $flag = $this->swap($arr,$j,$j+1,$flag);
            }
            if(!$flag) return $arr;
        }
        return $arr;
    }
    //第三种写法
    function BubbleSort3(array &$arr){
        $len = count($arr);
        if ($len <= 1) {return $arr;}
        for($i = 0;$i < $len-1;$i++){
            //从后往前逐层上浮小的元素 $j >= 0
            for($j = $len - 2;$j >= $i ;$j --){
                $this->swap($arr,$j,$j+1);
            }
        }
        return $arr;
    }
    //第四种写法
    function bubbleSort4($arr)
    {
        $len = count($arr);
        if ($len <= 1) {return $arr;}
        for($i = 0;$i < $len-1;$i++) {
            for($j = 0;$j < $len-$i-1;$j++) {
                $this->swap($arr,$j,$j+1);
            }
        }
        return $arr;
    }

로그인 후 복사

요약:

시간 복잡도: O(n^2)

보충: PHP 내장 함수 sort() 또는 rsort()를 사용할 수 있습니다.

위 함수는 키에 따라 인덱스 배열을 정렬합니다. 값(배열) 셀에 새 키 이름이 지정되며, 이는 단순히 순서를 바꾸는 대신 원래 키 이름을 삭제합니다. 성공하면 TRUE를 반환하고, 그렇지 않으면 FALSE

[2]를 반환합니다. 선택 정렬

아이디어 분석:
매번 정렬할 데이터 요소 중 가장 작은(또는 가장 큰) 요소를 선택하여 저장합니다. 순서 정렬할 모든 데이터 요소가 정렬될 때까지의 시작 위치

PHP 일반 정렬 알고리즘 알아보기

코드 구현

   /*
    * @param 选择排序法
    * 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
    * */
    function selectSort($arr){
        //双重循环完成，外层控制轮数，内层控制比较次数
        $len = count($arr);
        if ($len <= 1) {return $arr;}
        for ($i = 0; $i < $len-1; $i++) {
            $minIndex = $i;
            // 找出i后面最小的元素与当前元素交换
            for ($j = $i + 1; $j < $len; $j++) {
                if ($arr[$minIndex] > $arr[$j]){
                    $minIndex = $j;
                }
            }
            if ($minIndex != $i) {
                $temp = $arr[$i];
                $arr[$i] = $arr[$minIndex];
                $arr[$minIndex] = $temp;
            }
        }
        return $arr;
    }

로그인 후 복사

요약:

시간 복잡도: O(n^2)

불안정한 정렬 방법(예: The 시퀀스 [5, 5, 3]은 처음으로 첫 번째 [5]를 [3]과 교환하여 처음 5가 두 번째 5 뒤로 이동하게 합니다.

선택에서 요소가 현재 요소보다 작고 작은 요소가 현재 요소와 동일한 요소 뒤에 나타나면 교환 후 안정성이 파괴됩니다

가장 좋은 경우는 이미 In이 있다는 것입니다. 순서는 0번 교환하고, 최악의 경우 n-1번 교환하고, 역순으로 n/2번 교환한다. 교환 횟수는 비교보다 훨씬 적기 때문에 n 값이 작을 때는 선택 정렬이 버블 정렬

[3]보다 빠릅니다. 아이디어 분석: 각 단계에서 정렬할 레코드는 모두 삽입될 때까지 키 값의 크기에 따라 이전에 정렬된 파일의 적절한 위치에 삽입됩니다. (따라서 숫자에 1을 더한 새로운 순서의 데이터를 얻음)

설명:

⒈ 첫 번째 요소부터 시작하여 요소가 정렬된 것으로 간주할 수 있습니다.

⒉ 정렬된 요소 이후 다음 요소를 꺼냅니다. 순서에서 뒤에서 앞으로

⒊ (정렬된) 요소가 새 요소보다 크면 해당 요소를 다음 위치로 이동하세요

⒋ 정렬된 요소가 다음보다 작거나 같은 위치를 찾을 때까지 3단계를 반복하세요. the new element

⒌ 다음 위치에 새 요소를 삽입합니다

⒍ 2~5단계를 반복합니다

코드 구현

PHP 일반 정렬 알고리즘 알아보기 여기에 작성하는 방법에는 두 가지가 있는데, 루프를 작성하는 주요 방법은 다음과 같습니다. 조금 다르기 때문에 참고하시면 됩니다.

   /*
    * 插入排序法
    * 每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
    * */
    function insertSort($arr){
        $len = count($arr);
        if ($len <= 1) {return $arr;}
        //先默认$array[0]，已经有序，是有序表
        for($i = 1;$i < $len;$i++){
            if ($arr[$i] < $arr[$i-1]){
                $insertVal = $arr[$i]; //$insertVal是准备插入的数
                $insertIndex = $i - 1; //有序表中准备比较的数的下标
                while($insertIndex >= 0 && $insertVal < $arr[$insertIndex]){
                    $arr[$insertIndex + 1] = $arr[$insertIndex]; //将数组往后挪
                    $insertIndex--; //将下标往前挪，准备与前一个进行比较
                }
                if($insertIndex + 1 !== $i){
                    $arr[$insertIndex + 1] = $insertVal;
                }
            }
        }
        return $arr;
    }
    function insertSort2($arr){
        $len = count($arr);
        if ($len <= 1) {return $arr;}
        //先默认$array[0]，已经有序，是有序表
        for($i = 1;$i < $len;$i++){
            if ($arr[$i] < $arr[$i-1]){
                $insertVal = $arr[$i]; //$insertVal是准备插入的数
                //$j 有序表中准备比较的数的下标
                //$j-- 将下标往前挪，准备与前一个进行比较
                for ($j = $i-1;$j >= 0 && $insertVal < $arr[$j];$j--){
                    $arr[$j+1]= $arr[$j];//将数组往后挪
                }
                $arr[$j + 1] = $insertVal;
            }
        }
        return $arr;
    }

로그인 후 복사

요약:

시간 복잡도: O(n^2)

공간 복잡도: O(1) (삽입해야 할 데이터를 기록하는 데 사용)

안정적인 정렬 방법

소량 데이터에 적합한 알고리즘 정렬

교환 작업보다 비교 작업 비용이 큰 경우 이진 검색 방법을 사용하면 비교 작업 횟수를 줄일 수 있습니다. 이 알고리즘은 이진 검색 정렬이라고 하는 삽입 정렬의 변형으로 간주될 수 있습니다.

[4]. 빠른 정렬

아이디어 분석: 한 번의 정렬 과정을 통해 정렬할 데이터를 두 개의 독립적인 부분으로 분할합니다.

그런 다음 이 방법을 사용하면 데이터의 두 부분을 각각 빠르게 정렬할 수 있으므로 전체 정렬 프로세스가 순서대로 수행될 수 있습니다.

코드 구현

注：网上多数为quick_sort2（）这类的写法，感觉并非原算法的描述，建议可做参考.

或许代码quick_sort()有所欠缺，并未发现能有较快的排序效果，尴尬了.

   /**
     * @param $arr 目标数组
     * @param int $l 左起坐标
     * @param $r 右起坐标 初始化传入数组时，$r = count($arr)-1
     * @return mixed
     */
    public  function quick_sort(&$arr, $l=0, $r)
    {
        $length = count($arr);
        //先判断是否需要继续进行 递归出口:数组长度为1，直接返回数组
        if(!is_array($arr)||$length <= 1) {return $arr;}
        if ($l < $r)
        {
            $i = $l;
            $j = $r;
            $baseVal = $arr[$l];
            while ($i < $j)
            {
                // 从右向左找第一个小于$baseVal的数
                while($i < $j && $arr[$j] >= $baseVal)
                    $j--;
                if($i < $j)
                    $arr[$i++] = $arr[$j];
                // 从左向右找第一个大于等于$baseVal的数
                while($i < $j && $arr[$i] < $baseVal)
                    $i++;
                if($i < $j)
                    $arr[$j--] = $arr[$i];
            }
            $arr[$i] = $baseVal;
            $this->quick_sort($arr, $l, $i - 1); // 递归调用
            $this->quick_sort($arr, $i + 1, $r);
            return $arr;
        }
    }
    /*
    * 快速排序法
    * */
    public function quick_sort2($arr) {
        $length = count($arr);
        //先判断是否需要继续进行 递归出口:数组长度为1，直接返回数组
        if(!is_array($arr)||$length <= 1) {return $arr;}
        //选择第一个元素作为基准
        $baseValue = $arr[0];
        //遍历除了标尺外的所有元素，按照大小关系放入两个数组内
        //初始化两个数组
        $leftArr = array();  //小于基准的
        $rightArr = array();  //大于基准的
        //使用for循环进行遍历，把选定的基准当做比较的对象
        for($i = 1; $i<$length; $i++) {
            if( $arr[$i] < $baseValue) {
                //放入左边数组
                $leftArr[] = $arr[$i];
            } else {
                //放入右边数组
                $rightArr[] = $arr[$i];
            }
        }
        //再分别对左边和右边的数组进行相同的排序处理方式递归调用这个函数
        $leftArr = $this->quick_sort2($leftArr);
        $rightArr = $this->quick_sort2($rightArr);
        //合并 左边 标尺 右边， 注意：array($baseValue),关联着重复数据
        return array_merge($leftArr, array($baseValue), $rightArr);
    }

로그인 후 복사

小结：

既不浪费空间又可以快一点的排序算法

最差时间复杂度O(N^2)，平均时间复杂度为O(NlogN)

【五】.计数排序

思路分析

计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序

算法描述：

找出待排序的数组中最大和最小的元素；

统计数组中每个值为i的元素出现的次数，存入数组C的第i项；

对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；

反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

PHP 일반 정렬 알고리즘 알아보기

代码实现

   /**
     * 计数排序
     * @param $arr
     * @return array
     */
    function countingSort($arr)
    {
        $len = count( $arr );
        if( $len <= 1 ) return $arr;
        // 找出待排序的数组中最大值和最小值
        $min = min($arr);
        $max = max($arr);
        // 计算待排序的数组中每个元素的个数
        $countArr = array();
        for($i = $min; $i <= $max; $i++)
        {
            $countArr[$i] = 0;
        }
        foreach($arr as $v)
        {
            $countArr[$v] +=  1;
        }
        $resArr = array();
        foreach ($countArr as $k=>$c) {
            for($i = 0; $i < $c; $i++)
            {
                $resArr[] = $k;
            }
        }
        return $resArr;
    }

로그인 후 복사

小结：

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

计数排序不是比较排序，排序的速度快于任何比较排序算法

最佳情况：T(n) = O(n+k)
最差情况：T(n) = O(n+k)
平均情况：T(n) = O(n+k)

限制条件很多注意

【六】.桶排序

思路分析

假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)

算法描述

设置一个定量的数组当作空桶；

遍历输入数据，并且把数据一个一个放到对应的桶里去；

对每个不是空的桶进行排序；

从不是空的桶里把排好序的数据拼接起来。

PHP 일반 정렬 알고리즘 알아보기

代码实现

   /**
     * 木桶排序设计
     * @param $arr 目标数组
     * @param int $bucketCount 分配的木桶数目（整数）
     * @return array
     */
    public function bucketSort($arr,$bucketCount = 10)
    {
        $len = count($arr);
        $max = max($arr)+1;
        if ($len <= 1) {return $arr;}
        //填充木桶
        $arrFill = array_fill(0, $bucketCount, []);
        //开始标示木桶
        for($i = 0; $i < $len ; $i++)
        {
            $key = intval($arr[$i]/($max/$bucketCount));
            array_push($arrFill[$key] , $arr[$i]);
            //TODO 测试发现：如果此处调用，耗时翻倍
            /*if(count($arrFill[$key])){
                $arrFill[$key] = $this->insertSort($arrFill[$key]);
            }*/
        }
        //对每个不是空的桶进行排序
        foreach ($arrFill as $key=>$f){
            if (count($f)){
                $arrFill[$key] = $this->insertSort($f);
            }
        }
        //开始从木桶中拿出数据
        for($i = 0; $i < count($arrFill); $i ++)
        {
            if($arrFill[$i]){
                for($j = 0; $j <= count($arrFill[$i]); $j++)
                {   //这一行主要用来控制输出多个数字
                    if ($arrFill[$i][$j]){
                        $arrBucket[] = $arrFill[$i][$j];
                    }
                }
            };
        }
        return $arrBucket;
    }

로그인 후 복사

注：

上述代码是我根据对木桶排序的定义进行的设计，因为网上多数的PHP代码感觉不合规范，其中的insertSort()为借用的文中所写的插入排序

通过测试发现，此方法耗时比countingSort()要长好多，此处仅做参考不做推荐。

总结：

当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。

稳定的排序方法

桶排序是计数排序的升级版

最佳情况：T(n) = O(n+k)
最差情况：T(n) = O(n^2)
平均情况：T(n) = O(n+k)

附录

【1】排序算法总结

PHP 일반 정렬 알고리즘 알아보기

【2】自行分析

此处提供一个网上多数作为“桶排序”的类似代码段,个人认为并非描述中的排序算法，倒是与文中涉及到的“计数排序”更为契合.

  /**
     * @param $arr 目标数组
     * @return array 返回的已排序数组
     */
    public function bOrCSort($arr)
    {
        $len = count($arr);
        $max = max($arr);
        if ($len <= 1) {return $arr;}
        //填充木桶
        $arrFill = array_fill(0, $max, 0);
        for($i = 0; $i < $len ; $i++)
        {
            $arrFill[$arr[$i]] ++;
        }
        //开始从木桶中拿出数据
        for($i = 0; $i <= $max; $i ++)
        {
            for($j = 1; $j <= $arrFill[$i]; $j++)
            { //这一行主要用来控制输出多个数字
                $arrRes[] = $i;
            }
        }
        return $arrRes;
    }

로그인 후 복사

【3】用时测试

为了简单比较几种算法的用时大小，本人随机生成了数量为10000，数值在300以内的测试数组，文中介绍的算法用时如下：

bucketsort 用时：1013.6640071869 ms
countingSort 用时：5.6858062744141 ms
quick_sort 用时：66540.108919144 ms
selectSort 用时：15234.955072403 ms
bubbleSort 用时：162055.89604378 ms
insertSort 用时：12029.093980789 ms
内置sort 用时：3.0169486999512 ms

所以，简单需求的数组排序处理还是建议使用内置的sort()函数.