堆排序的一些思路看下去相信会有收获

朱雀 2022-12-14 13:46 154阅读 0赞

给出一些思路 希望能帮到大家

也算是做个记录 自己忘记了也能够看到

先明确一些概念  
注意我圈出的部分  
![在这里插入图片描述][20201014081055496.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center]

--------------------

开始啦！！！！！！！！！！！！

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 1]  
假设我们要对这样的数组进行排序

思路是这样的

如果是升序排列 先要将该树变为**大顶堆**

根节点与末尾元素交换 放在数组末尾 那就是9

接着将除9外的元素变成大顶堆 根元素为最大元素

在与末尾元素进行交换 放在数组末尾 之后是8

一直循环。。。。完全有序

--------------------

我觉得关键的有两部分  
1.堆排序是基于完全二叉树的 即从左至右一直连续 中间不能有**坑**

2.如何找到他从下往上 从左至右的第一个非叶节点呢(包含孩子节点)

正是基于了**完全二叉树** 的特性才能够做到 这样找下去的第一个非叶子节点的索引为

int i=arr.length/2-1;

再看下上图 i=5/2-1=1

找到的节点正是编号为1的元素![在这里插入图片描述][20201014084821756.png_pic_center]

找到该非叶节点temp后 将temp与他的孩子节点做比较 大的那个与temp交换位置

同时指针指向**大孩子**的索引 以便继续**深度遍历**

此时面临两种情况 大孩子和左右子节点比较 发现是最大的 则跳出

还有种就是现在的情况 下面已经没有孩子节点了 证明整个循环完毕

有人问 为啥还要深度遍历呢 不是从下至上开始的吗

看图

找到6  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 2]  
⑥与⑨交换 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 3]  
指针指向⑥ 发现没有元素了 此时第一遍遍历完毕 这时候要往上找非叶节点了

--------------------

注意力放在④上面 开始比较

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 4]  
往左走

⑨和⑧比较 ⑨要大 将④和⑨交换 指针放在大孩子身上 就是④这个节点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 5]  
发现没 为什么要继续往下 因为 下标 1 3 4 这几个元素 已经乱了 不满足大顶堆的概念了  
![在这里插入图片描述][20201014084905569.png_pic_center]

所以要再进行比较 交换 指针移动  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 6]  
指针指向④ 但此时已经没有孩子节点了 遍历完毕

**大顶堆构建完成**

之后就是将根元素拿走 放入数组末尾

但不能直接拿 因为根移动 **树就散了** 所以需要将0和4下标交换

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 7]

下次遍历不用管9了 但此时树又乱了 不是大顶堆了 再次调整。。。最终达到有序状态

注意我是从上至下的顺序 其中k就是 指向左右节点的指针

public class HeapSort { 
    
        //注意len是一个可变的长度 每次排完序 找出最大元素时 都会-1
        public static void sort(int[] arr, int i, int len) { 
            int temp = arr[i];
            //一直往左节点的方向遍历
            for (int k = 2 * i + 1; k < len; k = 2 * k + 1) { 
                //当右子节点的下标不大于len时 且左子节点<右子节点 指针+1 指向右节点
                if (k + 1 < len && arr[k] < arr[k + 1]) { 
                    k++;
                }
                //当leaf叶节点比孩子节点小时 需要交换
                if (temp < arr[k]) { 
                    //将当前找到的最大元素与叶节点进行交换 保证此时叶节点是最大的
                    arr[i] = arr[k];
                    arr[k] = temp;
                    //很关键 将叶节点指针指向孩子节点 若没有孩子节点 
                    //则不会进入for循环 k < len 限定了k的大小
                    i = k;
                } else { 
                    break;
                }
    
            }
        }
        
       //堆排序的完整步骤
       public static void heapSort(int[] arr) { 
       		//不断切换叶节点 arr.length / 2 - 1很重要 i=0即为根节点
            for (int i = arr.length / 2 - 1; i >= 0; i--) { 
         		//就是调整大顶堆的过程
                sort(arr, i, arr.length);
            }
            //这一步是先将最大元素放到末尾 前段无序 后段有序 慢慢的 后面全部有序
            for (int j = arr.length - 1; j > 0; j--) { 
            	//简单的交换操作
                int temp = arr[j];
                arr[j] = arr[0];
                arr[0] = temp;
                //交换完毕后 只是将最大元素放到末尾 此时大顶堆规则被破坏 还需要进行调整
                //但只需要稍微调整下就行了 因为他的左右孩子节点必有一个是整个堆里最大的 不需要往后遍历了
                sort(arr, 0, j);
            }
            //打印操作
            System.out.println(Arrays.toString(arr));
        }
    
    
        public static void main(String[] args) { 
            int[] arr = { 4,6,8,5,9};
            heapSort(arr);
        }
    }
    
    //输出 [4, 5, 6, 8, 9]

[20201014081055496.png_pic_center]: /images/20221123/aa26da7ffe394f54b6a837045b204b40.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/83939a51e96d473ab7f2e5e65bcb88b0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/f112b492314b4f72b23a633f873c1c69.png
[20201014084821756.png_pic_center]: /images/20221123/025fd7a8239b4fe8b6792731f487da5d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/994446b1dbd246e1b3d4c1deadeab236.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/a5ccfe13ada3412f80f62f8cbed6ee03.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/a6ff421e4e2a4c7f9b063465c55958d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/c5b577b5df5d4f099eb64656de82f053.png
[20201014084905569.png_pic_center]: /images/20221123/43a07e095dd74f96b82b4f3e9457494b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/959370e68fca41e095ad1196e1242ef7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/d308a5ce5fcc42ecbdff2d60aa76690a.png