>  기사  >  Java  >  Java 학습 힙 정렬 프로세스 다이어그램 및 코드 설명

Java 학습 힙 정렬 프로세스 다이어그램 및 코드 설명

little bottle
little bottle앞으로
2019-04-28 10:03:332857검색

이 글에서는 주로 힙 정렬 과정을 그림 형식으로 설명하고, Java 코드를 사용하여 힙 정렬을 구현하고 시간 복잡도를 분석합니다. 이에 대해 관심 있는 친구들이 배울 수 있습니다.

1. 소개2. # 3. Java 코드 구현 및 시간 복잡도 분석 4. 요약 # 🎜🎜#

1. 소개

우선순위 큐는 위와 같이 O(NlogN) 시간으로 정렬하는 데 사용할 수 있습니다. 이 기사에서 topK 문제를 해결하는 데 사용된 것과 동일한 아이디어가 힙 정렬입니다.

2. 그래픽 힙 정렬(힙 정렬)

    알고리즘적 사고 : 배열 요소에 대해 buildHeap을 수행한 다음 힙에 대해 N-1 deleteMax 작업을 수행하여 힙 순서 지정(큰 상위 힙 구축)
  1. 새 배열을 사용하여 저장하는 경우 O(N) 공간이 필요하지만 deleteMax가 위치를 비우고 꼬리 노드를 필터링할 때마다 deleteMax의 데이터를 사용할 수 있습니다. 마지막에 배치됩니다.
  2. 힙 정렬 프로세스:
  3. 바이너리 힙에 대해 모른다면 다음을 살펴보세요. 그림으로 표시된 우선순위 큐(힙)#🎜 🎜#

    3. Java 코드 구현 및 시간 복잡도 분석

    배열 인덱스 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)입니다.

4. 요약

이 글에서는 힙 정렬이 먼저 힙 정렬된 다음 deleteMax를 통해 정렬된다는 것이 분명합니다. 공간 복잡도는 O(1)이고, 시간 복잡도는 O(NlogN)으로 안정적입니다.

위 내용은 Java 학습 힙 정렬 프로세스 다이어그램 및 코드 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
이 기사는 cnblogs.com에서 복제됩니다. 침해가 있는 경우 admin@php.cn으로 문의하시기 바랍니다. 삭제