又到了金三銀四找工作的時間，相信很多開發者都在找工作或者準備著找工作了。一般應對面試，我們無可厚非的去刷下麵試題。對於PHPer來說，除了要熟悉自己所做的項目，還有懂的基本的演算法。下麵來分享下PHP面試中常會問到的演算法：冒泡排序和快速排序

冒泡排序：一一對比排序

基本思想：

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

圖解：

1.第一次：拿著數組的第一個元素，分別從第二個元素開始比較，如果前面的元素比後面的元素大，則交換兩個元素，得到較大的這個值，繼續向後比較，直到數組元素的最後，實現一次冒泡（冒泡一次，就得到當前“剩餘”數組的最大值，並且放到數組的“最後面”）

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

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

代碼：

 1         $arr = array(3,2,6,0,1,4,7);
 2         //因為排序需要每次將一個元素與數組的其他元素進行比較，所以需要兩層迴圈來控制
 3         //外層迴圈控制冒泡次數
 4         //記憶體迴圈比較每次的大小，得到每次的最大值（泡）
 5  
 6         for($i = 0,$length = count($arr);$i < $length;$i++){
 7         
 8                  //記憶體迴圈
 9                  for($j = 0;$j < ($length - $i - 1);$j++){
10                          //拿著j變數所對應的數組元素，與後面的元素進行比較
11                          if($arr[$j] > $arr[$j + 1]){
12                                   //交換位置
13                                   $temp              = $arr[$j];
14                                   $arr[$j]           = $arr[$j+1];
15                                   $arr[$j+1]         = $temp;
16                          }
17                  }
18         }

總結：

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

快速排序：用空間換時間

基本思想：

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

圖解：

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

遞歸思路

1.遞歸點：如果兩個數組的元素大於1，就需要再進行分解

2.遞歸出口：數組元素變成1的時候

代碼：

 1 //待排序數組
 2         $arr = array(5,3,8,2,6,4,7);
 3         //函數實現快速排序
 4         function quick_sort($arr){
 5                  //判斷參數是否是一個數組
 6                  if(!is_array($arr)) return false;
 7  
 8                  //遞歸出口：數組長度為1就直接返回數組
 9                  $length = count($arr);
10                  if($length <= 1) return $arr;
11 
12                  //數組元素有多個
13                  $left = $right = array();
14                  //使用for迴圈進行遍歷，把第一個元素當做比較的對象
15                  for($i = 1;$i < $length;$i++){
16                          //判斷當前元素值的大小
17                          if($arr[$i] < $arr[0]){
18                                   //當前元素小於標準元素，放到左邊數組
19                                   $left[] = $arr[$i];
20                          }else{
21                                   $right[] = $arr[$i];
22                          }
23                  }
24                  //遞歸調用
25                  $left = quick_sort($left);
26                  $right = quick_sort($right);
27  
28                  //將所有的結果合併
29                  return array_merge($left,array($arr[0]),$right);
30         }

總結：

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

------------------------------------------------------------------------------