알고리즘 의 길2. 정렬 선택

해명 하 다
정렬 법 을 선택 하 는 것 은 사실상 포 지 셔 닝 비교 교환 법 (즉 거품 정렬 법) 에 대한 개선 이다.
기본 사상: 첫 번 째, 정렬 대기 기록 r [1] ~ r [n] 에서 가장 작은 기록 을 선택 하여 r [1] 와 교환 합 니 다.두 번 째, 정렬 대기 기록 r [2] ~ r [n] 에서 가장 작은 기록 을 선택 하여 r [2] 와 교환 합 니 다.이 를 통 해 i 번 째 는 정렬 대기 기록 r [i] ~ r [n] 에서 가장 작은 기록 을 선택 하여 r [i] 와 교환 하여 모든 정렬 이 끝 날 때 까지 질서 있 는 서열 을 계속 증가 시 킵 니 다.
상기 알고리즘 사상 에서 알 수 있 듯 이 정렬 을 선택 하 는 것 은 대기 기록 에서 가장 작은 것 을 왼쪽 에 두 는 것 이 고 위의 블 로그 에서 쓴 거품 은 대기 기록 에서 가장 큰 것 을 오른쪽 에 두 는 것 이다.
예시:
초기 시퀀스: {49 27 65 97 76 12 38} 첫 번 째: 12 와 49 교환: 12 {27 65 97 76 49 38} 두 번 째: 27 움 직 이지 않 음: 12 27 {65 97 76 49 38} 세 번 째: 65 와 38 교환: 12 27 38 {97 76 49 65} 네 번 째: 97 과 49 교환: 12 27 38 49 {76 97 65} 다섯 번 째: 76 과 65 교환: 12 27 38 49 65 {97 76 76 76}제6 회: 97 과 76 교환: 12 27 38 49 65 76 97 완성
코드
	public static void selectionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		//      
		for (int i = 0; i < arr.length - 1; i++) {
			//    minIndex                 
			int minIndex = i;
			//              
			// minIndex                  minIndex
			for (int j = i + 1; j < arr.length; j++) {
				minIndex = arr[j] < arr[minIndex] ? j : minIndex;
			}
			//                
        		int tmp = arr[i];
        		arr[i] = arr[minIndex];
        		arr[minIndex] = tmp;
		}
	}

좋은 웹페이지 즐겨찾기