이 글에서는 주로 힙 정렬 과정을 그림 형식으로 설명하고, Java 코드를 사용하여 힙 정렬을 구현하고 시간 복잡도를 분석합니다. 이에 대해 관심 있는 친구들이 배울 수 있습니다.
1. 소개2. # 3. Java 코드 구현 및 시간 복잡도 분석 4. 요약 # 🎜🎜#
1. 소개배열 인덱스 1부터 시작하는 바이너리 힙과 달리 배열 인덱스 0부터 시작합니다.
코드 구현
public class Heapsort { public static void main(String[] args) { Integer[] integers = {7, 1, 13, 9, 11, 5, 8}; System.out.println("原序列:" + Arrays.toString(integers)); heapsort(integers); System.out.println("排序后:" + Arrays.toString(integers)); } public static <T extends Comparable<? super T>> void heapsort(T[] a) { if (null == a || a.length == 0) { throw new RuntimeException("数组为null或长度为0"); } //构建堆 for (int i = a.length / 2 - 1; i >= 0; i--) { percDown(a, i, a.length); } //deleteMax for (int i = a.length - 1; i > 0; i--) { swapReferences(a, 0, i); percDown(a, 0, i); } } /** * 下滤的方法 * * @param a:待排序数组 * @param i:从哪个索引开始下滤 * @param n :二叉堆的逻辑大小 * @param <T> */ private static <T extends Comparable<? super T>> void percDown(T[] a, int i, int n) { int child; T tmp; for (tmp = a[i]; leftChild(i) < n; i = child) { child = leftChild(i); if (child != n - 1 && a[child].compareTo(a[child + 1]) < 0) { child++; } if (tmp.compareTo(a[child]) < 0) { a[i] = a[child]; } else { break; } } a[i] = tmp; } private static int leftChild(int i) { return 2 * i + 1; } /** * 交换数组中两个位置的元素 * * @param a:目标数组 * @param index1 :第一个元素下标 * @param index2 :第二个元素下标 * @param <T> */ private static <T> void swapReferences(T[] a, int index1, int index2) { T tmp = a[index1]; a[index1] = a[index2]; a[index2] = tmp; } } //输出结果 //原序列:[7, 1, 13, 9, 11, 5, 8] //排序后:[1, 5, 7, 8, 9, 11, 13]
시간 복잡성: buildHeap은 O(N) 시간을 사용하고 요소 필터링에는 O(logN)이 필요하며 N-1번 필터링하므로 총 O (N+(N-1)logN) = O(NlogN). 힙 정렬의 최고 및 최악의 시간 복잡도는 O(NlogN)에서 stable이라는 과정을 통해 알 수 있습니다.
공간 복잡성: 자체 스토리지를 사용하면 의심할 여지 없이 O(1)입니다.
이 글에서는 힙 정렬이 먼저 힙 정렬된 다음 deleteMax를 통해 정렬된다는 것이 분명합니다. 공간 복잡도는 O(1)이고, 시간 복잡도는 O(NlogN)으로 안정적입니다.
위 내용은 Java 학습 힙 정렬 프로세스 다이어그램 및 코드 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!