数据结构与算法（二十二）堆排序

堆排序基本介绍

• 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。
• 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。
• 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆.

大顶堆

大顶堆特点：arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2] // i 对应第几个节点，i从0开始编号

小顶堆

小顶堆：arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2] // i 对应第几个节点，i从0开始编号

一般升序采用大顶堆，降序采用小顶堆 

堆排序基本思想

堆排序的基本思想是：

• 将待排序序列构造成一个大顶堆
• 此时，整个序列的最大值就是堆顶的根节点。
• 将其与末尾元素进行交换，此时末尾就为最大值。
• 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了.

代码实现

/**
 * 堆排序
 */
public class HeapSort {


    public static void main(String[] args) {
        int [] arr={8,3,4,1,0,3,2};
        heapsort(arr);
        System.out.println(Arrays.toString(arr));
    }


    public static void heapsort(int [] arr){
        int temp=0;
        for (int i = arr.length/2-1; i >=0; i--) {
            adjustHeap(arr,i,arr.length);
        }
        for (int j = arr.length-1; j >0; j--) {
            temp=arr[j];
            arr[j]=arr[0];
            arr[0]=temp;
            adjustHeap(arr,0,j);
        }
    }

    /**
     * 将一个数组调整成一个大顶堆
     * @param arr
     * @param i
     * @param length
     */
    public static  void adjustHeap(int arr[] ,int i,int length){

        int temp=arr[i];

        for (int k = 2*i+1; k <length; k=k*2+1) {
            if (k+1<length&&arr[k]<arr[k+1]){
                k++;
            }
            if (arr[k]>temp){
                arr[i]=arr[k];
                i=k;
            }else {
                break;
            }
        }
        arr[i]=temp;
    }

}