排序算法之堆排序

堆排序是利用堆的数据结构而设计的一种排序算法，堆排序是一种选择排序。可以利用数组的特点快速定位制定索引的元素。

大顶堆和小顶堆

堆分为大根堆和小根堆，是一种完全二叉树，大顶堆的要求是每个节点的值都不大于其父节点的值（如下左图所示）。小顶堆的要求是每个节点的值都不小于其父节点的值（如下右图所示）。对于非降序排列，一般使用大根堆。

image.png

按照从左到右，从上到下，对堆中的结点按层进行编号，将这种逻辑结构映射到数组中如下图所示。

image.png

该数组从逻辑上讲就是一个堆结构，也就是一个完全二叉树，通过用简单的数学公式可以描述一下堆的定义就是
大顶堆：arr[i]>=arr[2i+1]&&arr[i]>=arr[2i+2]
小顶堆：arr[i]<=arr[2i+1]&&arr[i]<=arr[2i+2]

堆排序基本思想

1. 先将初始待排序序列建成一个大顶堆，此时序列的最大值就是大顶堆的根节点。
2. 将大顶堆中的根节点元素与末尾元素交换，此时最大值就排在了末尾。
3. 将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值，反复执行，便可将所有元素排序。

堆排序步骤

1. 假定给定无序序列结构如下

   
   image.png

2. 此时从最后一个非叶子结点开始，即arr.length/2-1处开始，从右至左，从下至上进行调整。

   
   image.png

3. 找到第二个非叶节点4 ，由于[4,9,8]中9元素最大，4和9交换。

   
   image.png
   

   这时，由于交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

   
   image.png

此时将一个无序序列构造成了一个大顶堆。

4. 将堆顶元素9与末尾元素4交换

   
   image.png

5. 重新调整结构，使其满足堆定义

   
   image.png

6. 再将堆顶元素8与末尾元素5进行交换，得到第二大元素8

   
   image.png

后续依次进行调整，交换，反复执行，最终使得整个序列有序。

下面使用java程序实现该算法

import java.util.Arrays;
import java.util.Scanner;
public class testHeapSort {
    public static void main(String[] args) {
        System.out.print("请输入:\n");
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] arr= new int[n];
        for (int i=0;i<n;i++) {
            arr[i]=scan.nextInt();
        }
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int[] arr) {
        for(int i=arr.length/2-1;i>=0;i--) {
            adjustHeap(arr,i,arr.length);
        }
        for(int j=arr.length-1;j>0;j--) {
            swap(arr,0,j);
            adjustHeap(arr,0,j);
        }
    }
    public static void adjustHeap(int[] arr, int i, int length) {
        int temp=arr[i];
        for(int k=i*2+1;k<length;k=k*2+1) {
            if (k+1<length&&arr[k]<arr[k+1]) {
                k++;
            }
            if(temp<arr[k]) {
                arr[i]=arr[k];
                i=k;
            }
            else {
                break;
            }
        }
        arr[i]=temp;
    }
    public static void swap(int[] arr, int a ,int b ) {
        int temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
        }
}

时间复杂度

堆的存储表示是顺序的。因为堆所对应的二叉树为完全二叉树，而完全二叉树通常采用顺序存储方式。当想得到一个序列中第k个最小的元素之前的部分排序序列，最好采用堆排序。因为堆排序的时间复杂度是O(n+klogn),若k<=n/logn, 则可得到的时间复杂度为O(n)。