归纳法：堆排序：

1、堆排序基本概念：

堆排序 (Heap Sort) 是一种树形选择排序，在排序过程中，将待排序的记录 r[l..n]看成是一 棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前 无序的序列中选择关键字最大（或最小）的记录。

堆：堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。
每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆，堆排序利用了大根堆（或 小根堆） 堆顶记录的关键字最大（或最小）这 一特征，使得当前无 序的序列中选择关键字最大（或最小） 的记录变得简单。

完全二叉树：完全二叉树：深度为K的， 有n个结点的二叉树， 当且仅当其每一个结点都与深度为K的满 二叉树中编号从1至n的结点一一对应时， 称之为完全二叉树。

              在进行堆排序操作时，节点值可看作一维数组下标

大顶堆：

我们对堆中的结点按层进行编号，映射到数组中就是下面这个样子: 

小根堆：

我们对堆中的结点按层进行编号，映射到数组中就是下面这个样子: 

2、堆排序基本思想：

堆排序的基本思想是：

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

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

3、堆排序举例说明：

例：数组 {4,6,8,5,9} , 要求使用堆排序法，将数组升序排序。

我们先进行建大根堆操作：

• 假设给定无序序列结构如下

• 此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点arr.length/2=5/2=1,也就是下面的6结点)，从左至右，从下至上进行调整。

调整后：

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

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

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

大根堆建好以后，我们再进行堆调整操作：

具体步骤：堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换

• 将堆顶元素9和末尾元素4进行交换
• 

交换后：

• 重新调整结构，使其继续满足堆定义

8与4进行交换

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

• 后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

时间复杂度分析：

初始化堆复杂度计算：

对于每个非叶子结点，都要调用上述函数，将它与它的孩子结点进行比较和交换，顺序是从后向前。

以交换节点作为基本操作，对每一层都完全铺满的堆进行分析，

设元素个数为n，则堆的高度k=log（n+1）≈log n，非叶子结点的个数为2^（k-1）-1

假设每个非叶子结点都需要进行调整，则第i层的非叶子结点需要的操作次数为k-i，

第i层共有2^（i-1）个结点，则第i层的所有结点所做的操作为k*2^（i-1）- i*2^（i-1），

共k-1层非叶子结点，总的操作次数为 

得初始化堆的复杂度为O(n)

调整堆的复杂度计算：

假设根节点和排在最后的序号为m的叶子结点交换，并进行调整，那么调整的操作次数 = 原来m结点所在的层数 = 堆的高度（因为m结点在堆的最后）= log m

共n个结点，调整的总操作次数为

得复杂度为O(n*log n)

总体复杂度为：O(n*log n)

代码实现：

public class HeapSort {  
    public static void main(String[] args) {  
        int[] arr={4,6,8,5,9};  
        heapSort(arr);  
        System.out.println(Arrays.toString(arr));  
    }  
  
    public static void heapSort(int[] arr){  
        //给你一个数组 {4,6,8,5,9} , 要求使用堆排序法，将数组升序排序  
        /* 
         将待排序序列构造成一个大顶堆 
        此时，整个序列的最大值就是堆顶的根节点。*/  
        /*adjustHeap( arr,1,arr.length); 
        adjustHeap( arr,0,arr.length);*/  
        for (int i = arr.length/2-1; i >=0; i--) {  
            adjustHeap( arr,i,arr.length);  
        }  
        int temp=0;  
        /* 
         将其与末尾元素进行交换，此时末尾就为最大值。 
         然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的如此反复执行，便能            
 得到一个有序序列了。*/  
        for (int j=arr.length-1;j>0;j--){  
            temp=arr[j];  
            arr[j]=arr[0];  
            arr[0]=temp;  
            adjustHeap(arr,0,j);  
        }  
  
    }  
  
    public static void adjustHeap(int[] arr,int i,int length){  
        //第一步把数组 {4,6,8,5,9}调整排序为{4,9,8,5,6}  
        //k=i*2+1 是循环对应的左子树元素  
        //记录当前要调整的元素  
        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 (arr[k]>temp){  
                //交换位置  
                arr[i]=arr[k];  
                i=k;  
            }else{  
                break;  
            }  
        }  
        arr[i]=temp;  
    }  
	} 

最后

以上就是无语棒球最近收集整理的关于堆排序图解归纳法：堆排序：的全部内容，更多相关堆排序图解归纳法内容请搜索靠谱客的其他文章。