더미 정렬 (히트 정렬)

글 목록

알고리즘 설명

움 직 이 는 그림 시연

코드 구현

알고리즘 분석

쌓 기 정렬 (Heapsort) 은 쌓 기 라 는 데이터 구 조 를 이용 하여 디자인 한 정렬 알고리즘 을 말한다.퇴적 은 완전 이 진 트 리 와 비슷 한 구조 이 며, 동시에 퇴적 의 성질 을 만족 시 킵 니 다. 즉, 하위 노드 의 키 나 색인 은 항상 부모 노드 보다 작 습 니 다.
알고리즘 설명

초기 정렬 대기 키워드 시퀀스 (R1, R2... Rn) 를 큰 꼭대기 로 구축 합 니 다. 이 더 미 는 초기 무질서 구역 입 니 다.

쌓 인 요소 R [1] 을 마지막 요소 R [n] 과 교환 합 니 다. 이때 새로운 무질서 구역 (R1, R2,... Rn - 1) 과 새로운 질서 구역 (Rn) 을 얻 고 R [1, 2... n - 1] < = R [n] 을 만족 시 킵 니 다.

교환 후 새로운 더미 R [1] 은 더미 의 성질 을 위반 할 수 있 기 때문에 현재 무질서 구역 (R1, R2,... Rn - 1) 을 새로운 더미 로 조정 한 다음 에 R [1] 을 무질서 구역 의 마지막 요소 와 교환 하여 새로운 무질서 구역 (R1, R2... Rn - 2) 과 새로운 질서 구역 (Rn - 1, Rn) 을 얻 을 수 있 습 니 다.질서 있 는 구역 의 요소 개수 가 n - 1 일 때 까지 이 과정 을 계속 반복 하면 전체 정렬 과정 이 완 료 됩 니 다.

데모
코드 구현
아래 의 정렬 알고리즘 을 통일 적 으로 사용 하 는 테스트 코드 는 다음 과 같 습 니 다. 소스 GitHub 링크 입 니 다.

public static void main(String[] args) {
    int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
	//                 
    heapSort(array);

    System.out.println(Arrays.toString(array));
}

주의: 여기 완전 이 진 트 리 의 일부 성질 을 사 용 했 습 니 다.

/**
 * Description:    
 *
 * @param array
 * @return void
 * @author JourWon
 * @date 2019/7/11 23:40
 */
public static void heapSort(int[] array) {
	if (array == null || array.length <= 1) {
		return;
	}

	int length = array.length;

	//1.     
	for (int i = length / 2 - 1; i >= 0; i--) {
		//             ，        
		adjustHeap(array, i, length);
	}
	//2.     +           
	for (int j = length - 1; j > 0; j--) {
		//              
		swap(array, 0, j);
		//        
		adjustHeap(array, 0, j);
	}

}

/**
 * Description:      （      ，             ）
 *
 * @param array
 * @param i
 * @param length
 * @return void
 * @author JourWon
 * @date 2019/7/11 17:58
 */
private static void adjustHeap(int[] array, int i, int length) {
	//       i
	int temp = array[i];
	// i         ，   2i+1   
	for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
		//            ，k      
		if (k + 1 < length && array[k] < array[k + 1]) {
			k++;
		}
		//          ，          （      ）
		if (array[k] > temp) {
			array[i] = array[k];
			i = k;
		} else {
			break;
		}
	}
	// temp        
	array[i] = temp;
}

/**
 * Description:       
 *
 * @param array
 * @param a
 * @param b
 * @return void
 * @author JourWon
 * @date 2019/7/11 17:57
 */
private static void swap(int[] array, int a, int b) {
	int temp = array[a];
	array[a] = array[b];
	array[b] = temp;
}

알고리즘 분석
최 적 상황: T (n) = O (nlogn) 최 악의 상황: T (n) = O (nlogn) 평균 상황: T (n) = O (nlogn)