堆排序

前言:网上有很多堆排序的案例,我只想写自己堆排序。

一:堆结构

  即:一个父节点最多只能有两个子节点(可以没有),如下图

图1堆排序       图2堆排序          图3 堆排序      图4堆排序

二: 数组与堆结构转换

     假设已知堆数组   int[]  a = {9,7,6,4,5,1,3,2,}  则相应对结构如下

堆排序

 

 

 

 

图5

 

   备注: 一个父节点(pNode  为图5中的7 )和两个子节点(4(lNOde 左节点)和5(rNode 右节点))的关系

 左节点: lNOde =  2*pNode   + 1  ;

 右节点 :  rNode  = 2*pNode    +2 ;

三:通过已知数组建立成堆结构数组

     假设已知数组   int[] a = { 7,9,6,4,5,1,3,2};

思路:对一个已知堆结构数组(长度为n)中添加一个元素,并调整该结果使之成为新的堆结构数组(长度变成 n+1)

步骤一:获取该数组的第一个元素 7 (a[0])为已知堆数组。

步骤二 :获取该数组的第下一个元素9(a[1])并添加到上一个堆结构数组中,并判断其的父节点是否大于自己,如果大于则交换父节点与自己的位置,交换后自己就在父节点的位置并把自己当成新的子节点,继续寻找父节点直至自己小于父节点并返回。如果大于则已是堆结构返回。以此类推直至成为新的堆结构。

步骤三 :重复步骤二,直至数组最后一个元素。

java实现:

/**
     * 建立堆模型
     * 
     * @param a
     */
    private static void buildHeat(int[] a) {   
        for (int i = 1; i < a.length; i++) {  //注意我是从数组的第二个位置(即 index = 1)开始的
            int parentNodeIndex = getParentNodeIndex(i);
            int currentIndex = i;
            while (parentNodeIndex >= 0) {
                // 判断子节点是否大于父节点
                if (a[parentNodeIndex] < a[currentIndex]) { // 步骤2  自己大于父节点  交换父节点位置
                    // 父节点小于子节点 》》交换节点位置
                    int temp = a[parentNodeIndex];
                    a[parentNodeIndex] = a[currentIndex];
                    a[currentIndex] = temp;
                } else {
                    //
                    break;  //步骤2 : 自己小于父节点结束循环(while)已成为新的堆结构。>>>>>>>执行步骤3
                }
                currentIndex = parentNodeIndex;    //步骤2 把自己当成新的子节点
                parentNodeIndex = getParentNodeIndex(parentNodeIndex);
            }
        }
    }

四:去堆(获取排序)

  步骤一:因为堆顶是整个堆结构中最大的数,所以我获取堆顶的哪个数9(a[0]  如图5),并把堆中最后一个数2(如图5)放入堆顶 (此时的数组长度是原来数组长度的减一)

 

  步骤二 :调整堆结构(因为上一个步骤把 最后一个数放入如堆顶).。

    调整方法:   获取获取左右子节点,先判断是否有子节点,然后判断两个子节点的大小(假设9已经换成了2,当前它有两个子节点,7(左子节点) 6 (右子节点)),获取到最大的子节点(7),并于父节点(2)比较 ,如果子节点大于父节点,交换父节点与子节点的位置,并把当前自己成为新的父节点重复调整方法,直至没有子节点或父节点大于所有子节点。成为新的堆结构

 

 步骤三 :重复步骤一和二 ,直至没有改结构中没有子节点。

java实现

 备注:代码与步骤二的调整方法有些不同 ,因为 1)如果没有左节点 (调整结束) 就一定不会有右节点?。2)如果有右节点就一定有左节点?。3)如果只有左节点没有右节点?

//去除堆 》》即排序
        for(int j = 0; j < a.length; j++) {
            int lastIndex = a.length - 1 -j;
            int currentIndex = 0;       
            int temp2 = a[0];    //步骤1 : 获取堆结构中的最大数  并与最后一个数交换位置
            a[0] = a[lastIndex];
            a[lastIndex] = temp2;
            while(true) {
                //获取左节点
                int leftChildNodeIndex = getLeftChildNodeIndex(currentIndex);  //步骤2 获取左节点位置
                if(leftChildNodeIndex >= lastIndex) {    //判断做节点是否有 有数   
                    //没有左节点子节点 即去堆完成
                    for (int i = 0; i < a.length ; i++) {
                        System.out.print(a[i] + ",");
                    }
                    System.out.println("没有左节点子节点 即去堆完成");
                    break; //步骤3
                }
                //获取右节点
                int rightChildNodeIndex = getRightChildNodeIndex(currentIndex);
                if(rightChildNodeIndex >= lastIndex) {    //获取右节点
                    //没有右子节点 但有左节点     需要进行 交换            
                    if (a[leftChildNodeIndex] > a[currentIndex]) {
                        //判断左子节点  大于父节点  需要交换位置
                        int temp = a[leftChildNodeIndex];
                        a[leftChildNodeIndex] = a[currentIndex];
                        a[currentIndex] = temp;
                    }
                    for (int i = 0; i < a.length ; i++) {
                        System.out.print(a[i] + ",");
                    }
                    System.out.println("没有右子节点 但有左节点");
                    break;   //步骤3
                }
                //即有左节点又有有节点
                //先判断左右节点的大小  返回大节点
                int whichIndexBig = a[leftChildNodeIndex] > a[rightChildNodeIndex] ? leftChildNodeIndex : rightChildNodeIndex;
                //判断子节点是否大于符节点
                if (a[whichIndexBig] > a[currentIndex]) {
                    //子节点大于父节点  需要交换子父节点的位置
                    int temp = a[whichIndexBig];
                    a[whichIndexBig] = a[currentIndex];
                    a[currentIndex] =  temp;
                }
                //当前父节点
                currentIndex = whichIndexBig;      //
            }
        }

五 完整代码实现如下

堆排序
package com.jinliang.sort;

public class HeatSort {
    public static void main(String[] args) {
        int[] a = { 7,4,6,9,5,1,3,2};
        //创建堆数组
        buildHeat(a);
        for (int j = 0; j < a.length; j++) {
            System.out.print(a[j] + ",");
        }
        System.out.println("建队完成");
        //int[] a = {42, 88, 77, 76, 66, 55, 64, 52, 45, 54, 34, 2, 32, 12, 35, 1, 22, 21, 34, 3};
        //去除堆 》》即排序
        for(int j = 0; j < a.length; j++) {
            int lastIndex = a.length - 1 -j;
            int currentIndex = 0;        
            int temp2 = a[0];
            a[0] = a[lastIndex];
            a[lastIndex] = temp2;
            while(true) {
                //获取左节点
                int leftChildNodeIndex = getLeftChildNodeIndex(currentIndex);
                if(leftChildNodeIndex >= lastIndex) {
                    //没有左节点子节点 即去堆完成
                    for (int i = 0; i < a.length ; i++) {
                        System.out.print(a[i] + ",");
                    }
                    System.out.println("没有左节点子节点 即去堆完成");
                    break;
                }
                //获取右节点
                int rightChildNodeIndex = getRightChildNodeIndex(currentIndex);
                if(rightChildNodeIndex >= lastIndex) {
                    //没有右子节点 但有左节点     需要进行 交换            
                    if (a[leftChildNodeIndex] > a[currentIndex]) {
                        //判断左子节点  大于父节点  需要交换位置
                        int temp = a[leftChildNodeIndex];
                        a[leftChildNodeIndex] = a[currentIndex];
                        a[currentIndex] = temp;
                    }
                    for (int i = 0; i < a.length ; i++) {
                        System.out.print(a[i] + ",");
                    }
                    System.out.println("没有右子节点 但有左节点");
                    break;
                }
                //即有左节点又有有节点
                //先判断左右节点的大小  返回大节点
                int whichIndexBig = a[leftChildNodeIndex] > a[rightChildNodeIndex] ? leftChildNodeIndex : rightChildNodeIndex;
                //判断子节点是否大于符节点
                if (a[whichIndexBig] > a[currentIndex]) {
                    //子节点大于父节点  需要交换子父节点的位置
                    int temp = a[whichIndexBig];
                    a[whichIndexBig] = a[currentIndex];
                    a[currentIndex] =  temp;
                }
                //当前父节点
                currentIndex = whichIndexBig;    
            }
        }
        //输出排序后的数组
        for (int i = 0; i < a.length; i++) {
            System.err.print(a[i] + ",");
        }
    }

    /**
     * 建立堆模型
     * 
     * @param a
     */
    private static void buildHeat(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int parentNodeIndex = getParentNodeIndex(i);
            int currentIndex = i;
            while (parentNodeIndex >= 0) {
                // 判断子节点是否大于父节点
                if (a[parentNodeIndex] < a[currentIndex]) {
                    // 父节点小于子节点 》》交换节点位置
                    int temp = a[parentNodeIndex];
                    a[parentNodeIndex] = a[currentIndex];
                    a[currentIndex] = temp;
                } else {
                    //
                    break;
                }
                currentIndex = parentNodeIndex;
                parentNodeIndex = getParentNodeIndex(parentNodeIndex);
            }
        }
    }

    // 获取父节点索引
    public static int getParentNodeIndex(int currentIndex) {
        int parentNodeIndex = (currentIndex - 1) % 2;
        Boolean isJO = (parentNodeIndex == 0) ? true : false;
        if (isJO) { // 奇数
            // 获取父节点
            return (currentIndex - 1) / 2;
        }
        parentNodeIndex = (currentIndex - 2) / 2;
        return parentNodeIndex;
    }

    // 获取left子节点索引
    public static int getLeftChildNodeIndex(int currentIndex) {
        return 2 * currentIndex + 1;
    }
    // 获取right子节点索引
    public static int getRightChildNodeIndex(int currentIndex) {
        return 2 * currentIndex + 2;
    }

}
View Code

 

上一篇:Flutter 三种方式实现页面切换后保持原页面状态


下一篇:sg2021090721407-管理范畴-v1_beta