PHP에서 네 가지 기본 정렬 알고리즘의 코드 구현

많은 사람들은 알고리즘이 프로그램의 핵심이고, 알고리즘의 품질이 프로그램의 품질을 결정한다고 말합니다. 주니어 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;
 }
 }
 }
 return $arr;
}

2. 정렬을 선택하세요

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

function selectSort($arr) {
//이중 루프가 완료되고 외부 레이어는 라운드 수를 제어하고 내부 레이어는 비교 수를 제어합니다.
$len=count( $arr);
for($i=0; $i<$len-1; $i ) {
//최소값의 위치를 ​​먼저 가정
 $p = $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;
}

3. 삽입 정렬

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

함수 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]) {
//삽입된 요소가 더 작은 것으로 확인되면 위치를 바꾸고 다음 요소를 이전 요소와 교환
 $arr[$j 1] = $arr[$j];
$arr[$j] = $tmp;
} else {
//필요하지 않은 요소를 발견한 경우 정렬이 완료된 배열이라면 이전 배열을 다시 비교할 필요가 없습니다.
break;
}
}
}
return $arr;
}

4. 퀵 정렬

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

functionquickSort($arr) {
//먼저 계속해야 하는지 여부를 결정합니다.
$length = count($arr);
if ( $length <= 1) {
return $arr;
}
//첫 번째 요소를 기본으로 선택
$base_num = $arr[0];
//Traverse Except 눈금자 외부의 모든 요소는 크기 관계에 따라 두 개의 배열로 배치됩니다.
//두 개의 배열 초기화
$left_array = array() //기준보다 작은 것
$right_array = array() ; / / 밑수보다 큼
for($i=1; $i<$length; $i ) {
if($base_num > $arr[$i]) {
//Put 왼쪽 배열에 넣습니다
$left_array[] = $arr[$i];
} else {
//오른쪽에 넣습니다
$right_array[] = $arr[$i] ;
}
}
//그런 다음 왼쪽 및 오른쪽 배열에 동일한 정렬을 수행하고 이 함수를 재귀적으로 호출합니다.
$left_array =quick_sort($left_array);
$right_array =quick_sort( $right_array);
//Merge
return array_merge($left_array, array($base_num), $right_array);
}

원천: php100

4가지 유형, PHP