整理常見的PHP演算法面試題
- 藏色散人轉載
- 2021-05-28 13:42:555272瀏覽
這篇文章向大家介紹整理常見的PHP演算法面試題，有一定的參考價值，有需要的朋友可以參考一下，希望對大家有幫助。
1、插入排序（一維數組） 基本思想：每次將一個待排序的資料元素，插入到前面已經排好序的數列中的適當位置，使數列依然有序；直到待排序資料元素全部插入完為止。
範例：
[初始關鍵字] [49] 38 65 97 76 13 27 49
J=2(38) [38 49] 65 97 76 13 27 49
J=3(65) [38 49 65] 97 76 13 27 49
J=4(97) [38 49 65 97] 76 13 27 49
#J=5(76) [38 49 65 76 97] 13 27 49
J=6(13) [13 38 49 65 76 97] 27 49
#J=7(27 ) [13 27 38 49 65 76 97] 49
J=8(49) [13 27 38 49 49 65 76 97]
function insert_sort($arr){
$count = count($arr);
for($i=1; $i<$count; $i++){
$tmp = $arr[$i];
$j = $i - 1;
while($arr[$j] > $tmp){
$arr[$j+1] = $arr[$j];
$arr[$j] = $tmp;
$j--;
}
}
return $arr;
}2、選擇排序（一維陣列） 基本想法：每一趟從待排序的資料元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最後，直到全部待排序的資料元素排完。範例：
[初始關鍵字] [49 38 65 97 76 13 27 49]
第一趟排序後13 ［38 65 97 76 49 27 49]
第二趟排序後13 27 ［65 97 76 49 38 49]
第三趟排序後13 27 38 [97 76 49 65 49]
第四趟排序後13 27 38 49 [49 97 65 76]
第五趟排序後13 27 38 49 49 [97 97 76]
第六趟排序後13 27 38 49 49 76 [76 97]
第七趟排序後13 27 38 49 49 76 76 [97]
最後排序結果13 27 38 49 49 76 76 97
function select_sort($arr){
$count = count($arr);
for($i=0; $i<$count; $i++){
$k = $i;
for($j=$i+1; $j<$count; $j++){
if ($arr[$k] > $arr[$j]) $k = $j;
}
if($k != $i){
$tmp = $arr[$i];
$arr[$i] = $arr[$k];
$arr[$k] = $tmp;
}
}
return $arr;
}#3、冒泡排序（一維數組） 基本思想：兩兩比較待排序資料元素的大小，發現兩個資料元素的次序相反時即進行交換，直到沒有反序的資料元素為止。排序過程：設想被排序的數組R［1..N］垂直豎立，將每個資料元素看作有重量的氣泡，根據輕氣泡不能在重氣泡之下的原則， 從下往上掃描數組R，凡掃描到違反本原則的輕氣泡，就使其向上” 漂浮”，如此反复進行，直至最後任何兩個氣泡都是輕者在上，重者在下為止。
範例：
49 13 13 13 13 13 13 13
38 49 27 27 27 27 27 27
65 38 49 38 38 38 38 38
97 65 38 49 49 49 49 49
76 97 65 49 49 49 49 49
13 76 97 65 65 65 65 #27##13 76 97 65 65 65 65 #27# 76 97 76 76 76 76
49 49 49 76 97 97 97 97
function bubble_sort($array){
$count = count($array);
if ($count <= 0) return false;
for($i=0; $i<$count; $i++){
for($j=$count-1; $j>$i; $j--){
if ($array[$j]<$array[$j-1]){
$tmp = $array[$j];
$array[$j] = $array[$j-1];
$array[$j-1] = $tmp;
}
}
}
return $array;
}4、快速排序（一維數組） 基本思想：在當前無序區R [1..H ] 中任取一個資料元素作為比較的」 基準」(不妨記為X)， 用此基準將目前無序區劃分為左右兩個較小的無序區：R [1..I-1] 和R [I 1..H]，且左邊的無序子區中資料元素均小於等於基準元素， 右邊的無序子區中資料元素皆大於等於基準元素，而基準X 則位於最終排序的位置上，即R [1..I-1]≤X.Key≤RI 1..H， 當R [1..I-1] 和R [I 1..H] 均非空時，分別對它們進行上述的劃分過程，直至所有無序子區中的資料元素均已排序為止。範例：
初始關鍵字[49 38 65 97 76 13 27 49］
第一次交換後［27 38 65 97 76 13 49 49］
。次交換後［27 38 49 97 76 13 65 49］
J 向左掃描，位置不變，第三次交換後［27 38 13 97 76 49 65 49］
I向右掃描，位置不變，第四次交換後［27 38 13 49 76 97 65 49］
J 向左掃描［27 38 13 49 76 97 65 49］
（一次劃分過程）
初始關鍵字［49 38 65 97 76 13 27 49］
一趟排序之後［27 38 13］ 49 ［76 97 65 49］
二趟排序之後［13］ 27 ［38］ 49 ［49 65］76 ［97］三趟排序之後13 27 38 49 49 ［65］#三趟排序之後13 27 38 49 49 ［65］76 97#結果13 27 38 49 49 65 76 97各趟排序之後的狀態function quickSort(&$arr){
if(count($arr)>1){
$k=$arr[0];
$x=array();
$y=array();
$_size=count($arr);
for($i=1;$i<$_size;$i++){
if($arr[$i]<=$k){
$x[]=$arr[$i];
}elseif($arr[$i]>$k){
$y[]=$arr[$i];
}
}
$x=quickSort($x);
$y=quickSort($y);
return array_merge($x,array($k),$y);
}else{
return$arr;
}
}5、希爾排序（shell sort）— O (n log n)functionshell_sort(&$arr){
if(!is_array($arr))return;
$n=count($arr);
for($gap=floor($n/2);$gap>0;$gap=floor($gap/=2)){
for($i=$gap;$i<$n;++$i){
for($j=$i-$gap;$j>=0&&$arr[$j+$gap]<$arr[$j];$j-=$gap){
$temp=$arr[$j];
$arr[$j]=$arr[$j+$gap];
$arr[$j+$gap]=$temp;
}
}
}
}6、二分查找/**
* 二分算法查找
* @param array $array 要查找的数组
* @param int $min_key 数组的最小下标
* @param int $max_key 数组的最大下标
* @param mixed $value 要查找的值
* @return boolean
*/
function bin_search($array,$min_key,$max_key,$value){
if($min_key <= $max_key){
$key = intval(($min_key+$max_key)/2);
if($array[$key] == $value){
return true;
}elseif($value < $array[$key]){
return bin_search($array,$min_key,$key-1,$value);
}else{
return bin_search($array,$key+1,$max_key,$value);
}
}else{
return false;
}
}7、線性表的刪除（數組中實現）###function delete_array_element($array, $i) {
$len = count($array);
for ($j=$i; $j<$len; $j++){
$array[$j] = $array[$j+1]
}
array_pop($array);
return $array;
}###8、字串長度###function strlen($str) {
if ($str == '') return 0;
$count = 0;
while (1){
if ($str[$count] != NULL){
$count++;
continue;
}else{
break;
}
}
return $count;
}###9、字串翻轉########################################################## function strrev($str) {
if ($str == '') return 0;
for ($i=(strlen($str)-1); $i>=0; $i--){
$rev_str .= $str[$i];
}
return $rev_str;
}###10、字串比較###function strcmp($s1, $s2) {
if (strlen($s1) < strlen($s2)) return -1;
if (strlen($s1) > strlen($s2)) return 1;
for ($i=0; $i<strlen($s1); $i++){
if ($s1[$i] == $s2[$i]){
continue;
}else{
return false;
}
}
return 0;
}###11、尋找字串###function strstr($str, $substr) {
$m = strlen($str);
$n = strlen($substr);
if ($m < $n) return false;
for ($i=0; $i<=($m-$n+1); $i++){
$sub = substr($str, $i, $n);
if (strcmp($sub, $substr) == 0) return $i;
}
return false;
}###12、字串替換###function str_replace($substr, $newsubstr, $str) {
$m = strlen($str);
$n = strlen($substr);
$x = strlen($newsubstr);
if (strchr($str, $substr) == false) return false;
for ($i=0; $i<=($m-$n+1); $i++){
$i = strchr($str, $substr);
$str = str_delete($str, $i, $n);
$str = str_insert($str, $i, $newstr);
}
return $str;
}###13、插入一段字串###function str_insert($str, $i, $substr) {
for($j=0; $j<$i; $j++){
$startstr .= $str[$j];
}
for ($j=$i; $j<strlen($str); $j++){
$laststr .= $str[$j];
}
$str = ($startstr . $substr . $laststr);
return $str;
} ###14、刪除一段字串###function str_delete($str, $i, $j){
for ($c=0; $c<$i; $c++){
$startstr .= $str[$c];
}
for ($c=($i+$j); $c<strlen($str); $c++){
$laststr .= $str[$c];
}
$str = ($startstr . $laststr);
return $str;
}###15、複製字串###function strcpy($s1, $s2){
if (strlen($s1)==NULL || !isset($s2)) return;
for ($i=0; $i<strlen($s1); $i++){
$s2[] = $s1[$i];
}
return $s2;
}
16、连接字符串
function strcat($s1, $s2){
if (!isset($s1) || !isset($s2)) return;
$newstr = $s1;
for($i=0; $i<count($s); $i++){
$newstr .= $st[$i];
}
return $newsstr;
}###17、簡單編碼函數（對應於php_decode 函數）###function php_encode($str) {
if ($str=='' && strlen($str)>128)
return false;
for($i=0; $i<strlen($str); $i++){
$c = ord($str[$i]);
if ($c>31 && $c<107)
$c += 20;
if ($c>106 && $c<127)
$c -= 75;
$word = chr($c);
$s .= $word;
}
return $s;
}
}
}####18、簡單解碼函數（對應於php_encode 函數）###function php_decode($str) {
if ($str=='' && strlen($str)>128) return false;
for($i=0; $i<strlen($str); $i++){
$c = ord($word);
if ($c>106 && $c<127) $c = $c-20;
if ($c>31 && $c<107) $c = $c+75;
$word = chr($c);
$s .= $word;
}
return $s;
}###19、簡單加密函數（對應於php_decrypt 函數）###function php_encrypt($str) {
$encrypt_key = 'abcdefghijklmnopqrstuvwxyz1234567890';
$decrypt_key = 'ngzqtcobmuhelkpdawxfyivrsj2468021359';
if (strlen($str) == 0) return false;
for ($i=0; $i<strlen($str); $i++){
for ($j=0; $j<strlen($encrypt_key); $j++){
if ($str[$i] == $encrypt_key[$j]){
$enstr .= $decrypt_key[$j];
break;
}
}
}
return $enstr;
}###20、簡單解密函數（對應於php_encrypt 函數）###function php_decrypt($str) {
$encrypt_key = 'abcdefghijklmnopqrstuvwxyz1234567890';
$decrypt_key = 'ngzqtcobmuhelkpdawxfyivrsj2468021359';
if (strlen($str) == 0) return false;
for ($i=0; $i<strlen($str); $i++){
for ($j=0; $j<strlen($decrypt_key); $j++){
if ($str[$i] == $decrypt_key[$j]){
$enstr .= $encrypt_key[$j];
break;
}
}
}
return $enstr;
}####推薦學習：《###PHP影片教學###》###以上是整理常見的PHP演算法面試題的詳細內容。更多資訊請關注PHP中文網其他相關文章！