排序算法,堆排序

 我的笔记   2020-03-13 16:46   111 人阅读  0 条评论

相信大家都听说堆排序吧,二叉树在大学期间大家应该都学过,不过按照我当时那个状态,是完全没听懂。

这都好多年了,我觉得再不弄懂二叉树排序,我怕是死都不能瞑目了。

首先,要想要排序,得有一个数组,biu~

8329146

这个数组大家看到了,是一个无序数组,要想用堆排序,首先让它变成一个堆

image.png

一、初始化堆

1、从左往后,先取出 8

image.png

2、然后取出3 ,放在8的左下方

image.png

3、取出2放在8的右下方

image.png

4、取出9放在3的做下方

image.png

5、但是9大于3所以3和9交换位置

image.png

6、但是9又大于8,8和9再次交换位置

image.png

7、这样就可以了,继续取数组。把1取出来放在3的右侧,8的右下方


image.png

8、取出4放在2的左下方

image.png

9、但是4比2大,同理,继续交换位置

image.png

10、取6放在4的右下侧,但是6大于4

image.png

11、交换位置

image.png

经过11步,我们看到,已经得到一个稳定堆了,这个堆有什么特征呢?

二叉树的父节点比左右两个子节点大

如果把元素的位置都用红色序号标记,那么的要如下图

image.png

最后的出公式:

arr[i]>=arr[2i+1]&&arr[i]>=arr[2i+2]

二、堆排序

现在我们得到一个稳定堆了之后,我们还得要一个新数组,我们就可以开始排序了:

9863124

1、取出位置一(4)和位置七(9)进行交换,然后将数字9存到最后一位,下次遍历不会再包含9

得出:

4863129

image.png

2、可以看出,在9和4进行了交换后,这个堆(排除9)就不是一个稳定堆了,因为不满足,初始化堆的时候:二叉树的父节点比左右两个子节点大

那么将进行第二轮交换。

从4开始我们把8和4进行交换后,发现堆又稳定了

image.png

那么,把位置一(8)和位置六(2)进行交换,然后将数字8存到最后一位,下次遍历不会再包含8,9

2463189

就这样循环第一步,第二步,就可以得到一个从小到大的数组:

1234689

最后附上代码(递归方式):

/**
 * @Description :
 * @Author :付亚东
 * @Date :2020/3/13
 **/
public class Test {
    public static void main(String[] args) {
        int[] arr= {8,3,2,9,1,4,6};
        initHeap(arr);
        sortHeap(arr);
        System.out.println("-------");
        for (int a:arr) {
            System.out.print(a);
        }
        System.out.println("");
        System.out.println("-------");
    }

    /***
     * 初始化堆,稳定堆,这个方法是第一大步
     * @param arr
     */
    public static void initHeap(int[] arr){
        //将数组先转换成一个堆,就是上边的图一
        //因为最后一层的借点没有子节点,所以直接从倒数第二行的最后一个节点开始,也就是图一的2
        for(int i=(arr.length-2)/2;i>=0;i--){
            swapHeap(arr,i,arr.length-1);
        }
    }

    /***
     * 这个方法是第二大步
     * @param arr
     */
    public static void sortHeap(int[] arr){
        //将堆顶的那个数字和最后一个数字交换
        for (int i=arr.length-1;i>0;i--){
            swapLocation(arr,0,i);
            //继续交换,从堆顶开始(父节点也就是0),i-1代表排除已经交换过位置的
            swapHeap(arr,0,i-1);
        }
    }


    /***
     * 堆排序
     * @param arr
     * @param parent
     * @param length
     */
    public static void swapHeap(int[] arr,int parent,int length){
        //这是传进来的节点的左子节点
        int leftChiledLocation = (parent<<1)+1;
        //这是传进来的节点的右子节点
        int rightChiledLocation = leftChiledLocation+1;
        //临时当做父节点最大
        int maxChildLocation=leftChiledLocation;
        // 左子节点索引超出计算范围,直接返回。
        if(leftChiledLocation>length) return;

        //查出两个子节点比较大的哪一个,赋值给maxChild
        if(rightChiledLocation<=length && arr[leftChiledLocation]<arr[rightChiledLocation]){
            maxChildLocation = rightChiledLocation;
        }
        //然后判断两个子节点大的那一个,和自己本身比较,如果比自己(父节点)大,就交换位置,若“<”这是从大到小
        if(arr[maxChildLocation]>arr[parent]){
            swapLocation(arr,maxChildLocation,parent);
            //然后把换好的位置,也就是左节点或者右节点,继续往下查找
            swapHeap(arr,maxChildLocation,length);
        }
    }

    /***
     * 交换数组位置
     * @param arr
     * @param a
     * @param b
     */
    public static void swapLocation(int[] arr,int a,int b){
        int temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }

}





我的笔记博客版权我的笔记博客版权
本文地址:https://wdnote.com/post/759.html
版权声明:本文为原创文章,版权归 我的笔记 所有,欢迎分享本文,转载请保留出处!

 发表评论


表情

还没有留言,还不快点抢沙发?