Java 排序算法之堆排序实现

Myth丶恋晨 2021-09-21 22:14 315阅读 0赞

### **最大堆的构建**： ###

采用直接插入算法，从空堆开始，依次插入各个关键码，时间复杂度为 O(n \* log n)。

采用**筛选法**构建堆，可以将时间复杂度降低到 **O(n)**。

筛选法步骤：以最大堆为例，由于最大堆是完全二叉树的一种特殊形式，因此参照完全二叉树的性质，可以将最大堆存储到数组中，用数组下标来表示节点之间的关系。从第一个具有孩子的节点 **i** = **n / 2 -1** 开始，如果以这个元素为根的子树已是最大堆，则不需调整，否则需调整子树使之成为堆。继续检查 **i - 1**，**i - 2 **等节点为根的子树，直到该二叉树的根结点（根结点下标位置为 0）被检查并调整结束后，构建才结束。具有孩子的节点 **i** ，它两个左、右孩子节点在数组中的下标位置分别为 **2 \* i + 1**，**2 \* i + 2** 。

### **堆排序算法**： ###

时间平均复杂度：**O(n \* log n)**。稳定性：**不稳定**

步骤，假设待排序元素个数为 n：

1、首先将待排序数据初始化为一个最大堆；

2、将堆顶元素 a\[0\] 和当前最后一个元素交换位置，  n= n -1。

3、调整堆结构；

4、如果当前待排元素个数 n > 1，则重复步骤 2 和步骤 3。

public class MaxHeapTest {
        public static void main(String[] args) {
            int a[] = {20,12,35,15,10,80,30,17,2,1};
            buildMaxHeap(a);
            sort(a);
            System.out.println(Arrays.toString(a));
        }
    
        /**
         * 堆排序，前提构建好最大堆，平均时间复杂度：n * log(n)，稳定性：不稳定
         * @param a
         */
        public static void sort(int []a){
            for (int n = a.length - 1 ; n > 0; n--) {
                int temp = a[n];
                a[n] = a[0];
                a[0] = temp;
                siftDown(0, a, n);
            }
        }
    
        /**
         * 筛选法构建堆，时间复杂度：O(n)
         * @param a
         */
        public static void buildMaxHeap(int []a) {
            for (int i = a.length / 2 - 1 ; i >= 0; i--) {
                siftDown(i, a, a.length);
            }
        }
    
        public static void siftDown(int i, int []a, int length){
            int j = 2 * i + 1;
            int temp = a[i];
            while (j <= length - 1) {
                // 找到左右孩子节点较大的那一个与父节点交换位置
                if (j < length -1 && a[j + 1] >= a[j]) {
                    j = j + 1;
                }
                if (a[j] >= temp) {
                    a[i] = a[j];
                    i = j;
                    j = j * 2 + 1;
                } else {
                    break;
                }
            }
            a[i] = temp;
        }
    
    }