집 > 기사 > 백엔드 개발 > 일반적으로 사용되는 버블 정렬 및 빠른 정렬 알고리즘과 이진 검색 및 순차 검색을 PHP에서 알고리즘 구현

일반적으로 사용되는 버블 정렬 및 빠른 정렬 알고리즘과 이진 검색 및 순차 검색을 PHP에서 알고리즘 구현

不言원래의: 2018-08-22 16:34:371507검색

이 기사의 내용은 PHP에서 일반적으로 사용되는 버블 정렬 및 빠른 정렬 알고리즘과 이진 검색 및 순차 검색 알고리즘 구현에 대한 내용입니다. 도움이 필요한 친구들이 참고할 수 있기를 바랍니다. .

1. 버블 정렬

기본 아이디어:

두 개의 인접한 값의 순서가 밝혀진 경우 뒤에서 앞으로(역순으로) 정렬할 배열을 여러 번 스캔합니다. 정렬 요구 사항과 일치합니다. 규칙이 일치하지 않으면 두 값이 교환됩니다. 이런 식으로 작은(큰) 값이 뒤에서 앞으로 점차 이동하게 됩니다.

<?php
function mysort($arr)
{
for($i = 0; $i < count($arr); $i++)
{
$isSort = false;
for ($j=0; $j< count($arr) - $i - 1; $j++) 
{
if($arr[$j] < $arr[$j+1])
{
$isSort = true;
$temp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $temp ;
}
}
if($isSort)
{
break;
}
}
return $arr;
}
$arr = array(3,1,2);
var_dump(mysort($arr));
?>

2. 빠른 정렬

기본 아이디어:

배열의 요소(주로 첫 번째 요소)를 눈금자로 선택하고 배열을 한 번 스캔한 다음 눈금자보다 작은 요소를 눈금자 앞에 정렬합니다. 눈금자보다 큰 모든 요소는 눈금자 뒤에 배열되며, 모든 시퀀스가 동일한 순서가 될 때까지 재귀를 통해 각 하위 시퀀스를 더 작은 시퀀스로 나눕니다.

<?php
//快速排序
function quick_sort($arr) 
{
//先判断是否需要继续进行
$length = count($arr);
if($length <= 1) 
{
return $arr;
}
$base_num = $arr[0];//选择一个标尺 选择第一个元素
//初始化两个数组
$left_array = array();//小于标尺的
$right_array = array();//大于标尺的
for($i=1; $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(3,1,2);
var_dump(quick_sort($arr));
?>

3. 이진 검색

기본 개념:

주어진 값 x에 대해 현재 위치 값이 있으면 데이터가 오름차순으로 정렬되어 있다고 가정합니다. x와 같으면 검색이 성공합니다. x가 현재 위치 값보다 작으면 배열의 전반부에서 검색하고, x가 현재 위치 값보다 크면 배열의 후반부에서 검색을 계속합니다. 설립하다. (데이터 양이 많을 때 사용)

<?php
//二分查找
function bin_search($arr,$low,$high,$k)
{
 if($low <= $high)
{
$mid = intval(($low + $high)/2);
if($arr[$mid] == $k)
{
return $mid;
}
else if($k < $arr[$mid])
{
return bin_search($arr,$low,$mid-1,$k);
}
else
{
return bin_search($arr,$mid+1,$high,$k);
}
}
 return -1;
}
$arr = array(1,2,3,4,5,6,7,8,9,10);
print(bin_search($arr,0,9,3));
?>

4. 순차 검색

기본 아이디어:

배열의 첫 번째 요소부터 시작하여 아래로 하나씩 일치하는 요소가 있으면 검색합니다. target, 검색은 성공합니다. ; 마지막 요소까지 여전히 target 요소가 없으면 검색이 실패합니다.

<?php
//顺序查找
function seq_search($arr,$n,$k)
{
$array[$n] = $k;
for($i = 0;$i < $n; $i++)
{
if($arr[$i] == $k)
 {
break;
}
if($i < $n)
{
return $i;
}
else
{
return -1;
}
}
?>

5. 파일 아래의 모든 파일과 하위 폴더를 탐색할 수 있는 함수를 작성합니다.

<?php  
function my_scandir($dir)
{
$files = array();
if($handle = opendir($dir))
{
while (($file = readdir($handle))!== false) 
{
if($file != &#39;..&#39; && $file != &#39;.&#39;)
{
if(is_dir($dir."/".$file))
{
$files[$file]=my_scandir($dir."/".$file);
}
else
{
$files[] = $file;
}
}
}
closedir($handle);
return $files;
}
}
var_dump(my_scandir(&#39;../&#39;));
?>

6. 표준 URL에서 파일 확장자를 최대한 효율적으로 추출하는 함수를 작성합니다.

<?php
function getExt($url)
{
$arr = parse_url($url);//parse_url解析一个 URL 并返回一个关联数组，包含在 URL 中出现的各种组成部分
//&#39;scheme&#39; => string &#39;http&#39; (length=4)
//&#39;host&#39; => string &#39;www.sina.com.cn&#39; (length=15)
//&#39;path&#39; => string &#39;/abc/de/fg.php&#39; (length=14)
//&#39;query&#39; => string &#39;id=1&#39; (length=4)
$file = basename($arr[&#39;path&#39;]);// basename函数返回路径中的文件名部分
$ext = explode(&#39;.&#39;, $file);
 return $ext[count($ext)-1];
}
print(getExt(&#39;http://www.sina.com.cn/abc/de/fg.html.php?id=1&#39;));
?>

7. 잘못된 문자 없이 중국어 문자열을 가로채려면

mb_substr을 사용할 수 있지만 php_mbstring.dll이 php.ini에 로드되어 있는지 확인해야 합니다. 즉, "extension=php_mbstring.dll" 줄이 존재하고 있는지 확인해야 합니다. 주석 처리하지 않으면 정의되지 않은 함수 문제가 발생합니다.

일반적으로 사용되는 버블 정렬 및 빠른 정렬 알고리즘과 이진 검색 및 순차 검색을 PHP에서 알고리즘 구현

관련 기사