English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
이 글은 PHP의 고전 알고리즘을 요약한 예제입니다. 여러분과 공유하고, 다음과 같습니다:
1먼저 다이아몬드를 그려보겠습니다. 많은 사람들이 C를 배울 때 책에 그려놓은 것을 많이 봤습니다. 우리는 PHP로 그려보겠습니다. 반으로 그려졌습니다.
구상: 몇 행을 한 번에 반복할지, 그 안에서 공백과 별을 반복.
<?php
for($i=0;$i<=3;$i++{
echo str_repeat(" ",3-$i);
echo str_repeat("*"$i*2+1);
echo '<br/>';
}
2백그라운드 정렬, C에서의 기본 알고리즘, 작은 것부터 큰 것까지 순서대로 정렬.
구상: 이 문제는 작은 것부터 큰 것까지 정렬합니다. 첫 번째 턴에서 가장 작은 것을 정렬하고, 두 번째 턴에서 두 번째로 작은 것을 정렬하고, 세 번째 턴에서 세 번째로 작은 것을 정렬하고, 이렇게 계속합니다...
<?php
$arr = array(1,3,5,32,756,2,6);
$len = count($arr);
for ($i=0;$i<$len-1;$i++{
for ($j=$i+1;$j<$len;$j++{
if($arr[$i]>$arr[$j]){//작은 것부터 큰 것까지
$p = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $p;
}
}
}
var_dump($arr);
3양우각형, PHP로 작성.
구상: 각 행의 첫 번째와 마지막은 다음과 같습니다1변화가 없으며, 중간은 앞쪽 한 줄과 왼쪽 한 줄의 합입니다. 이 알고리즘은 이차원 배열을 사용하여 저장하며, 또 다른 알고리즘은 일차원 배열로도 구현할 수 있습니다. 행별로 출력하며, 관심이 있으면 써보세요.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
<?php
//각 행의 첫 번째와 마지막은 다음과 같습니다1，썼다6행
for($i=0; $i<6; $i++) {
$a[$i][0]=1;
$a[$i][$i]=1;
}
//出除了第一位和最后一位的值，保存在数组中
for($i=2; $i<6; $i++) {
for($j=1; $j<$i; $j++) {
$a[$i][$j] = $a[$i-1][$j-1]+$a[$i-1
}
}
//출력
for($i=0; $i<6; $i++{
for($j=0; $j<=$i; $j++) {
echo $a[$i][$j].' ';
}
echo '<br/>';
}
4、수열에 수를 삽입하고, 원래 순서를 유지하며 정렬 유지합니다.
추이: 삽입할 수보다 큰 위치를 찾고, 대체하고, 뒤의 수를 한 칸 뒤로 이동시킵니다.
<?php
$in = 2;
$arr = array(1,1,1,3,5,7);
$n = count($arr);
//삽입할 수가 가장 크다면, 직접 출력
if($arr[$n-1] < $in) {
$arr[$n+1] = $in; print_r($arr);
}
for($i=0; $i<$n; $i++) {
//삽입할 위치를 찾습니다
if($arr[$i] >= $in){
$t1= $arr[$i];
$arr[$i] = $in;
//뒤의 데이터를 한 칸 뒤로 이동시킵니다
for($j=$i+1; $j<$n+1; $j++) {
$t2 = $arr[$j];
$arr[$j] = $t1;
$t1 = $t2;
}
//출력
print_r($arr);
die;
}
}
5、수열을 정렬합니다 (퀵 정렬 알고리즘).
추이: 한 번의 정렬을 통해 두 부분으로 나누고, 그 두 부분을 재귀적으로 정렬한 후 병합합니다.
<?php
function q($array) {
if (count($array) <= 1) {return $array;}
//$key를 경계로 두 개의 서브 배열로 분할합니다
$key = $array[0];
$l = array();
$r = array();
//각각 재귀적으로 정렬한 후 하나의 배열로 병합합니다
for ($i=1; $i<count($array); $i++) {
if ($array[$i] <= $key) { $l[] = $array[$i]; }
else { $r[] = $array[$i]; }
}
$l = q($l);
$r = q($r);
return array_merge($l, array($key), $r);
}
$arr = array(1,2,44,3,4,33);
print_r( q($arr) );
6、 필요한 요소를 찾기 위해 배열에서 검색 (이분 검색 알고리즘).
추이: 배열 중 하나의 값을 경계로, 끝까지 재귀적으로 검색합니다.
<?php
function find($array, $low, $high, $k){
if ($low <= $high){
$mid = intval(($low+$high)/2);
if ($array[$mid] == $k){
return $mid;
};elseif ($k < $array[$mid]){
return find($array, $low, $mid-1, $k);
}else{
return find($array, $mid+1, $high, $k);
}
}
die('Not have...');
}
//test
$array = array(2,4,3,5);
$n = count($array);
$r = find($array,0,$n,5)
7다른 배열을 합치지 않고 array_merge() 사용하지 않음, 주제는 포럼에서 온 것입니다.
의사 결정: 각 배열을 순회하며 새로운 배열을 구성합니다.
<?php
function t(){
$c = func_num_args()-1;
$a = func_get_args();
//print_r($a);
for($i=0; $i<=$c; $i++{
if(is_array($a[$i])){
for($j=0; $j<count($a[$i]); $j++{
$r[] = $a[$i][$j];
}
} else {
die('Not a array!');
}
}
return $r;
}
//test
print_r(t(range(1,4),range(1,4),range(1,4
echo '<br/>';
$a = array_merge(range(1,4),range(1,4),range(1,4));
print_r($a);
8년 소를 찾는 것: 한 마리의 소가, n년 후에4세에 임신할 수 있으며, 매년 한 마리를 낳으며, 모두가 동일한 소는 아니며, n년 후에15세에 중성화되어 더 이상 소를 낳을 수 없습니다.20세에 죽음, n년 후 몇 마리의 소가 있을까요？（포럼에서 온 것）
<?php
function t($n) {
static $num = 1
for($j=1; $j<=$n; $j++{
if($j>=4 && $j<15) {$num++;t($n-$j);}
if($j==20){$num--;}
}
return $num;
}
//test
echo t(8);
====================다른 알고리즘=========================
발버블 정렬 (bubble sort) — O(n2)
$data = array(3,5,9,32,2,1,2,1,8,5);
dump($data);
BubbleSort($data);
dump($data);
function BubbleSort(& $arr)
{
$limit = count($arr);
for($i=1; $i<$limit; $i++)
{
for($p=$limit-1; $p>=$i; $p--)
{
if($arr[$p]}-1] > $arr[$p])
{
$temp = $arr[$p-1];
$arr[$p-1] = $arr[$p];
$arr[$p] = $temp;
}
}
}
}
function dump( $d )
{
echo '<pre>';
print_r($d);
echo '</pre>';
}
삽입 정렬 (insertion sort) — O(n2)
$data = array(6,13,21,99,18,2,25,33,19,84);
$nums = count($data)-1;
dump( $data );
InsertionSort($data,$nums);
dump( $data );
function InsertionSort(& $arr,$n )
{
for( $i=1; $i<=$n; $i++ )
{
$tmp = $arr[$i];
for( $j = $i; $j>0 && $arr[$j-1]>$tmp; $j-- )
{
$arr[$j] = $arr[$j-1];
}
$arr[$j] = $tmp;
}
}
function dump( $d )
{
echo '<pre>';print_r($d);echo '</pre>';
}
希尔排序 (shell sort) — O(n log n)
$data = array(6,13,21,99,18,2,25,33,19,84);
$nums = count($data);
dump( $data );
ShellSort($data,$nums);
dump( $data );
function ShellSort(& $arr,$n )
{
for( $increment = intval($n/2); $increment > 0; $increment = intval($increment/2) )
{
for( $i=$increment; $i<$n; $i++ )
{
$tmp = $arr[$i];
for( $j = $i; $j>= $increment; $j -= $increment )
if( $tmp < $arr[ $j-$increment ] )
$arr[$j] = $arr[$j-$increment];
else
break;
$arr[$j] = $tmp;
}
}
}
function dump( $d )
{
echo '<pre>';print_r($d);echo '</pre>';
}
빠른 정렬 (quicksort) — O(n log n)
$data = array(6,13,21,99,18,2,25,33,19,84);
dump($data);
quicks($data,0,count($data)-1);
dump($data);
function dump( $data){
echo '<pre>';print_r($data);echo '</pre>';
}
function QuickSort(& $arr,$left,$right)
{
$l = $left;
$r = $right;
$pivot = intval(($r)+$l)/2);
$p = $arr[$pivot];
do
{
while(($arr[$l] < $p) && ($l < $right))
$l++;
while(($arr[$r] > $p) && ($r > $left))
$r--;
if($l <= $r)
{
$temp = $arr[$l];
$arr[$l] = $arr[$r];
$arr[$r] = $temp;
$l++;
$r--;
}
}
while($l <= $r);
if($left < $r)
QuickSort(&$arr,$left,$r);
if($l < $right)
QuickSort(&$arr,$l,$right);
}
=================================================
버블 정렬: 숫자를 두두로 교환하여, 가장 작은 값이 왼쪽에 있어, 가장 가벼운 백파가 가장 위쪽에 있듯이. 전체 숫자列을 두두로 교환하면, 가장 작은 숫자가 왼쪽에 있고, 매번 나머지 숫자 중에서 가장 작은 숫자를 얻습니다. "백파"로 나오는 숫자들은 정렬된 区间을 형성하고, 나머지 값들은 무질서 区间을 형성하며, 정렬된 区간의 각 요소 값은 무질서 区간의 요소 값보다 작습니다.
퀵 정렬: 기준 값, 왼쪽과 오른쪽 두 개의 배열, 재귀 호출, 병합.
삽입 정렬: 정렬区间을 두 부분으로 나누어, 왼쪽이 정렬되고 오른쪽이 정렬되지 않습니다. 오른쪽区间에서 첫 번째 요소를 왼쪽区间에 삽입합니다. 이 요소가 왼쪽区间의 가장 오른쪽 요소보다 크면 그대로 두고, 이 요소가 왼쪽区间의 가장 오른쪽 요소보다 작으면 그 원래 위치에 삽입하고, 가장 오른쪽 요소를 한 칸 오른쪽으로 이동시키고, 계산기를 하나 줄입니다. 그런 다음, 이전 요소와 다시 비교하여, 이전 요소가 삽입할 요소보다 작을 때까지 반복합니다. 이 과정을 반복하여, 삽입할 요소보다 작은 요소들이 모두 왼쪽으로 이동합니다.
区间의 끝점 값의 처리와 배열의 첫 번째 요소 인덱스가 0인 것을 주의하세요.
<?php
//PHP의 일반 정렬 알고리즘
function bubblesort ($array)
{
$n = count ($array);
for ($i = 0; $i < $n; $i++)
{
for ($j = $n - 2; $j >= $i; $j--) //[0,i-1] [i,$n-1]
{
if ($array[$j] > $array[$j + 1]);
{
$temp = $array[$j];
$array[$j] = $array[$j + 1];
$array [$j + 1] = $temp;
}
}
}
return $array;
}
$array = array (3,6,1,5,9,0,4,6,11);
print_r (bubblesort ($array));
echo '<hr>';
function quicksort ($array)
{
$n = count ($array);
if ($n <= 1)
{
return $array;
}
$key = $array['0'];
$array_r = array();
$array_l = array ();
for ($i = 1; $i < $n; $i++)
{
if ($array[$i] > $key)
{
$array_r[] = $array[$i];
}
else
{
$array_l[] = $array[$i];
}
}
$array_r = quicksort ($array_r);
$array_l = quicksort ($array_l);
$array = array_merge ($array_l, array($key), $array_r);
return $array;
}
print_r (quicksort ($array));
echo '<hr>';
function insertsort ($array)
{
$n = count ($array);
for ($i = 1; $i < $n; $i++) //[0,i-1] [i,n]
{
$j = $i - 1;
$temp = $array[$i];
while ($array[$j] > $temp)
{
$array[$j + 1] = $array[$j];
$array[$j] = $temp;
$j--;
}
}
return $array;
}
print_r (insertsort ($array));
?>
=======================================
<?php
/*
【삽입 정렬（일维 배열）】
【기본 개념】：매趟 하나의 정렬되지 않은 데이터 요소를 선택하여 이미 정렬된 시퀀스의 적절한 위치에 삽입하여 시퀀스가 여전히 정렬된 상태를 유지하고, 모든 정렬되지 않은 데이터 요소가 삽입될 때까지 반복합니다.
【예시】：
[초기 키워드] [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;
}
/*
【선택 정렬（일维 배열）】
【기본 개념】：매趟 중간에 정렬된 데이터 요소에서 가장 작은(또는 가장 큰) 요소를 선택하여 이미 정렬된 시퀀스의 마지막에 순서대로 배치하고, 모든 정렬되지 않은 데이터 요소가 정렬될 때까지 반복합니다.
【예시】：
[초기 키워드] [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;
}
/*
【버블 정렬（일维 배열）】
【기본적인 생각】：정렬되지 않은 데이터 요소를 두끼리 비교하여, 두 데이터 요소의 순서가 반대로 되어 있으면 교환하여, 더 이상 반대 순서의 데이터 요소가 없을 때까지.
【정렬 과정】：정렬될 수 있는 배열 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 65
27 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;
}
/*
【퀵 정렬（일维 배열）】
【기본적인 생각】：현재 비정렬 区 R[1..H]에서 데이터 요소를 선택하여 비교의 "기준"(X라고 부를 수 있습니다)으로 사용합니다,
이 기준을 사용하여 현재 비정렬 区를 왼쪽과 오른쪽으로 두 개의 더 작은 비정렬 区로 나눕니다: R[1..I-1] 와 R[I 1..H]，이리고 왼쪽 비정렬 서브 区의 데이터 요소는 모두 기준 요소보다 작거나 같습니다.
오른쪽 비정렬 서브 区의 데이터 요소는 모두 기준 요소보다 크거나 같으며, 기준 X는 최종 정렬 위치에 있으며, 즉 R[1..I-1]≤X.Key≤R[I 1..H](1≤I≤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］76 97
최종 정렬 결과 13 27 38 49 49 65 76 97
각 턴 정렬 후 상태
*/
function quick_sort($array){
if (count($array) <= 1) return $array;
$key = $array[0];
$left_arr = array();
$right_arr = array();
for ($i=1; $i<count($array); $i++{
if ($array[$i] <= $key)
$left_arr[] = $array[$i];
else
$right_arr[] = $array[$i];
}
$left_arr = quick_sort($left_arr);
$right_arr = quick_sort($right_arr);
return array_merge($left_arr, array($key), $right_arr);
}
/*배열 전체 내용 출력*/
function display_arr($array){
$len = count($array);
for($i = 0; $i<$len; $i++{
echo $array[$i].' ';
}
echo '<br />';
}
/*
수种 정렬 알고리즘의 비교 및 선택
1정렬 방법 선택을 위해 고려해야 할 요인:
(1정렬할 요소 수 n;
(2요소 자체 정보량의 크기;
(3키워드의 구조 및 분포 상태;
(4언어 도구의 조건, 보조 공간의 크기 등을 고려해야 합니다.
2결론:
(1n이 작으면 (n <= 50)이면, 직접 삽입 정렬이나 직접 선택 정렬을 사용할 수 있습니다. 직접 삽입 정렬은 직접 선택 정렬보다 더 많은 레코드 이동 작업이 필요하기 때문에, 레코드 자체 정보량이 큰 경우 직접 선택 정렬을 사용하는 것이 더 좋습니다.
(2파일의 초기 상태가 키워드로 기본적으로 정렬되어 있으면, 직접 삽입 정렬이나 부포 정렬을 사용하는 것이 좋습니다.
(3n이 크면, O(nlogn)의 시간 복잡도를 가진 방법을 사용해야 합니다.2n)의 정렬 방법: 퀵 정렬, 힙 정렬 또는 병합 정렬. 퀵 정렬은 비교 기반 내부 정렬 알고리즘 중 가장 좋은 방법으로 여겨집니다.
(4비교 정렬 방법을 기반으로, 두 키워드의 크기를 비교한 후에는 두 가지 가능한 이동만 발생하기 때문에, 비교 판정 과정을 트리로 설명할 수 있습니다. 따라서 다음과 같이 증명할 수 있습니다: 파일의 n 개의 키워드가 무작위로 분포되어 있을 때, "비교"를 기반으로 한 어떤 정렬 알고리즘도 최소한 O(nlogn)의 정렬 방법을 필요로 합니다: 퀵 정렬, 힙 정렬 또는 병합 정렬.2n) 시간.
(5) 기록 자체의 정보량이 크면, 기록을 이동하는 데 많은 시간을 소비하지 않기 위해 링크드 리스트를 저장 구조로 사용할 수 있습니다。
*/
/*정렬 테스트*/
$a = array('12','4','16','8','13','20','5','32);
echo '삽입 정렬의 결과:';
$insert_a = insert_sort($a);
display_arr($insert_a);
echo '선택 정렬의 결과:';
$select_a = select_sort($a);
display_arr($select_a);
echo '버블 정렬의 결과:';
$bubble_a = bubble_sort($a);
display_arr($bubble_a);
echo '버블 정렬의 결과:';
$quick_a = quick_sort($a);
display_arr($quick_a);
?>
/**
* 정렬 조합
* 이진 방법을 사용하여 조합을 선택하면, 예를 들어5선택3이면, 단순히3위치1그래서 가능한 조합은 01101 11100 00111 10011 01110등10조합
*
* @param 정렬할 배열 $arr
* @param 최소 개수 $min_size
* @return 새로운 조건을 만족하는 배열 조합
*/
function pl($arr,$size=5) {
$len = count($arr);
$max = pow(2, $len);
$min = pow(2, $size)-1;
$r_arr = array();
for ($i=$min; $i<$max; $i++{
$count = 0;
$t_arr = array();
for ($j=0; $j<$len; $j++{
$a = pow(2, $j);
$t = $i&$a;
if($t == $a){
$t_arr[] = $arr[$j];
$count++;
}
}
if($count == $size){
$r_arr[] = $t_arr;
}
}
return $r_arr;
}
$pl = pl(array(1,2,3,4,5,6,7,5);
var_dump($pl);
//재귀 알고리즘
//팩토리얼
function f($n){
if($n == 1 || $n == 0){
return 1;
}else{
return $n*f($n-1);
}
}
echo f(5);
//디렉토리 탐색
function iteral($path){
$filearr = array();
foreach (glob($path.'\"*}) as $file){
if(is_dir($file)){
$filearr = array_merge($filearr, iteral($file));
}else{
$filearr[] = $file;
}
}
return $filearr;
}
var_dump(iteral('d:\www\test'));
PHP와 관련된 더 많은 내용에 대해 관심이 있는 독자는 다음 사이트의 특辑을 확인할 수 있습니다: 《PHP 데이터 구조와 알고리즘 교본》、《php 프로그램 설계 알고리즘 요약》、《php 암호화 방법 요약》、《PHP编码 및 변환 작업 기술 요약》、《php 객체 지향 프로그래밍 입문 교본》、《PHP 수학 연산 기술 요약》、《PHP 배열(Array) 작업 기술大全》、《php 문자열(string) 사용 요약》、《php 정규 표현식 사용 요약》 및 《php 일반 데이터베이스 작업 기술 요약》
이 문서에서 설명된 내용이 여러분의 PHP 프로그램 설계에 도움이 되길 바랍니다.
선언: 이 문서의 내용은 인터넷에서 가져왔으며, 저작권자에게 소유됩니다. 내용은 인터넷 사용자가 자발적으로 기여하고 업로드한 것이며, 이 사이트는 소유권을 가지지 않으며, 인공 편집 처리를 하지 않았으며, 관련 법적 책임을 부담하지 않습니다. 저작권 침해 내용을 발견하셨다면, notice#w로 이메일을 보내 주세요.3codebox.com（이메일을 보내는 경우, #을 @으로 변경하십시오. 신고하고 관련 증거를 제공하시면, 사이트는 즉시 저작권 침해 내용을 삭제합니다.