PHP의 4가지 정렬 알고리즘 [버블정렬, 삽입정렬, 선택정렬, 퀵정렬] 구현 및 효율성 분석

이 글에서는 주로 PHP의 4가지 정렬 알고리즘의 구현 및 효율성 분석을 소개하며, 특정 예제를 통해 PHP 버블 정렬, 삽입 정렬, 선택 정렬 및 퀵 정렬의 구체적인 정의, 사용법 및 알고리즘 복잡성 분석을 분석합니다. 가치, 도움이 필요한 친구들이 참고할 수 있습니다

이 기사에서는 PHP에서 4가지 정렬 알고리즘의 구현 및 효율성 분석에 대해 설명합니다. 참고를 위해 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

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 <= 1) { //若数组只有一个元素，直接返回
     return $arr;
   }
   $largeArr = array(); //存放大数
  $smallArr = array(); //存放小数
   $cur = $arr[0];  //分类基数
   for($i=1;$i<$n;$i++) { //遍历数组元素，对每个元素进行归类
     if($arr[$i] > $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)
삽입 정렬	오 (n)	O(n2)	O(n2)	Stable	O(1)
선택 정렬	O(n2 )	O(n) 2)	O(n2)	Stable	O(1)
빠른 정렬	O(nlog2n)	O(n 2)	오 (nlog2n)	Unstable	O(log2n)~O(n)

참고: 빠른 정렬은 배열의 순서가 잘못되었을 때 가장 효율적입니다. 배열이 정렬될 때 최악입니다.

위 내용은 PHP의 4가지 정렬 알고리즘 [버블정렬, 삽입정렬, 선택정렬, 퀵정렬] 구현 및 효율성 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!