집 > 기사 > 백엔드 개발 > PHP 정렬 알고리즘 구현 요약

PHP 정렬 알고리즘 구현 요약

php中世界最好的语言원래의: 2018-05-16 13:44:421427검색

이번에는 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(n²)	O(n²)	Stable	O(1)
삽입 정렬	O(n)	O (n²)	O(n²)	Stable	O(1)
선택 정렬	O(n²)	O(n ²)	O(n²)	Stable	O(1)
빠른 정렬	O(nlog₂n)	O(n²)	O(nlog₂n )	Unstable	O(log₂n)~O(n)

참고: 퀵 정렬은 배열이 고장 났을 때, 배열이 주문되었을 때 가장 효율적입니다. 효율성은 최악입니다. .

이 기사의 사례를 읽은 후 방법을 마스터했다고 생각합니다. 더 흥미로운 정보를 보려면 PHP 중국어 웹사이트의 다른 관련 기사를 주목하세요!