【数据结构与算法】堆排序代码

深藏阁楼爱情的钟 2023-07-21 06:20 14阅读 0赞

参考网站： https://www.jianshu.com/p/11655047ab58

#### 1. 大顶堆与小顶堆 ####

1.若父亲大孩子小，则这样的堆叫做大顶堆；  
2.若父亲小孩子大，则这样的堆叫做小顶堆。

#### 2. 堆排序的算法思路 ####

假设一个序列如下所示：

**元素**　【49，38，65，97，76，13，27，49】  
**索引**　【０，１，２，３，４，５，６，７　】  
一. 首先将这个序列转化为堆，如下图所示，它具有如下特点：

1.  根节点为这个序列的第一个元素；
2.  叶子结点都在序列左半部分，非叶子结点都在序列的右半部分。求非叶子节点在序列中的位置代码为：

//第一个非叶子节点97在序列中的位置
     i = (list.length) / 2 - 1；
     //求所有非叶子结点的位置
    for(i = (list.length) / 2 - 1；i>=0;i--){
    save(i);//存储下所有非叶子结点
    }

1.  其非叶子结点k的左节点序列位置为：index = 2 \* k + 1;  
    其非叶子结点k的右节点序列位置为：index = 2 \* k + 2（可能没有右节点： 2 \* k + 2< len）;

![在这里插入图片描述][20200403114409986.png_pic_center]  
二 . 然后将这个堆转化为大顶堆，规则为：  
4. 遍历每个非叶子结点，对比他们的值和左右孩子结点的值，将最大的值交换到根节点上。  
5. 第1步的交换可能引发被交换的孩子结点的值，不满足堆的定义。所以要对孩子结点所在堆进行同样操作，直到满足堆的定义。

//k存储根节点位置， temp根节点值，index存储左（或右）孩子结点位置或
    int k = i, temp, index = 2 * k + 1;
    //index记录当前结点的孩子结点在序列中的位置，且不越界
    while (index < len) {
    //下面先比较结点的左右孩子结点：
    //右孩子节点存在且右孩子结点大于左节点，指针指向右节点。
     if (index + 1 < len&&list[index] < list[index + 1]) {
     index++;
     }
     //将大结点移动到根节点
     if (list[index] >  list[i]) {
     list[k] = list[index];
     list[index]= temp;
     k = index;               //k存储根节点位置
     index = 2 * k + 1;       //k存储根节点左孩子结点位置
     } else {                 //不发生移动直接终止本层循环体
     break;
     }  
    }

三 . 然后每次最大的结点就在了序列前，将最大结点与叶子结点交换位置，即将序列第一个元素和最后一个元素交换，最大元素到达最终位置。无序序列中减少一个，有序数列中增加一个。**此时只有序列第一个元素不满足条件，对其进行调整**（因为其他都应经调整过了的）：

for (int i = list.length - 1; i >= 1; i--) {
                //以下三句换出了根结点的关键字，将其放进最终位置
                int temp = list[0];
                list[0] = list[i];
                list[i] = temp;
                headAdjust(list, i, 0);//每执行一次，一轮调整
            }

#### 2. 堆排序的代码 ####

/**
     * @author: gethin
     * @create: 2018-05-23 16:21
     * @description: 常用排序算法
     **/
    public class 堆排序 {
        public static void main(String[] args) {
            int[] nums = {16,7,3,20,17,8};
            headSort(nums);
            for (int num : nums) {
                System.out.print(num + " ");
            }
        }
    
        /**
         * 堆排序
         */
        public static void headSort(int[] list) {
            //构造初始堆,从第一个非叶子节点开始调整,左右孩子节点中较大的交换到父节点中
            for (int i = (list.length) / 2 - 1; i >= 0; i--) {
                headAdjust(list, list.length, i); //每一轮调整一个结点
            }
            //排序，将最大的节点放在堆尾，然后从根节点重新调整
            for (int i = list.length - 1; i >= 1; i--) {
                //以下三句换出了根结点的关键字，将其放进最终位置
                int temp = list[0];
                list[0] = list[i];
                list[i] = temp;
                headAdjust(list, i, 0);//每执行一次，一轮调整
            }
        }
    
        private static void headAdjust(int[] list, int len, int i) {
            int index = 2 * i + 1,temp;
            while (index < len) {
                if (index + 1 < len&&list[index] < list[index + 1]) {
                        index++;
                }
                if (list[index] > list[i]) {
                    temp = list[i];
                    list[i] = list[index];
                    list[index] = temp;
                    i = index;
                    index = 2 * i + 1;
                } else {
                    break;//break是跳出整个循环，continue是中止此次循环
                }
            }
        }
    }

[20200403114409986.png_pic_center]: /images/20230528/a8a76a64d8cd49ddae113fd10d5dcd91.png