【排序算法】堆排序原理及Java实现

蔚落 2022-08-21 10:54 248阅读 0赞

## 1、基本思想 ##

堆是一种特殊的树形数据结构，其每个节点都有一个值，通常提到的堆都是指一颗完全二叉树，根结点的值小于（或大于）两个子节点的值，同时，根节点的两个子树也分别是一个堆。  
![这里写图片描述][20160427183713823]  
堆排序就是利用堆（假设利用大顶堆）进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的 *n-1* 个序列重新构造成一个堆，这样就会得到 *n* 个元素中次大的值。如此反复执行，便能得到一个有序序列了。  
堆排序的实现需要解决的两个关键问题：  
（1）将一个无序序列构成一个堆。  
（2）输出堆顶元素后，调整剩余元素成为一个新堆。

## 2、复杂度分析 ##

堆排序的运行时间主要耗费在初始构建堆和在重建堆时反复筛选上。在构建对的过程中，因为我们是完全二叉树从最下层最右边的非终端节点开始构建，将它与其孩子进行比较和若有必要的互换，对每个非终端节点来说，其实最多进行两次比较和互换操作，因此整个构建堆的时间复杂度为*O(n)*。  
在正式排序时，第i次取堆顶记录重建堆需要用*O(logi)*的时间（完全二叉树的某个节点到根节点的距离为![这里写图片描述][20160427183239770]），并且需要取*n-1*次堆顶记录，因此，重建堆的时间复杂度为*O(nlogn)*。  
所以总体来说，堆排序的时间复杂度为*O(nlogn)*，由于堆排序对原始记录的状态并不敏感，因此它无论是最好、最坏和平均时间复杂度均为*O(nlogn)*。这在性能上显然要远远好过于冒泡、简单选择、直接插入的时间复杂度了。  
空间复杂度上，它只有一个用来交换的暂存单元，也非常的不错。不过由于记录的比较与交换是跳跃式进行的，因此堆排序也是一种不稳定的排序方法。  
另外，由于出事构建堆所需要的比较次数比较多，因此，他并不适合待排序序列个数较少的情况。

## 3.大根堆排序算法的基本操作 ##

① 初始化操作：将R\[1..n\]构造为初始堆；  
②每一趟排序的基本操作：将当前无序区的堆顶记录R\[1\]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。

注意：  
①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。  
②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。

## 4、Java实现如下 ##

public class HeapSort { 
        /** * 构建大顶堆 */
        public static void adjustHeap(int[] a, int i, int len) {
            int temp, j;
            temp = a[i];
            for (j = 2 * i; j < len; j *= 2) {
       // 沿关键字较大的孩子结点向下筛选
                if (j < len && a[j] < a[j + 1])
                    ++j; // j为关键字中较大记录的下标
                if (temp >= a[j])
                    break;
                a[i] = a[j];
                i = j;
            }
            a[i] = temp;
        }
    
        public static void heapSort(int[] a) {
            int i;
            for (i = a.length / 2 - 1; i >= 0; i--) {
       // 构建一个大顶堆
                adjustHeap(a, i, a.length - 1);
            }
            for (i = a.length - 1; i >= 0; i--) {
       // 将堆顶记录和当前未经排序子序列的最后一个记录交换
                int temp = a[0];
                a[0] = a[i];
                a[i] = temp;
                adjustHeap(a, 0, i - 1);// 将a中前i-1个记录重新调整为大顶堆
            }
        }
    
        public static void main(String[] args) {
            int a[] = { 51, 46, 20, 18, 65, 97, 82, 30, 77, 50 };
            heapSort(a);
            System.out.println(Arrays.toString(a));
        }
    }

[20160427183713823]: /images/20220724/e7df967fda8049c9ad77ca5b4571fe63.png
[20160427183239770]: /images/20220724/1c1b7b90d77e4650b1c6f73e70ccef96.png