堆排序

一、

堆排序是一种特殊的比较排序,只不过简单的比较排序没有记录比较的结果,而堆排序利用堆的数据结构记录了比较排序的结果,这样就简化了算法的复杂度!

先上代码:

(注意:由于是仿照c中的代码来写的,所以会看到下表与其真实值有一个对应转换的关系:

如果数组为new int[9],则我们遍历是从1-9开始的,那么要转换成java 的标准下标,则为0-8,所以在下面的操作中会看到很多循环是从i=1开始,而很多求数组值的操作,都是num【i-1】!,这里需要注意,在以后的时间里会对这个方法进行改进,按照java中的标准思维开始!

package cn.edu.zjut.ProgramDesign;

public class 堆排序 {
    
    public static void main(String[] args)
    {
        int[] test={1,55,6,25,12,99,550,88,7,1000};
        sort(test);
        for(int i:test)
        System.out.println(i);
    }
    public static void sort(int[] num)
    {
        int i;
        //int middle;
        //在这里i对应的数组实际编号为i=》num[i-1]
        for(i=num.length/2;i>0;i--)
        {
            heapAdjust(num,i,num.length);//构建初始大顶堆
        }
        //一次互相交换,并进行交换
        for(i=num.length;i>1;i--)
        {
            swap(num,1,i);//交换头尾元素
            heapAdjust(num,1,i-1);//重新构建大顶堆
            
        }
        
    }
    
    /**
     * 构建大顶堆的方法
     * @param num
     * @param s
     * @param m
     */
    //这个逻辑太棒了!!!
    private static void heapAdjust(int[] num,int s,int m)
    {
        int temp,j;
        temp=num[s-1];
        //s的子节点为2*s与2*s+1
        for(j=2*s;j<=m;j*=2)
        {
            if(j<m && num[j-1]<num[j-1+1])//左子节点小于右子节点,则j取值为右子节点,否则j取值左子节点
            {
                ++j;
            }
            if(temp>=num[j-1])//如果头大于右子节点,则退出循环
            {
                break;
            }
            num[s-1]=num[j-1];//如果头小于其子节点,则子节点移至顶部
            s=j;//将头节点移到该子节点处
        }
        num[s-1]=temp;//头节点赋予最后移到的位置
    }
    
    
    private static void swap(int[] num,int k,int l)
    {
        int middle;
        middle=num[k-1];
        num[k-1]=num[l-1];
        num[l-1]=middle;
    }

}

二、解释

(1)堆

——完全二叉树

——每个结点的值都大于或等于其左右节点的值,这称为大顶堆;

——每个结点的值都小于或等于其左右节点的值,这称为小顶堆;

(2)算法流程

——首先得到i=num.length/2,这表示在完全二叉树中的最后一个根结点,如果k<i=num.length/2,则k必定为完全二叉树中的一个跟节点;

——从最后一个根结点开始遍历至最上面的根结点,对每个根节点下面的节点进行大顶堆构造;循环 for(i=num.length/2;i>0;i--) 结束后,大顶堆构造完成;

——开始用顶堆与最后一个元素进行交换,交换过后对于去掉最后元素的堆进行大顶堆构造;

——循环上一步操作,直到遍历到最后一个元素(i=1)为止

(3)大顶堆构造

如果对节点k进行大顶堆构造,则需知道数组的长度,及数组本身;

——比较k与k*2,及k*2+1(这两个值为k的左右子结点),如果k比它们两个都大,则停止循环;

——如果k小于两个之中最大的,则现将最大值(假设为k*2)赋予k,然后以最大的节点(k*2)为根,继续向下遍历,寻找比
k*2大的节点,再进行交换,直至数组末尾或者k为最大~

原文地址:https://www.cnblogs.com/mengyan/p/2672547.html