PHPer面試指南-算法篇

SimpleTriangle 發布于2019-06-28 18:19 / 1472人閱讀

摘要：快速排序快速排序是對冒泡排序的一種改進。獲取中間數兩值相等，返回元素比目標大，查找左部元素比目標小，查找右部查找失敗擴展閱讀冒泡排序實現快速排序實現各種經典算法常見算法面試篇實現二分查找法

本書的 GitHub 地址：https://github.com/todayqq/PH...

算法可以說是大廠的必考題，對于算法，一定要理解其中的精髓、原理。

冒泡排序

冒泡排序的原理：一組數據，比較相鄰數據的大小，將值小數據在前面，值大的數據放在后面。

function bubble_sort($arr)  
{  
    $count = count($arr);  
    if (0 == $count) {
        return false;  
    }

    for($i = 0; $i < $count; $i++){  
        for($j = 0; $j< $count-1-$i; $j++){
          　　if($arr[$j] > $arr[$j+1]){
              　　$temp        = $arr[$j];
              　　$arr[$j]     = $arr[$j+1];
              　　$arr[$j+1]   = $temp;
         　　}
   　　 }
    }  
    return $arr;  
}

這樣的一個數組 array(6, 3, 8, 2, 9, 1)，排序過程是怎樣的？細節問題不在過多論述，有興趣可以從擴展閱讀中尋找答案。

快速排序

快速排序是對冒泡排序的一種改進。

實現思想是：通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行快速排序，整個排序過程可以遞歸進行，以達到整個序列有序的目的。

簡單來說就是：找到當前數組中的任意一個元素（一般選擇第一個元素），作為標的，新建兩個空數組，遍歷整個數組元素，如果遍歷到的元素比當前的元素要小，那么就放到左邊的數組，否則放到右面的數組，然后再對新數組進行同樣的操作。

function quick_sort($arr) {
    $count = count($arr);
    if(1 >= $count) {
        return arr;
    }

    $base_num = $arr[0]; //選擇標的
    $left_array = array();//小于標的
    $right_array = array();//大于標的

    for($i = 1; $i < $count; $i++) {
        if($base_num > $arr[$i]) {
            $left_array[] = $arr[$i];
        } else {
            $right_array[] = $arr[$i];
        }
    }
    //再分別對左邊和右邊的數組，進行相同的排序處理方式
    $left_array = quick_sort($left_array);
    $right_array = quick_sort($right_array);

    //最終合并
    return array_merge($left_array, array($base_num), $right_array);
}

二分查找（折半查找）

實現思想：將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找后一子表。

function binSearch($arr, $target){  
    $height = count($arr)-1;  
    $low = 0;  

    while($low <= $height){  
        $mid = floor(($low+$height)/2);//獲取中間數

        //兩值相等，返回 
        if($arr[$mid] == $target){  
            return $mid; 

        //元素比目標大，查找左部 
        } elseif ($arr[$mid] < $target){
            $low = $mid + 1;  

        //元素比目標小，查找右部
        } elseif ($arr[$mid] > $target){  
            $height = $mid - 1;  
        }  
    }  
    return "查找失敗";  
}

擴展閱讀

PHP 冒泡排序

php實現快速排序

PHP實現各種經典算法

PHP常見算法-面試篇

php實現二分查找法

GPU云服務器云服務器自然語言處理算法面試字符串算法面試題面試c語言算法編程題 phper

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/28156.html

PHPer 面試指南-擴展閱讀資源整理

摘要：前端篇收集的前端面試題和答案前端開發面試題史上最全的前端面試題匯總及答案前端工程師手冊協議工作原理協議運行機制的概述協議篇原理原理解析的工作原理與的區別理解后端篇年的面試總結垃圾回收機制面向對象設計淺談說清楚是什么和的區別索引原理及慢查前端篇收集的前端面試題和答案前端開發面試題史上最全的web前端面試題匯總及答案前端工程師手冊 HTTP協議：工作原理 SSL/TLS協議運行...

wemall 2019-06-28 18:19 評論0 收藏0
PHPer面試指南-前言

摘要：先說一下面試時的心態，剛入門的程序員，技術實力不高，又大多不善言談，面試一旦遇到難題，很容易心態失衡驚慌失措語無倫次，最終丟掉了。其實大可不必，心態坦然，是面試必備的一點。本書的 GitHub 地址：https://github.com/todayqq/PH... 作為一位程序員，面試過多次，也面試過很多人，最近又在找工作，總結一下面試經驗和面試題，希望可以幫到正在找工作的小伙伴們...

includecmath 2019-06-28 18:20 評論0 收藏0
PHPer面試指南-協議篇

摘要：地址每次面試多多少少都會被問到等等之類協議，協議相關的問題也可以說是面試必備，所以我把這些知識單獨收集成了一篇文章。即標志位和標志位均為。發送完畢后，服務器端進入狀態。認證服務器對客戶端進行認證以后，確認無誤，同意發放令牌。 Git 地址：https://github.com/todayqq/PH... 每次面試多多少少都會被問到 HTTP、HTTPS、TCP、Socket、 OAu...

megatron 2019-06-28 18:35 評論0 收藏0
PHPer面試指南-PHP 篇

摘要：本書的地址篇收集了一些常見的基礎進階面試題，基礎的面試題不再作答。如何實現持久化持久化，將在內存中的的狀態保存到硬盤中，相當于備份數據庫狀態。相當于備份數據庫接收到的命令，所有被寫入的命令都是以的協議格式來保存的。本書的 GitHub 地址：https://github.com/todayqq/PH... PHP 篇收集了一些常見的基礎、進階面試題，基礎的面試題不再作答。基礎篇 ...

stackvoid 2019-06-28 18:19 評論0 收藏0
PHPer面試指南-Web 篇

摘要：擴展閱讀收集的前端面試題和答案前端開發面試題史上最全的前端面試題匯總及答案前端工程師手冊協議工作原理協議運行機制的概述本書的 GitHub 地址：https://github.com/todayqq/PH... 對于大公司，很少會有全棧工程師這個崗位，全棧是個花哨的詞，對于現在比較熱門的技術，不論是 Vue 還是 Laravel，只要智商不差，看著文檔，都能寫出一個 CURD 來，...

cnio 2019-06-28 18:19 評論0 收藏0