数据结构与算法之堆排序

╰+攻爆jí腚メ 2023-07-11 15:12 11阅读 0赞

**堆排序  
　　堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。**

**堆  
　　堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk_size_16_color_FFFFFF_t_70]

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

**大顶堆：arr\[i\] >= arr\[2i+1\] && arr\[i\] >= arr\[2i+2\]  
小顶堆：arr\[i\] <= arr\[2i+1\] && arr\[i\] <= arr\[2i+2\]**

ok，了解了这些定义。接下来，我们来看看堆排序的基本思想及基本步骤：

**堆排序基本思想及步骤  
　　堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了**

代码:

package com.yg.sort;/*
    @date    2020/3/6  10:59
    堆排序
    */
    
    import java.awt.*;
    import java.awt.image.Kernel;
    import java.util.Arrays;
    
    public class HeapSort {
        
        public static void main(String[] args) {
        
            int[] arr = {
        4, 2, 5, 6, 9, 8, 7, 2, 3};
            heapSort(arr);
            System.out.println(Arrays.toString(arr));
        }
    
        //堆排序
        public static void heapSort(int[] arr) {
        
            int temp = 0;
            //1.首先构建大顶堆
            for (int i = arr.length / 2 - 1; i >= 0; i--) {
        
                adjusHeap(arr, i, arr.length);
            }
            //2.进行首尾元素交换
            //3.交换后重新构建大顶堆,重复2,3
            for (int j = arr.length - 1; j > 0; j--) {
        
                temp = arr[0];
                arr[0] = arr[j];
                arr[j] = temp;
                adjusHeap(arr, 0, j);
            }
        }
    
        //调整成大顶堆
        /*
         * @param arr 需要调整的数组
         * @param i 非子树节点
         * @param length 数组长度
         * @return : void
         * @date : 2020/3/6 11:02
         */
        public static void adjusHeap(int[] arr, int i, int length) {
        
            int temp = arr[i];
            for (int j = 2 * i + 1; j < length; j = j * 2 + 1) {
        
                //左右比较
                if (j + 1 < length && arr[j] < arr[j + 1]) {
        
                    j++;
                }
                //上下比较
                if (arr[j] > temp) {
        
                    arr[i] = arr[j];
                    //i指向j
                    i = j;
                } else {
        
                    break;
                }
            }
            //交换
            arr[i] = temp;
    
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200306114111634.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbjEyMTQwMDA5OTk=,size_16,color_FFFFFF,t_70