PHP 단순 선택 정렬 알고리즘 학습

이 글에서는 주로 PHP Simple Selection Sort 알고리즘에 대해 자세히 소개하고 있으며, 관심 있는 친구들은 이를 참고할 수 있습니다.

이 글의 예제는 PHP Simple Selection Sort의 구체적인 내용을 공유합니다. 참고로 구체적인 내용은 다음과 같습니다

기본 아이디어:

n - i 키워드 간 비교를 통해 n - i + 1 레코드 중 가장 작은 키워드가 있는 레코드를 선택하고 i번째(1)와 결합합니다.

알고리즘 구현:

<?php

//简单选择排序

//交换函数
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//简单选择排序算法
function SelectSort(array &$arr){
  $count = count($arr);
  for($i = 0;$i < $count - 1;$i ++){
    //记录第$i个元素后的所有元素最小值下标
    $min = $i;
    for($j = $i + 1;$j < $count;$j ++){
      if($arr[$j] < $arr[$min]){
        $min = $j;
      }
    }

    if($min != $i){
      swap($arr,$min,$i);
    }
  }
}
$arr = array(9,1,5,8,3,7,4,6,2);
SelectSort($arr);
var_dump($arr);

복잡도 분석:

간단한 선택 정렬 과정에서 이동해야 하는 레코드 수가 상대적으로 적습니다. 가장 좋은 경우는 정렬할 레코드의 초기 상태가 이미 양의 순서이므로 레코드를 이동할 필요가 없다는 것입니다.

최악의 경우, 즉 정렬할 레코드의 초기 상태는 첫 번째 레코드가 가장 크고, 그 다음 레코드가 오름차순으로 정렬되어 있어 이동해야 하는 레코드의 개수는 최대 3개입니다. (n-1). 단순 선택 정렬 시 필요한 비교 횟수는 초기 상태에서 정렬할 레코드 순서의 배열과 관계가 없습니다. i=1이면 n-1 비교가 필요하고, i=2이면 n-2 비교가 필요합니다. 필요한 총 비교 수는 (n-1)+(n-2)+입니다. +2+1=n(n-1)/2, 즉 비교연산의 시간복잡도는 O(n^2)이고, 이동연산의 시간복잡도는 O(n)이다.

단순 선택 정렬은 불안정한 정렬입니다.

이 블로그는 "Dahua 데이터 구조"를 참조했습니다. 나중에 참고할 목적으로만 여기에 기록되었습니다.

위 내용은 이 글의 전체 내용입니다. 여러분의 학습에 도움이 되기를 바랍니다.

관심을 가질 만한 기사:

WeChat 점프 PHP 코드 구현에 대한 자세한 설명

WeChat의 Moments 공유 PHP 구현 설명 및 공유 기능 수 기록

PHP 구문 분석 xml 형식 데이터 도구 설명 예시

위 내용은 PHP 단순 선택 정렬 알고리즘 학습의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!