冒泡排序算法
基本思想:
對需要排序的數組從後往前(逆序)進行多遍的掃描,當發現相鄰的兩個數值的次序與排序要求的規則不一緻時,就将這兩個數值進行交換。這樣比較小(大)的數值就将逐漸從後面向前面移動。
<?php
function mysort($arr)
{
for($i = ; $i < count($arr); $i++)
{
for ($j=; $j< count($arr) - $i - ; $j++)
{
if($arr[$j] < $arr[$j+])
{
$temp = $arr[$j];
$arr[$j] = $arr[$j+];
$arr[$j+] = $temp ;
}
}
}
return $arr;
}
$arr = array(,,);
var_dump(mysort($arr));
?>
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
快速排序
基本思想:
在數組中挑出一個元素(多為第一個)作為标尺,掃描一遍數組将比标尺小的元素排在标尺之前,将所有比标尺大的元素排在标尺之後,通過遞歸将各子序列分别劃分為更小的序列直到所有的序列順序一緻。
<?php
//快速排序
function quick_sort($arr)
{
//先判斷是否需要繼續進行
$length = count($arr);
if($length <= )
{
return $arr;
}
$base_num = $arr[];//選擇一個标尺 選擇第一個元素
//初始化兩個數組
$left_array = array();//小于标尺的
$right_array = array();//大于标尺的
for($i=; $i<$length; $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);
}
$arr = array(,,);
var_dump(quick_sort($arr));
?>
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
二分查找
基本思想:
假設資料是按升序排序的,對于給定值x,從序列的中間位置開始比較,如果目前位置值等于x,則查找成功;若x小于目前位置值,則在數列的前半段中查找;若x大于目前位置值則在數列的後半段中繼續查找,直到找到為止。(資料量大的時候使用)
<?php
//二分查找
function bin_search($arr,$low,$high,$k)
{
if($low <= $high)
{
$mid = intval(($low + $high)/);
if($arr[$mid] == $k)
{
return $mid;
}
else if($k < $arr[$mid])
{
return bin_search($arr,$low,$mid-,$k);
}
else
{
return bin_search($arr,$mid+,$high,$k);
}
}
return -;
}
$arr = array(,,,,,,,,,);
print(bin_search($arr,,,));
?>
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
順序查找
基本思想:
從數組的第一個元素開始一個一個向下查找,如果有和目标一緻的元素,查找成功;如果到最後一個元素仍沒有目标元素,則查找失敗。
<?php
//順序查找
function seq_search($arr,$n,$k)
{
$array[$n] = $k;
for($i = ;$i < $n; $i++)
{
if($arr[$i] == $k)
{
break;
}
}
if($i < $n)
{
return $i;
}
else
{
return -;
}
}
?>
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
周遊檔案夾
<?php
function my_scandir($dir)
{
$files = array();
if($handle = opendir($dir))
{
while (($file = readdir($handle))!== false)
{
if($file != '..' && $file != '.')
{
if(is_dir($dir."/".$file))
{
$files[$file]=my_scandir($dir."/".$file);
}
else
{
$files[] = $file;
}
}
}
closedir($handle);
return $files;
}
}
var_dump(my_scandir('../'));
?>
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
寫一個函數,盡可能高效的從一個标準url中取出檔案的擴充名
<?php
function getExt($url)
{
$arr = parse_url($url);//parse_url解析一個 URL 并傳回一個關聯數組,包含在 URL 中出現的各種組成部分
//'scheme' => string 'http' (length=)
//'host' => string 'www.sina.com.cn' (length=)
//'path' => string '/abc/de/fg.php' (length=)
//'query' => string 'id=1' (length=)
$file = basename($arr['path']);// basename函數傳回路徑中的檔案名部分
$ext = explode('.', $file);
return $ext[count($ext)-];
}
print(getExt('http://www.sina.com.cn/abc/de/fg.html.php?id=1'));
?>
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
實作中文字元串截取無亂碼的方法
可使用mb_substr,但是需要確定在php.ini中加載了php_mbstring.dll,即確定“extension=php_mbstring.dll”這一行存在并且沒有被注釋掉,否則會出現未定義函 數的問題。
資料結構和算法
使對象可以像數組一樣進行foreach循環,要求屬性必須是私有。(Iterator模式的PHP5實作,寫一類實作Iterator接口)(騰訊)
<?php
class Test implements Iterator{
private $item = array('id'=>,'name'=>'php');
public function rewind(){
reset($this->item);
}
public function current(){
return current($this->item);
}
public function key(){
return key($this->item);
}
public function next(){
return next($this->item);
}
public function valid(){
return($this->current()!==false);
}
}
//測試
$t=new Test;
foreach($t as $k=>$v){
echo$k,'--->',$v,'<br/>';
}
?>
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
用PHP實作一個雙向隊列(騰訊)
<?php
class Deque{
private $queue=array();
public function addFirst($item){
return array_unshift($this->queue,$item);
}
public function addLast($item){
return array_push($this->queue,$item);
}
public function removeFirst(){
return array_shift($this->queue);
}
public function removeLast(){
return array_pop($this->queue);
}
}
?>
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
請使用冒泡排序法對以下一組資料進行排序10 2 36 14 10 25 23 85 99 45。
<?php
// 冒泡排序
function bubble_sort(&$arr){
for ($i=,$len=count($arr); $i < $len; $i++) {
for ($j=; $j < $len-$i; $j++) {
if ($arr[$j-] > $arr[$j]) {
$temp = $arr[$j-];
$arr[$j-] = $arr[$j];
$arr[$j] = $temp;
}
}
}
}
// 測試
$arr = array(,,,,,,,,,);
bubble_sort($arr);
print_r($arr);
?>
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
寫出一種排序算法(要寫出代碼),并說出優化它的方法。(新浪)
<?php
//快速排序
function partition(&$arr,$low,$high){
$pivotkey = $arr[$low];
while($low<$high){
while($low < $high && $arr[$high] >= $pivotkey){
$high--;
}
$temp = $arr[$low];
$arr[$low] = $arr[$high];
$arr[$high] = $temp;
while($low < $high && $arr[$low] <= $pivotkey){
$low++;
}
$temp=$arr[$low];
$arr[$low]=$arr[$high];
$arr[$high]=$temp;
}
return$low;
}
function quick_sort(&$arr,$low,$high){
if($low < $high){
$pivot = partition($arr,$low,$high);
quick_sort($arr,$low,$pivot-);
quick_sort($arr,$pivot+,$high);
}
}
?>
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
關于猴子的面試題
一群猴子排成一圈,按1,2,...,n依次編号。然後從第1隻開始數,數到第m隻,把它踢出圈,從它後面再開始數,再數到第m隻,在把它踢出去...,如此不停的進行下去,直到最後隻剩下一隻猴子為止,那隻猴子就叫做大王。要求程式設計模拟此過程,輸入m、n,輸出最後那個大王的編号。(新浪)(小米)
<?php
// 方案一,使用php來模拟這個過程
function king($n,$m){
$mokey = range(, $n);
$i = ;
while (count($mokey) >) {
$i += ;
$head = array_shift($mokey);//一個個出列最前面的猴子
if ($i % $m !=) {
#如果不是m的倍數,則把猴子傳回尾部,否則就抛掉,也就是出列
array_push($mokey,$head);
}
// 剩下的最後一個就是大王了
return $mokey[];
}
}
// 測試
echo king(,);
// 方案二,使用數學方法解決
function josephus($n,$m){
$r = ;
for ($i=; $i <= $m ; $i++) {
$r = ($r + $m) % $i;
}
return $r+;
}
// 測試
print_r(josephus(,));
?>
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
二維數組排序算法函數,能夠具有通用性,可以調用php内置函數。
<?php
//二維數組排序,$arr是資料,$keys是排序的健值,$order是排序規則,1是降序,0是升序
function array_sort($arr,$keys,$order=){
if(!is_array($arr)){
return false;
}
$keysvalue=array();
foreach($arr as $key => $val){
$keysvalue[$key] = $val[$keys];
}
if($order == ){
asort($keysvalue);
}else{
arsort($keysvalue);
}
reset($keysvalue);
$new_array=array();
foreach($keysvalue as $key=> $val){
$new_array[$key]=$arr[$key];
}
return$new_array;
}
//測試
$person=array(
array('id'=>,'name'=>'zhangsan','age'=>),
array('id'=>,'name'=>'lisi','age'=>),
array('id'=>,'name'=>'apple','age'=>)
);
$result = array_sort($person,'name',);
print_r($result);
?>
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
順序查找和二分查找(也叫做折半查找)算法,順序查找必須考慮效率,對象可以是一個有序數組(小米)
<?php
/**
* 順序查找
* @param array $arr 數組
* @param $k 要查找的元素
* @return mixed 成功傳回數組下标,失敗傳回-1
*/
function seq_sch($arr,$k){
for ($i=,$n = count($arr); $i < $n; $i++) {
if ($arr[$i] == $k) {
break;
}
}
if($i < $n){
return $i;
}else{
return -;
}
}
/**
* 二分查找,要求數組已經排好順序
* @param array $array 數組
* @param int $low 數組起始元素下标
* @param int $high 數組末尾元素下标
* @param $k 要查找的元素
* @return mixed 成功時傳回數組下标,失敗傳回-1
*/
function bin_sch($array,$low,$high,$k){
if ($low <= $high) {
$mid = intval(($low + $high) / );
if ($array[$mid] == $k) {
return $mid;
} elseif ($k < $array[$mid]) {
return bin_sch($array,$low,$mid - ,$k);
} else{
return bin_sch($array,$mid + ,$high,$k);
}
}
return -;
}
// 測試:順序查找
$arr1 = array(,,,,,,,);
echo seq_sch($arr1,);//結果為6
echo "<br />";
// 測試:二分查找
$arr2 = array(,,,,,,,);
echo bin_sch($arr2,,,);//結果為5
?>
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
洗牌算法
<?php
$card_num = ;//牌數
function wash_card($card_num){
$cards = $tmp = array();
for($i = ;$i < $card_num;$i++){
$tmp[$i] = $i;
}
for($i = ;$i < $card_num;$i++){
$index = rand(,$card_num-$i-);
$cards[$i] = $tmp[$index];
unset($tmp[$index]);
$tmp = array_values($tmp);
}
return $cards;
}
// 測試:
print_r(wash_card($card_num));
?>