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

little bottle

發布： 2023-04-05 22:08:01

轉載

2246 人瀏覽過

一般應對面試，我們無可厚非的去刷下面試題。對於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);
        }

登入後複製