Heapsort是什么

本篇內(nèi)容介紹了“Heapsort是什么”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。
大頂堆：每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值，在堆排序算法中用于升序排列；
小頂堆：每個(gè)節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值，在堆排序算法中用于降序排列；

1. 算法步驟
   創(chuàng)建一個(gè)堆 H[0……n-1]；

把堆首（最大值）和堆尾互換；

把堆的尺寸縮小 1，并調(diào)用 shift_down(0)，目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置；

重復(fù)步驟 2，直到堆的尺寸為 1。

public int[] sort(int[] sourceArray) throws Exception {        // 對(duì) arr 進(jìn)行拷貝，不改變參數(shù)內(nèi)容        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);        int len = arr.length;        buildMaxHeap(arr, len);        for (int i = len - 1; i > 0; i--) {            swap(arr, 0, i);            len--;            heapify(arr, 0, len);        }        return arr;    }    private void buildMaxHeap(int[] arr, int len) {        for (int i = (int) Math.floor(len / 2); i >= 0; i--) {            heapify(arr, i, len);        }    }    private void heapify(int[] arr, int i, int len) {        int left = 2 * i + 1;        int right = 2 * i + 2;        int largest = i;        if (left < len && arr[left] > arr[largest]) {            largest = left;        }        if (right < len && arr[right] > arr[largest]) {            largest = right;        }        if (largest != i) {            swap(arr, i, largest);            heapify(arr, largest, len);        }    }    private void swap(int[] arr, int i, int j) {        int temp = arr[i];        arr[i] = arr[j];        arr[j] = temp;    }

“Heapsort是什么”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！