PHP 정렬 알고리즘 구현 요약
- php中世界最好的语言원래의
- 2018-05-16 13:44:421476검색
이번에는 PHP 정렬 알고리즘 구현에 대한 요약을 가져오겠습니다. PHP 정렬 알고리즘 구현에 대한 주의사항은 무엇인가요?
이 문서의 예에서는 PHP의 네 가지 정렬 알고리즘 구현 및 효율성 분석을 설명합니다. 참조를 위해 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.
PHP의 네 가지 기본 정렬 알고리즘은 버블 정렬, 삽입 정렬, 선택 정렬 및 빠른 정렬입니다.
다음은 제가 컴파일한 알고리즘 코드입니다.
1. 버블 정렬:
아이디어: 배열에서 여러 라운드의 버블링을 수행하고, 각 라운드에서 배열의 요소를 쌍으로 비교하고, 위치를 조정하고, 팝합니다. up 최대 숫자가 나옵니다.
//简单版：
function bubbleSort($arr)
{
$n = count($arr);
for($i=1;$i<$n;$i++) { //冒泡的轮数(最多$n-1轮)
for($j=0;$j<$n-1;$j++) { //每一轮冒泡(两两比较，大者后移)
if($arr[$j] > $arr[$j+1]) { //前者大于后者，交换位置
$tmp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $tmp;
}
}
}
return $arr;
}//改进版：
function bubbleSort($arr)
{
$n = count($arr);
for($i=1;$i<$n;$i++) { //冒泡的轮数(最多$n-1轮)
$flag = 0; //是否发生位置交换的标志
for($j=0;$j<$n-$i;$j++) { //每一轮冒泡(两两比较，大者后移)
if($arr[$j] > $arr[$j+1]) { //前者大于后者，交换位置
$tmp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $tmp;
$flag = 1;
}
}
if($flag == 0) { //没有发生位置交换，排序已完成
break;
}
}
return $arr;
}버블 정렬 알고리즘의 효율성을 높이기 위해 개선이 필요한 주요 영역은 다음과 같습니다.
(1) 버블 라운드 수 줄이기: 버블 정렬 라운드에서 위치 교환이 발생하지 않는 경우는 다음을 의미합니다. 배열이 정렬되었으면 루프를 즉시 종료해야 합니다.
(2) 각 라운드의 비교 횟수를 줄입니다. 정렬된 배열의 일부 요소를 더 이상 비교하지 않습니다.
2. 삽입 정렬:
아이디어: 배열 앞의 요소가 정렬되어 있다고 가정하고 배열 뒤의 요소를 탐색하고 정렬된 요소 대기열에서 적절한 위치를 찾아 삽입합니다. 그것에.
function insertSort($arr)
{
$n = count($arr);
for($i=1;$i<$n;$i++) { //从第二个元素开始插入
for($j=$i-1;$j>=0;$j--) { //与前面的数比较，找到插入的位置
if($arr[$j] > $arr[$j+1]) { //比前面的数小，交换位置
$tmp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $tmp;
} else { //大于或等于前面的数，表示已找到插入的位置
break;
}
}
}
return $arr;
}3. 선택 정렬:
아이디어: 여러 항목을 선택하고 매번 가장 큰 요소를 선택하여 지정된 위치에 배치합니다.
function selectSort($arr)
{
$n = count($arr);
for($i=$n-1;$i>0;$i--) { //选择排序的轮数($n-1轮)
$pos = $i; //假设最大元素的位置
for($j=0;$j<$i;$j++) { //每一轮：从未选择过的元素中选择最大的数
if($arr[$j] > $arr[$pos]) { //所在位置元素比目前最大元素大，标志其位置
$pos = $j;
}
}
if($pos != $i) { //将最大元素放入指定的位置
$tmp = $arr[$pos];
$arr[$pos] = $arr[$i];
$arr[$i] = $tmp;
}
}
return $arr;
}4. 빠른 정렬:
아이디어: 재귀 알고리즘. 먼저 배열의 첫 번째 요소를 기준으로 선택한 다음 그보다 작거나 같은 숫자와 그보다 큰 숫자를 각각 두 개의 배열에 넣고 두 배열에 대해 동일한 처리를 수행한 다음 마지막으로 두 배열을 첫 번째 요소와 병합합니다. .
function quickSort($arr)
{
$n = count($arr);
if($n 28271668e93981ced645b8dc0e449995 $cur) {
$largeArr[] = $arr[$i];
} else {
$smallArr[] = $arr[$i];
}
}
//分别对大数组和小数组进行相同的处理
$smallArr = quickSort($smallArr);
$largeArr = quickSort($largeArr);
//合并小数组、分类基数和大数组
return array_merge($smallArr,array($cur),$largeArr);
}
각 정렬 알고리즘의 시간 복잡도와 공간 복잡도:
| 정렬 알고리즘 | 최고 시간 분석 | 최악의 시간 분석 | 평균 시간 복잡도 | 안정성 | 공간 복잡성 정도 |
| 버블 정렬 | O(n) | O(n2) | O(n2) | Stable | O(1) |
| 삽입 정렬 | O(n) | O (n2) | O(n2) | Stable | O(1) |
| 선택 정렬 | O(n2) | O(n 2) | O(n2) | Stable | O(1) |
| 빠른 정렬 | O(nlog2n) | O(n2) | O(nlog2n ) | Unstable | O(log2n)~O(n) |
참고: 퀵 정렬은 배열이 고장 났을 때, 배열이 주문되었을 때 가장 효율적입니다. 효율성은 최악입니다. .
이 기사의 사례를 읽은 후 방법을 마스터했다고 생각합니다. 더 흥미로운 정보를 보려면 PHP 중국어 웹사이트의 다른 관련 기사를 주목하세요!
추천 자료:
PHP가 Curl을 사용하여 로그인을 시뮬레이션하고 데이터를 캡처하는 단계에 대한 자세한 설명
위 내용은 PHP 정렬 알고리즘 구현 요약의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!