【PHP面試】面試必問的兩個簡單排序演算法解說:冒泡排序與快速排序

little bottle
發布: 2023-04-05 22:08:01
轉載
2425 人瀏覽過

一般應對面試,我們無可厚非的去刷下面試題。對於PHP開發者來說,除了要熟悉自己所做的項目,還有懂的基本的演算法。以下來分享下PHP面試中常會問到的演算法:冒泡排序與快速排序。

 

冒泡排序:一一比較排序

#基本思想:

重複走訪過要排序的元素列,依序比較兩個相鄰的元素,如果他們的順序(如從大到小)錯誤就把他們交換過來。走訪元素的工作是重複地進行直到沒有相鄰元素需要交換,也就是說該元素已經排序完成。

 

圖解:

1.第一次:拿著陣列的第一個元素,分別從第二個元素開始比較,如果前面的元素比後面的元素大,則交換兩個元素,得到較大的這個值,繼續向後比較,直到數組元素的最後,實現一次冒泡(冒泡一次,就得到目前「剩餘」數組的最大值,並且放到數組的「最後面」)

2.第二次開始,還是從第一個元素開始比較,但是只比較到數組長度要-1位置,每次的比較次數都依序-1

3.後面重複比較,直到最後沒有需要一堆數字需要比較

程式碼:

$arr = array(3,2,6,0,1,4,7);
        //因为排序需要每次将一个元素与数组的其他元素进行比较,所以需要两层循环来控制
        //外层循环控制冒泡次数
        //内存循环比较每次的大小,得到每次的最大值(泡)
 
        for($i = 0,$length = count($arr);$i < $length;$i++){
        
                 //内存循环
                 for($j = 0;$j < ($length - $i - 1);$j++){
                         //拿着j变量所对应的数组元素,与后面的元素进行比较
                         if($arr[$j] > $arr[$j + 1]){
                                  //交换位置
                                  $temp              = $arr[$j];
                                  $arr[$j]           = $arr[$j+1];
                                  $arr[$j+1]         = $temp;
                         }
                 }
        }
登入後複製

總結:

冒泡排序最好的時間複雜度是O(n),雖然說它不是最優的演算法,但是這是我們經常接觸到的,面試也會問到,所以我們一定要懂的基本原理,能理解到,能寫的出來

 

#快速排序:用空間換時間

#基本思想:

透過一趟排序將要排序的資料分割成獨立的兩部分,其中一部分的所有資料都比另外一部分的所有資料都要小,然後再按此方法對這兩部分資料分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個資料變成有序序列。

圖解:

 

 

找到目前陣列中的任一個元素,作為標準,新兩個空數組,遍歷整個數組元素,遍歷到的元素比當前元素要小,那麼放到左邊的數組;如果要大,放到另外一個數組中

遞歸思路

1.遞歸點:如果兩個陣列的元素大於1,就需要再進行分解

2.遞迴出口:陣列元素變成1的時候

程式碼:

//待排序数组
        $arr = array(5,3,8,2,6,4,7);
        //函数实现快速排序
        function quick_sort($arr){
                 //判断参数是否是一个数组
                 if(!is_array($arr)) return false;
 
                 //递归出口:数组长度为1就直接返回数组
                 $length = count($arr);
                 if($length <= 1) return $arr;

                 //数组元素有多个
                 $left = $right = array();
                 //使用for循环进行遍历,把第一个元素当做比较的对象
                 for($i = 1;$i < $length;$i++){
                         //判断当前元素值的大小
                         if($arr[$i] < $arr[0]){
                                  //当前元素小于标准元素,放到左边数组
                                  $left[] = $arr[$i];
                         }else{
                                  $right[] = $arr[$i];
                         }
                 }
                 //递归调用
                 $left = quick_sort($left);
                 $right = quick_sort($right);
 
                 //将所有的结果合并
                 return array_merge($left,array($arr[0]),$right);
        }
登入後複製

總結:

快速排序在一般的排序的方式中最快的排序方式,以遞歸為基礎,使用空間換時間。在一般的面試中會問到,要能知道基礎原理。

 【相關教學:PHP影片教學

以上是【PHP面試】面試必問的兩個簡單排序演算法解說:冒泡排序與快速排序的詳細內容。更多資訊請關注PHP中文網其他相關文章!

來源:cnblogs.com
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
作者最新文章
最新問題
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板