PHP는 네 가지 기본 정렬 알고리즘을 구현합니다.-PHP 튜토리얼-php.cn

PHP는 네 가지 기본 정렬 알고리즘을 구현합니다.

WBOY

풀어 주다： 2016-07-25 08:44:20

원래의

905명이 탐색했습니다.

많은 사람들은 알고리즘이 프로그램의 핵심이고, 알고리즘의 품질이 프로그램의 품질을 결정한다고 말합니다. 주니어 PHPer로서 알고리즘에 대한 노출은 거의 없습니다. 그러나 기본 정렬 알고리즘은 프로그램 개발에 필수적인 도구입니다. 여기서는 버블 정렬, 삽입 정렬, 선택 정렬, 퀵 정렬의 4가지 기본 알고리즘을 소개하고 알고리즘의 아이디어를 분석합니다.

전제 : 버블 정렬, 퀵 정렬, 선택 정렬, 삽입 정렬을 이용하여 아래 배열의 값을 작은 것부터 큰 것 순으로 정렬합니다.
$arr(1,43,54,62,21,66,32,78,36,76,39)

1. 버블정렬

아이디어 분석: 정렬할 숫자 그룹에서 아직 정렬되지 않은 순서에 대해 인접한 두 숫자를 앞에서 뒤로 비교 조정하여 더 큰 숫자가 가라앉도록 하고, 그리고 작은 것들이 올라갑니다. 즉, 두 개의 인접한 숫자를 비교할 때 그 순서가 순서 요구 사항과 반대인 것으로 밝혀질 때마다 서로 교체됩니다.

코드 구현:

$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;
}
}
}
$arr 반환 ;
}

코드 복사

2. 정렬을 선택하세요

아이디어 분석: 정렬할 숫자 집합에서 가장 작은 숫자를 선택하여 첫 번째 위치의 숫자와 교환하세요. 그런 다음 남은 숫자 중에서 가장 작은 숫자를 찾아 두 번째 위치의 숫자와 교환하고, 두 번째 숫자가 마지막 숫자와 비교될 때까지 이 루프가 계속됩니다.

코드 구현:

function selectSort($arr) {
//이중 루프가 완료되고 외부 레이어가 라운드 수, 내부 레이어 레이어 제어 비교 수
$len=count($arr);
for($i=0; $i / /가장 작은 값의 위치를 먼저 가정
$p = $i;
for($j=$i 1; $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;
}

코드 복사

3. 삽입 정렬

아이디어 분석: 정렬할 숫자 집합에서 이전 숫자가 이미 순서대로 되어 있다고 가정하고 이제 이전에 정렬된 숫자에 n번째 숫자를 삽입해야 합니다. 도 순서대로 배열되어 있습니다. 모든 것이 정상화될 때까지 이 주기를 반복합니다.

코드 구현:

function insertSort($arr) {
$len=count($arr)
for; ($i=1, $i<$len; $i ) {
$tmp = $arr[$i];
//내부 루프 제어, 비교 및 삽입
for($j= $ i-1;$j>=0;$j--) {
if($tmp < $arr[$j]) {
//삽입된 요소가 더 작은 것으로 확인되면, position, 그리고 다음 요소는 이전 요소와 교체됩니다
$arr[$j 1] = $arr[$j];
$arr[$j] = $tmp;
} else {
/ /이동할 필요가 없는 요소를 만나면 정렬된 배열이므로 이전 요소를 다시 비교할 필요가 없습니다.
break;
}
}
}
return $arr;
}

코드 복사

4. 퀵 정렬

아이디어 분석: 벤치마크 요소를 선택합니다. 일반적으로 첫 번째 요소 또는 마지막 요소입니다. 한 번의 스캔을 통해 정렬할 열을 두 부분으로 나누어 한 부분은 기준 요소보다 작고, 다른 부분은 기준 요소보다 크거나 같습니다. 이때 기본 요소는 정렬 후 올바른 위치에 있으며, 두 개의 분할된 부분은 동일한 방식으로 재귀적으로 정렬됩니다.

코드 구현: