한국어
한국어
간단한 선택 분류는 다양한 데이터를 효과적으로 처리 할 수있는 직관적이고 일반적으로 사용되는 정렬 알고리즘입니다. 핵심 아이디어는 매번 정렬 할 요소에서 최소값을 선택하고 정렬 된 시퀀스의 끝에 배치하는 것입니다. 특정 프로세스는 다음과 같습니다. 처음으로 전체 배열에서 가장 작은 요소를 선택하고 첫 번째 위치를 교환하고, 두 번째는 나머지 요소에서 가장 작은 값을 선택하고 두 번째 위치를 교환하는 등 모든 요소가 정렬 될 때까지옵니다.
먼저 배열 길이 n을 가져온 다음 N-1 라운드 선택 작업을 수행하십시오. 각 선택 라운드는 분류되지 않은 부분에서 최소값을 찾아 현재 라운드의 시작 위치에서 요소와 교환하여 로컬 순서를 달성하고 마지막으로 전체 분류를 완료합니다.
다음은 PHP 구현의 간단한 선택 분류를위한 샘플 코드로 알고리즘의 특정 실행 프로세스에 대한 이해를 촉진합니다.
function selectionSort(&$arr)
{
$len=count($arr);
for($i=0;$i<$len-1;$i++)
{
$min=$i; // 현재 요소가 최소 값 위치라고 가정합니다.
for($j=$i+1;$j<$len;$j++) // 후속 요소에서 작은 값을 찾으십시오
{
if($arr[$j]<$arr[$min])
{
$min=$j; // 최소 값 위치를 업데이트하십시오
}
}
if($min!=$i) // 위치가 변경 될 때 요소를 교환합니다
{
$temp=$arr[$min];
$arr[$min]=$arr[$i];
$arr[$i]=$temp;
}
}
}
간단한 선택 분류에는 N-1 선택이 필요하며 각 라운드는 나머지 요소들 사이에서 최소값을 찾으므로 비교 횟수는 N²/2에 대해서는 비교 수가 초기 데이터 순서에 따라 다릅니다. 총 시간 복잡성은 O (n²)입니다. 그럼에도 불구하고 데이터 볼륨이 작거나 기본적으로 주문되면 알고리즘은 여전히 실용적입니다.
이 알고리즘은 하나의 임시 변수를 사용하여 교환을 지원하고 매우 작은 공간 오버 헤드와 O (1)의 공간적 복잡성을 제공합니다.
간단한 선택 분류는 불안정한 정렬 알고리즘입니다. 동일한 요소가 분류 프로세스 중에 위치를 바꾸어 상대 순서를 변경할 수 있습니다. 예를 들어, 순서 5 8 5 2 9에서 첫 번째 교환 후 첫 번째 요소 5를 갖는 가장 작은 요소 2를, 동일한 위치 순서 5가 중단됩니다.
