PHP 단순 선택 정렬 알고리즘 example_php 기술

간단한 선택정렬 알고리즘 : 키워드간 n-i 비교를 통해 n-i개의 레코드 중 가장 작은 키워드를 갖는 레코드를 선택하여 i번째(1<=i<=n) 레코드와 교환

코드 복사 코드는 다음과 같습니다.

클래스 정렬{
         /**
* 간단한 선택 정렬
           *                                 * @param 알 수 없는_유형 $arr
                     */
           공개 함수 selectSort(&$arr) {
               $len=count($arr);
                for ($i=0;$i<$len;$i) {
                   $min=$i;
($j=$i 1;$j<=$len-1;$j) {
If ($arr[$min]>$arr[$j]) {//$arr[$min]보다 작은 값이 발견되면 $min
에 아래 첨자를 할당합니다.                            $min=$j;
                 }
                }
If ($min!=$i){//$min이 $i와 같지 않으면 최소값을 찾았음을 의미하며 교환
$this->swap($arr[$i],$arr[$min]);
                }
            }
}
         /**
* 두 값 ​​​​$a 및 $b의 위치를 ​​바꿉니다
                     */
          공개 함수 교환(&$a,&$b) {
               $temp=$a;
               $a=$b;
               $b=$temp;
}
}
$arr=배열(4,6,1,2,9,8,7,3,5);
$test=new 정렬()
$test->selectSort($arr);//간단한 선택 정렬
// var_dump($arr);
?>

간단한 선택 정렬의 특징: 모바일 데이터 교환 횟수가 매우 적으므로 해당 시간이 절약됩니다

단순 선택 정렬의 시간 복잡도 분석:
최선의 경우나 최악의 경우에 관계없이 i번째 정렬에는 n-i 키워드 비교가 필요하며 n(n-1)/2 비교가 필요합니다. 따라서 최종 시간 복잡도는 O(n^2)
버블 정렬과 마찬가지로 O(n^2)이지만 선택 정렬의 성능은 여전히 ​​버블 정렬보다 약간 더 좋습니다.

성명：

본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.