数据结构与算法(二十二)堆排序

堆排序基本介绍

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

大顶堆

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

小顶堆

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

image.png

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

堆排序基本思想

堆排序的基本思想是:

  • 将待排序序列构造成一个大顶堆
  • 此时,整个序列的最大值就是堆顶的根节点。
  • 将其与末尾元素进行交换,此时末尾就为最大值。
  • 然后将剩余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;
    }

}

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://www.fengpt.cn/archives/数据结构与算法二十二堆排序