写了一个堆排序

堆
堆是一颗完全二叉树
堆中节点不大于或者不小于其父节点

入堆:
直接放入堆内部数据结构的最后，通过shiftUp操作，
与其父节点进行比较，交换位置

出堆：
内部数据结构的第一个（最大或者最小元素）和最后一个元素交换
位置移除最后一个元素并返回然后对第一个元素进行shiftDown操作
与其左右子节点比较，找出子节点中最大或者最小的节点交换位置

heapify
对给定的集合构建成最大堆通过从后往前遍历(n / 2) -1 个节点，即所有
非叶子节点，进行shiftDown操作。

for (int i = (n >>> 1) - 1; i >= 0; i --) {
       shiftDown(data[i])
}

将第一个元素(最大)和最后一个元素进行交换让后对前n-1个元素中的第一个
进行shiftDown操作，依次循环，最后完成堆排序

package cn.school;

import java.util.Arrays;

public class Heap {

    //    "原先18现在22"

    public static void main(String[] args) throws Exception {

        Heap main = new Heap();
        main.heapSort(new Integer[]{234, 14, 12, 34, 299, 111});
        
    }

    public <T extends Comparable<T>> void heapSort(T[] arr) {
        
        //heapify 将传入的数组变成最大堆 对所有非叶子节点进行shiftDown操作
        //从最后一个节点到第一个非叶子节点
        for (int i = (arr.length >>> 1) - 1; i >= 0; i--) {
            shiftDown(i, arr, arr.length);
        }

//        swap(arr, 0, arr.length - 1);
//        shiftDown(0, arr, arr.length - 1);
//        swap(arr, 0, arr.length - 2);
//        shiftDown(0, arr, arr.length - 2);
//      建成最大堆后，将第一个元素和最后一个元素进行交换 之后再对0 - n-1 元素中
//        的0索引进行shiftDown操作，依次往复，最终排好序
        int lastIndex = arr.length - 1;
        while (lastIndex > 0) {
            swap(arr, 0, lastIndex);
            shiftDown(0, arr, lastIndex);
            lastIndex --;
        }

        System.out.println(Arrays.toString(arr));

    }

    private void swap(Object[] arr, int i, int j) {
        Object tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }


    private <T extends Comparable<T>> void shiftDown(int i, T[] arr, int size) {
        
        //将左右子节点中最大的和自己进行交换
        while (leftChild(i) < size) {
            int j = leftChild(i);
            if (j + 1 < size && arr[j + 1].compareTo(arr[j]) > 0) {
                j++;
            }

            if (arr[i].compareTo(arr[j]) >= 0) {
                break;
            }

            T tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;

            i = j;
        }
    }

    private int leftChild(int i) {
        return i * 2 + 1;
    }

    private int rightChild(int i) {
        return i * 2 + 2;
    }


}

最后编辑于：2020.09.22 10:17:04