Carson带你学数据结构：堆排序，内存占用最少的排序算法

比眉伴天荒 2022-08-28 05:41 122阅读 0赞

![e42c52b9af8d79486a0f3cd0e50df7b7.png][]

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

# 目录 #

![示意图][d5dc9caf6b11dbff42c9c6bfe933ae53.png]

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

# 1. 基础知识 #

堆的定义 = 具有下列性质的完全二叉树：

![e5d08f3523ba0a4574f0cbec0a04d72d.png][]

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

# 2. 简介 #

利用堆（大 / 小顶堆） 进行排序 的方法

> 1.  充分利用了完全二叉树深度 = `[log2n] + 1`的特性
> 2.  是 简单选择排序 的优化 & 改进

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

# 3. 算法原理 #

![示意图][827595e0a882f0abb4c757d6a2340cc1.png]

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

# 4. 算法示意图 #

初始状态 & 算法目标  
![162a27b217f6c9d81ae6be1dab411cf8.png][]

具体算法  
![920bdff4cbc36cd5a827b927c7514fe4.png][]

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

# 5. 算法实现 #

*  具体请看注释

public class HeapSort {
    
    
        /**
         * 执行 堆排序 算法
         */
        public static void main(String[] args) {
    
            // 定义待排序数列
            int[] src = new int[]{ 50, 10, 90, 30, 70, 40, 80, 60, 20 };
    
            // 输出结果
            heapSort(src);
    
        }
        
    
        /**
         * 堆排序算法
         */
        private static void heapSort(int[] arr) {
            // 步骤1：将待排序的序列构建成一个大顶堆
            for (int i = arr.length / 2; i >= 0; i--){
                // i = i / 2 ：求出非终端结点（即，具备孩子的结点）
                // 逐渐递减： i = 4-3-2-1
                heapAdjust(arr, i, arr.length);
            }
    
            
            for (int i = arr.length - 1; i > 0; i--) {
                // 步骤2：交换 根节点 与 末尾元素
                swap(arr, 0, i);
                // 步骤3：将序列剩余的（n-1）个记录重新构造成大顶堆
                heapAdjust(arr, 0, i);
                
                // 循环步骤2 、3，直到整个序列有序
            }
    
            // 输出排序后的序列
            for(int a =0;a<arr.length;a++)
                System.out.println(arr[a]);
    
        }
    
        /**
         * 构建堆的过程
         * 参数说明：
         * @param arr = 需排序的数组
         * @param i = 需要构建堆的根节点的序号
         * @param n = 数组的长度
         */
        private static void heapAdjust(int[] arr, int i, int n) {
            int child;
            int father;
            for (father = arr[i]; leftChild(i) < n; i = child) {
                child = leftChild(i);
    
                // 若左子树＜右子树，则比较右子树和父节点
                if (child != n - 1 && arr[child] < arr[child + 1]) {
                    child++; // 序号增1，指向右子树
                }
    
                // 若父节点＜孩子结点，则需要交换
                if (father < arr[child]) {
                    arr[i] = arr[child];
                } else {
    
                    // 大顶堆结构未被破坏，不需要调整
                    break;
                }
            }
            arr[i] = father;
        }
    
        // 获取左孩子结点 位置
        private static int leftChild(int i) {
            return 2 * i + 1;
        }
    
    
        // 交换元素位置
        private static void swap(int[] arr, int index1, int index2) {
            int tmp = arr[index1];
            arr[index1] = arr[index2];
            arr[index2] = tmp;
        }
    
    
    
    }

*  测试结果

10
    20
    30
    40
    50
    60
    70
    80
    90

`Demo`地址：[Carson\_Ho的Github地址：堆排序][Carson_Ho_Github]

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

# 6. 性能分析 #

以下将分析算法的性能：时间复杂度、空间复杂度、稳定性  
![示意图][12c73ef3e43cbd8cf7136ec258841d2b.png]

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

# 7. 应用场景 #

不适合待排序序列个数较少的情况

> 原因 = 初始构建堆的比较次数较多

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

# 8. 总结 #

*  本文全面讲解了数据结构中的排序算法：堆排序
 *  Carson带你学数据结构系列文章：  
    [Carson带你学数据：线性表-数组、链表][Carson_-]  
    [Carson带你学数据：特殊的线性表-栈、队列][Carson_- 1]  
    [Carson带你学数据：串][Carson]  
    [Carson带你学数据：树][Carson 1]  
    [Carson带你学数据：二叉树][Carson 2]  
    [Carson带你学数据：图][Carson 3]  
    [Carson带你学数据：查找][Carson 4]

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

# 欢迎关注Carson\_Ho的[CSDN博客][CSDN] ！ #

博客链接：https://carsonho.blog.csdn.net/  
![e42c52b9af8d79486a0f3cd0e50df7b7.png][]

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

# 请点赞！因为你的鼓励是我写作的最大动力！ #

[e42c52b9af8d79486a0f3cd0e50df7b7.png]: /images/20220828/c234a9bca7864fa0aa205804690ca01e.png
[d5dc9caf6b11dbff42c9c6bfe933ae53.png]: /images/20220828/81eb46f129354c2299976bf786560388.png
[e5d08f3523ba0a4574f0cbec0a04d72d.png]: /images/20220828/43d3136eedfb43b390e38ab6f57d524b.png
[827595e0a882f0abb4c757d6a2340cc1.png]: /images/20220828/a23e5786c8274aa3b47c718aa9421563.png
[162a27b217f6c9d81ae6be1dab411cf8.png]: /images/20220828/db31a6a42d8540d9b489a2993fd53b9d.png
[920bdff4cbc36cd5a827b927c7514fe4.png]: /images/20220828/4b78f11bd9de488e8480631fa63dfa99.png
[Carson_Ho_Github]: https://github.com/Carson-Ho/AlgorithmLearning
[12c73ef3e43cbd8cf7136ec258841d2b.png]: /images/20220828/f04abd315cd64be0ad98400951fcac3e.png
[Carson_-]: https://carsonho.blog.csdn.net/article/details/87910747
[Carson_- 1]: https://carsonho.blog.csdn.net/article/details/103452029
[Carson]: https://carsonho.blog.csdn.net/article/details/103556469
[Carson 1]: https://carsonho.blog.csdn.net/article/details/120695951
[Carson 2]: https://carsonho.blog.csdn.net/article/details/103676620
[Carson 3]: https://carsonho.blog.csdn.net/article/details/108571561
[Carson 4]: https://carsonho.blog.csdn.net/article/details/108723161
[CSDN]: https://carsonho.blog.csdn.net/