>  기사  >  백엔드 개발  >  PHP의 기본 알고리즘은 무엇입니까?

PHP의 기본 알고리즘은 무엇입니까?

藏色散人
藏色散人원래의
2019-06-18 15:44:064595검색

많은 사람들이 알고리즘이 프로그램의 핵심이라고 말합니다. 프로그램이 좋은지 나쁜지를 결정하는 관건은 알고리즘의 품질입니다. 주니어 PHPer로서 알고리즘에 대한 노출은 거의 없습니다. 하지만 여전히 버블 정렬, 삽입 정렬, 선택 정렬, 퀵 정렬의 4가지 기본 알고리즘을 마스터해야 한다고 생각합니다.

PHP의 기본 알고리즘은 무엇입니까?

관련 추천: "PHP 튜토리얼"

요구 사항: 버블 정렬, 퀵 정렬, 선택 정렬, 삽입 정렬을 사용하여 아래 배열의 값을 오름차순으로 정렬하세요.

$arr=array(11,3,56,62,21,66,32,78,36,76,39,88,34);

1. 버블 정렬

소개:

버블 정렬(버블 정렬, 대만에서는 버블 정렬 또는 버블 정렬로 번역됨)은 간단한 정렬 알고리즘입니다. 정렬할 시퀀스를 반복적으로 살펴보고 두 요소를 차례로 비교하고 순서가 잘못된 경우 교체합니다. 더 이상 교환이 필요하지 않을 때까지 어레이 방문 작업이 반복됩니다. 이는 어레이가 정렬되었음을 의미합니다. 이 알고리즘의 이름은 작은 요소가 스와핑을 통해 배열의 맨 위로 천천히 "부동"된다는 사실에서 유래되었습니다.

단계:

1. 인접한 요소를 비교합니다. 첫 번째 것이 두 번째 것보다 크면 둘 다 교환하세요.

2. 처음의 첫 번째 쌍부터 끝의 마지막 쌍까지 인접한 요소의 각 쌍에 대해 동일한 작업을 수행합니다. 이때 마지막 요소가 가장 큰 숫자가 되어야 합니다.

3. 마지막 요소를 제외한 모든 요소에 대해 위 단계를 반복합니다.

4. 비교할 숫자 쌍이 없을 때까지 점점 더 적은 수의 요소에 대해 위 단계를 계속 반복합니다.

특정 코드:

$arr=array(1,43,54,62,21,66,32,78,36,76,39);
function bubbleSort ($arr)
{
$len = count($arr);
//该层循环控制 需要冒泡的轮数
for ($i=1; $i<$len; $i++) {
//该层循环用来控制每轮 冒出一个数 需要比较的次数
for ($k=0; $k<$len-$i; $k++) {
if($arr[$k] > $arr[$k+1]) {
$tmp = $arr[$k+1]; // 声明一个临时变量
$arr[$k+1] = $arr[$k];
$arr[$k] = $tmp;
}
}
}
return $arr;
}

정렬 효과:
PHP의 기본 알고리즘은 무엇입니까?

2. 선택 정렬

소개:

선택 정렬(Selection sort)은 간단하고 직관적인 정렬 알고리즘입니다. 작동 방식은 다음과 같습니다. 먼저 정렬되지 않은 시퀀스에서 가장 작은 요소를 찾아 정렬된 시퀀스의 시작 부분에 저장한 다음, 정렬되지 않은 나머지 요소에서 계속해서 가장 작은 요소를 찾아 정렬된 시퀀스의 끝에 넣습니다. 모든 요소가 정렬될 때까지 계속됩니다.

특정 코드:

//实现思路 双重循环完成,外层控制轮数,当前的最小值。内层 控制的比较次数
function select_sort($arr) {
//$i 当前最小值的位置, 需要参与比较的元素
for($i=0, $len=count($arr); $i<$len-1; $i++) {
//先假设最小的值的位置
$p = $i;
//$j 当前都需要和哪些元素比较,$i 后边的。
for($j=$i+1; $j<$len; $j++) {
//$arr[$p] 是 当前已知的最小值
if($arr[$p] > $arr[$j]) {
//比较,发现更小的,记录下最小值的位置;并且在下次比较时,应该采用已知的最小值进行比较。
$p = $j;
}
}
//已经确定了当前的最小值的位置,保存到$p中。
//如果发现 最小值的位置与当前假设的位置$i不同,则位置互换即可
if($p != $i) {
$tmp = $arr[$p];
$arr[$p] = $arr[$i];
$arr[$i] = $tmp;
}
}
//返回最终结果
return $arr;
}

정렬 효과:

PHP의 기본 알고리즘은 무엇입니까?

3. 삽입 정렬

소개:

삽입 정렬의 알고리즘 설명은 간단하고 직관적인 정렬 알고리즘입니다. 정렬되지 않은 데이터의 경우 정렬된 시퀀스의 뒤에서 앞으로 스캔하여 해당 위치를 찾아 삽입합니다. 삽입 정렬의 구현에서는 일반적으로 내부 정렬(즉, O(1) 추가 공간만 사용하는 정렬)이 사용되므로 스캔 과정에서 뒤에서 앞으로 반복적이고 점진적으로 이동해야 합니다. 요소를 뒤로 정렬하여 최신 요소에 대한 삽입 공간을 제공합니다.

단계:

1. 정렬된 것으로 간주할 수 있는 첫 번째 요소부터 시작하여

2. 다음 요소를 꺼내고 정렬된 요소 순서에서 뒤에서 앞으로 스캔합니다. (정렬된) 요소가 새 요소보다 크면 요소를 다음 위치로 이동합니다.


4. 정렬된 요소가 새 요소보다 작거나 같은 위치를 찾을 때까지 3단계를 반복합니다. 5. 새 요소를 해당 위치에 넣습니다. 중간

6. 2단계를 반복하세요.


특정 코드:

function insert_sort($arr)
{
$len=count($arr);
for($i=1; $i<$len; $i++) {
//获得当前需要比较的元素值。
$tmp = $arr[$i];
//内层循环控制 比较 并 插入
for($j=$i-1; $j>=0; $j--) {
//$arr[$i];//需要插入的元素; $arr[$j];//需要比较的元素
if($tmp < $arr[$j]) {
//发现插入的元素要小,交换位置
//将后边的元素与前面的元素互换
$arr[$j+1] = $arr[$j];
//将前面的数设置为 当前需要交换的数
$arr[$j] = $tmp;
} else {
//如果碰到不需要移动的元素
//由于是已经排序好是数组,则前面的就不需要再次比较了。
break;
}
}
}
//将这个元素 插入到已经排序好的序列内。
//返回
return $arr;
}

정렬 효과:


4.빠른 정렬PHP의 기본 알고리즘은 무엇입니까?

소개: 빠른 정렬은 Tony Hall이 개발한 방법입니다. 정렬 알고리즘. 평균적으로 n개 항목을 정렬하려면 O(n log n) 비교가 필요합니다. 최악의 경우에는 O(n2) 비교가 필요하지만 이런 상황은 흔하지 않습니다. 실제로 퀵 정렬은 내부 루프가 대부분의 아키텍처에서 효율적으로 구현될 수 있고 대부분의 실제 응용 프로그램에서 잘 작동하기 때문에 다른 Ο(n log n) 알고리즘보다 훨씬 빠른 경우가 많습니다. 데이터가 설계 선택을 결정하여 2차 항의 가능성을 줄입니다. 필요한 시간에.

단계:

1. 시퀀스에서 "피벗"이라는 요소를 선택합니다.

2. 시퀀스의 순서를 변경합니다. 피벗 값보다 작은 모든 요소는 피벗 값 앞에 배치되고 그보다 작은 모든 요소는 피벗 값은 피벗 앞에 배치됩니다. 베이스 값이 더 큰 값이 베이스 뒤에 배치됩니다(같은 숫자가 양쪽에 있을 수 있음). 이 파티션이 종료된 후 베이스는 시퀀스의 중간에 있습니다. 이를 파티션 작업이라고 합니다.


3. 기준 값보다 작은 요소의 하위 배열과 기준 값보다 큰 요소의 하위 배열을 재귀적으로 정렬합니다.


특정 코드:

function quick_sort($arr)
{
//判断参数是否是一个数组
if(!is_array($arr)) return false;
//递归出口:数组长度为1,直接返回数组
$length = count($arr);
if($length<=1) return $arr;
//数组元素有多个,则定义两个空数组
$left = $right = array();
//使用for循环进行遍历,把第一个元素当做比较的对象
for($i=1; $i<$length; $i++)
{
//判断当前元素的大小
if($arr[$i]<$arr[0]){
$left[]=$arr[$i];
}else{
$right[]=$arr[$i];
}
}
//递归调用
$left=quick_sort($left);
$right=quick_sort($right);
//将所有的结果合并
return array_merge($left,array($arr[0]),$right);
}

정렬 효과:

위 내용은 PHP의 기본 알고리즘은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.