Heapsort

ゞ浴缸里的玫瑰 2022-06-02 03:48 130阅读 0赞

堆排序：堆排序就是利用堆这种数据结构的性质来对数组进行排序，在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的性质可知，最大的值一定在堆顶。堆排序一种不稳定的排序算法，其时间复杂度为O(nlogn)

算法思想  
（1）构建最大堆；   
（2）选择顶，并与第0位置元素交换；   
（3）由于步骤（2）的的交换可能破环了最大堆的性质，即第0位置的元素不再是最大元素，则需要调用maxHeap调整堆(沉降法)，根据实际情况重复步骤（2）。  
堆排序中最重要的算法就是maxHeap，该函数假设一个元素的两个子节点都满足最大堆的性质(即左、右子树都是最大堆)，只有根元素可能违反最大堆性质，那么把该元素以及左右子节点的最大元素找出来，如果该元素已经最大，那么整棵树都是最大堆，程序退出，否则交换根元素与最大元素的位置，继续调用maxHeap构建最大元素所在的子树。

package sort;
    
    /**
     * Created by long.chen  on 2017/12/29.
     */
    public class HeapSort<T extends Comparable<T>> {
        /**
         * 最大堆
         *
         * @param array
         * @param start
         * @param end
         */
        public void maxHeap(T[] array, int start, int end) {
            int left = 2 * start + 1;
            T temp = array[start];
            while (left < end) {
                if (left + 1 < end && array[left].compareTo(array[left + 1]) < 0)
                    left++;
                if (array[start].compareTo(array[left]) < 0) {
                    array[start] = array[left];
                    start = left;
                    array[start] = temp;
                    left = 2 * left + 1;
                } else {
                    break;
                }
            }
    
        }
    
        /**
         * @param array
         */
        public void sortHeap(T[] array) {
            //(array.length-1)/ 2; 最后一个拥有孩子的节点
            for (int i = (array.length - 1) / 2; i >= 0; i--) {
                maxHeap(array, i, array.length);
            }
            for (int i = array.length - 1; i > 0; i--) {
                T tmp = array[i];
                array[i] = array[0];
                array[0] = tmp;
                maxHeap(array, 0, i);
            }
        }
    
        public static void main(String[] args) {
            HeapSort<Integer> heapSort = new HeapSort<>();
            Integer[] array = {49, 38, 65, 97, 76, 13, 27, 49};
            heapSort.sortHeap(array);
            for (int i : array) {
                System.out.print(i + " ");
            }
        }
    }