Heapsort是什么

本篇內容介紹了“Heapsort是什么”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。
大頂堆：每個節點的值都大于或等于其子節點的值，在堆排序算法中用于升序排列；
小頂堆：每個節點的值都小于或等于其子節點的值，在堆排序算法中用于降序排列；

1. 算法步驟
   創建一個堆 H[0……n-1]；

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

把堆的尺寸縮小 1，并調用 shift_down(0)，目的是把新的數組頂端數據調整到相應位置；

重復步驟 2，直到堆的尺寸為 1。

public int[] sort(int[] sourceArray) throws Exception {        // 對 arr 進行拷貝，不改變參數內容        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是什么”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！