堆排序java

喜欢ヅ旅行 2022-06-06 08:24 141阅读 0赞

*  堆排序是利用堆这种数据结构而设计的一种算法，堆排序是一种选择排序，  
    它的最好、最坏、平均时间复杂度均为O(n log n)  
    它也是不稳定排序
 *  堆进行调整为大顶堆或小顶堆，将顶部元素换到末尾，在重新调整排除末位置的元素构成的新树，重复执行。
 *  根据堆的性质，可以直接通过数组索引映射堆中父子节点的关系

需要排序的数组 ->对应堆的层序遍
    满足以下公式：
    左孩子 = arr[2i+1]
    右孩子 = arr[2i+2]
    大顶堆：arr[i]>=arr[2i+1] && arr[i]>=arr[2i+2]
    小顶堆：arr[i]<=arr[2i+1] && arr[i]<=arr[2i+2]
    最后一个非叶子节点下标 = length/2-1
    第一个  叶子节点下标 = length/2

*  堆调整是从最后一个非叶子节点（下标是length/2-1）开始
 *  从小到大排序，调整为大顶堆
 *  从大到小排序，调整为小顶堆

java代码：

public class HeapSort { 
    
        public static <AnyType extends Comparable<? super AnyType>> void heapSort(AnyType[] a) {
            // 建堆
            for (int i=a.length/2-1; i>=0; i--) {     //从最后一个非叶子节点开始，从左向右，从下往上，调整成大顶堆
                percDown(a, i, a.length);
            }
            // 交换元素后，调整堆
            for (int i=a.length-1; i>0; i--) {
                swapReferences(a, 0, i);       // 调整堆顶元素与末尾元素
                percDown(a, 0, i);               // 重新调整（堆顶），堆的范围是length - 1, 最后一个元素已经从堆中排除
            }
        }
    
        /** * 调整堆的思路：从序号最大的非叶子节点开始便利，左右孩子中有比它大的，交换该节点和叶子的位置 * 父节点和较大的孩子节点交换后，新的父节点是稳定的，但是新的孩子节点可能不满足大顶堆规则，而另一边的孩子不会受影响， * 所以要继续对新孩子进行调整判断，直至新孩子满足规则，或者没有新孩子为止 */
        public static <AnyType extends Comparable<? super AnyType>> void percDown(AnyType[] a, int i, int n) {
            int child;
            AnyType tmp; // 保存待调整的父亲节点
            // 从最后一个非叶子节点开始
            for (tmp = a[i]; leftChild(i) < n; i=child) { // 交换以后，调下去的节点可能会依旧不平衡
                child = leftChild(i);   // 取得左孩子的下标
                //child=n-1, 说明只有一个左孩子，直接到下一步
                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;     // 父节点元素给child
        }
    
        public static int leftChild(int i) {
            return 2 * i + 1;
        }
    }