이 글에서는 주로 특정 참고값을 갖는 Java 단순 선택 정렬 예제를 자세히 소개합니다. 관심 있는 친구는 참고하세요.
1. 기본 개념
각 패스에서 정렬할 레코드 중에서 선택 가장 작은 레코드 키는 선택되어 모든 정렬이 완료될 때까지 정렬된 레코드 순서의 끝에 배치됩니다.
2. 구현 아이디어
정렬할 시퀀스에서 가장 작은 키워드가 있는 요소를 찾습니다.
가장 작은 요소가 정렬할 시퀀스의 첫 번째 요소가 아닌 경우
에서; 나머지 N - 1개의 요소 중 가장 작은 키워드를 가진 요소를 찾아 정렬이 완료될 때까지 (1)과 (2) 단계를 반복합니다.
3. 코드 구현
public class SelectionSort { public static void selectionSort(int[] list){ //需要遍历获得最小值的次数 if (1>=list.length)return; for (int i=0;i<list.length-1;i++){ int temp=0; int index=i; //选择当前值为最小值索引 for (int j=i+1;j<list.length;j++){ if (list[index]>list[j]){ index=j; //修改最小值索引 } } temp=list[index]; list[index]=list[i]; list[i]=temp; } } public static void main(String[] args){ int[] list={4,3,6,5,7,8,2,10,2,9}; selectionSort(list); for (int num:list){ System.out.print(num+" "); } } }
4. 시간 복잡도
단순 선택 정렬의 비교 횟수는 시퀀스의 초기 정렬과 관련이 없습니다. 정렬할 시퀀스에 N개의 요소가 있다고 가정하면 비교 횟수는 항상 N(N - 1) / 2입니다.
이동 횟수는 시퀀스의 초기 순서와 관련이 있습니다. 순서가 양수이면 이동 횟수가 가장 적어 0이 됩니다.
순서가 역순이면 이동 횟수가 가장 많아 3N(N - 1) / 2입니다.
위를 기준으로 하면 단순 정렬의 시간복잡도는 O(N2)입니다.
위 내용은 Java의 선택 정렬에 대한 코드 예제의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!