데이터 구조 정렬 시리즈 상세 한 6 트 리 선택 정렬

이 블 로 그 는 이어서 클래스 정렬 중 하 나 를 선택 하 는 정렬: 트 리 선택 정렬
간단 한 정렬 선택 에서 매번 의 비 교 는 지난번 에 비교 한 결 과 를 사용 하지 않 았 기 때문에 비교 작업 의 시간 복잡 도 는 O (N ^ 2) 이 고 비교 횟수 를 낮 추 려 면 비교 과정 에서 의 크기 관 계 를 저장 해 야 합 니 다.트 리 선택 정렬 은 간단 한 선택 정렬 에 대한 개선 입 니 다.
트 리 선택 정렬: 선수 권 대회 정렬 (Tournament Sort) 이 라 고도 부 르 며 선수 권 대회 의 사상 에 따라 정렬 하 는 방법 입 니 다.먼저 n 개의 기록 키 워드 를 두 가지 비교 한 다음 에 n / 2 개의 작은 자 사이 에서 두 가지 비 교 를 한 다음 에 이렇게 반복 하여 가장 작은 기록 을 선택 할 때 까지 한다.
알고리즘 구현 코드 는 다음 과 같 습 니 다.

package exp_sort;

public class TreeSelectSort {

	public static int[] TreeSelectionSort(int[] mData) {
		int TreeLong = mData.length * 4;
		int MinValue = -10000;
		int[] tree = new int[TreeLong]; //     
		int baseSize;
		int i;
		int n = mData.length;
		int max;
		int maxIndex;
		int treeSize;
		baseSize = 1;
		
		while (baseSize < n) {
			baseSize *= 2;
		}
		treeSize = baseSize * 2 - 1;
		
		for (i = 0; i < n; i++) {
			tree[treeSize - i] = mData[i];
		}
		for (; i < baseSize; i++) {
			tree[treeSize - i] = MinValue;
		}
		//      
		for (i = treeSize; i > 1; i -= 2) {
			tree[i / 2] = (tree[i] > tree[i - 1] ? tree[i] : tree[i - 1]);
		}
		n -= 1;
		while (n != -1) {
			max = tree[1];
			mData[n--] = max;
			maxIndex = treeSize;
			while (tree[maxIndex] != max) {
				maxIndex--;
			}
			tree[maxIndex] = MinValue;
			while (maxIndex > 1) {
				if (maxIndex % 2 == 0) {
					tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex + 1] ? tree[maxIndex]
							: tree[maxIndex + 1]);
				} else {
					tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex - 1] ? tree[maxIndex]
							: tree[maxIndex - 1]);
				}
				maxIndex /= 2;
			}
		}
		return mData;
	}

	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
		TreeSelectionSort(array);
		
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + " ");
		}
		System.out.println("
");
	}

}

알고리즘 분석:
트 리 선택 정렬 에서 가장 작은 키 워드 를 제외 하고 선택 한 가장 작은 키 워드 는 모두 잎 결점 에서 노드 와 비교 하 는 과정 을 걸 었 습 니 다. n 개의 잎 결점 을 포함 한 완전 이 진 트 리 의 깊이 log2n + 1 이기 때문에 트 리 선택 정렬 에서 작은 키 워드 를 선택 할 때마다 log2n 회 를 비교 해 야 하기 때문에 그 시간 복잡 도 는 O (nlog2n) 입 니 다.이동 기록 횟수 가 비교 횟수 를 초과 하지 않 기 때문에 전체적인 알고리즘 시간 복잡 도 는 O (nlog2n) 로 정렬 알고리즘 을 간단하게 선택 하 는 것 에 비해 비교 횟수 의 수량 급 을 낮 추고 n - 1 개의 추가 저장 공간 저장 중간 비교 결 과 를 증가 시 켰 다.
다음 절 에서 우 리 는 트 리 선택 과 정렬 을 개선 하 는 또 다른 정렬 방법 인 쌓 기 정렬 을 말 합 니 다.