关于java:排序算法之堆排序

5次阅读

共计 1101 个字符，预计需要花费 3 分钟才能阅读完成。

堆排序是指利用堆这种数据结构所设计的一种排序算法。沉积是一个近似齐全二叉树的构造，并同时满足沉积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序能够说是一种利用堆的概念来排序的抉择排序。分为两种办法：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的均匀工夫复杂度为 Ο(nlogn)。

创立一个堆 H[0……n-1]；
把堆首（最大值）和堆尾调换；
把堆的尺寸放大 1，并调用 shift_down(0)，目标是把新的数组顶端数据调整到相应地位；
反复步骤 2，直到堆的尺寸为 1。

    public static void main(String[] args) {int[] arr = {5, 3, 1, 4, 2, 7, 8, 6, 10, 9};
        buildSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void buildSort(int[] tree) {buildHeap(tree);
        for (int i = tree.length - 1; i >= 0; i--) {swap(tree, 0, i);
            heapify(tree, 0, i);
        }

    }


    private static void buildHeap(int[] tree) {int parent = (tree.length / 2) - 1;
        for (int i = parent; i >= 0; i--) {heapify(tree, i, tree.length);
        }
    }


    private static void heapify(int[] tree, int i, int length) {

        int leftChild = 2 * i + 1;
        int rightChild = 2 * i + 2;
        int max = i;

        if (leftChild < length && tree[leftChild] > tree[max]) {max = leftChild;}

        if (rightChild < length && tree[rightChild] > tree[max]) {max = rightChild;}

        if (max != i) {swap(tree, max, i);
            heapify(tree, max, length);
        }

    }

    private static void swap(int[] tree, int max, int i) {int temp = tree[max];
        tree[max] = tree[i];
        tree[i] = temp;

    }