이 글에서는 주로 PHP 정렬 알고리즘인 Simple Selection Sort를 소개합니다. Simple Selection Sort 알고리즘의 원리와 관련 구현 기법을 예제 형식으로 자세히 분석합니다. 도움이 필요한 친구들이 참고할 수 있습니다.
이 글의 예제는 PHP 정렬 알고리즘인 Simple Selection Sort를 배웠습니다. 다음과 같이 참고할 수 있도록 모두와 공유하세요.
기본 아이디어:
n - i 키워드 간 비교를 통해 n - i + 1 레코드 중에서 가장 작은 키워드가 있는 레코드를 선택하고 i와 교환합니다. -th (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);
실행 결과:
array(9) { [0]=> int(1) [1]=> int(2) [2]=> int(3) [3]=> int(4) [4]=> int(5) [5]=> int(6) [6]=> int(7) [7]=> int(8) [8]=> int(9) }
복잡성 분석:
선택 정렬 프로세스, 필요한 이동 기록 횟수를 비교하십시오. 가장 좋은 경우는 정렬할 레코드의 초기 상태가 이미 양의 순서이므로 레코드를 이동할 필요가 없다는 것입니다.
최악의 경우, 즉 정렬해야 할 레코드의 초기 상태는 첫 번째 레코드가 가장 큰 레코드이고 다음 레코드를 작은 것부터 큰 것 순으로 정렬한 다음 이동해야 할 레코드 수만큼 정렬하는 것입니다. 최대 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 데이터 구조"를 참조했습니다. 나중에 참고할 수 있도록 여기에만 기록했습니다.
관련 추천:
위 내용은 PHP 정렬 알고리즘 Simple Selection Sort (Simple Selection Sort)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!