《恋上数据结构与算法》排序（三）：堆排序

傷城~ 2022-12-29 14:06 115阅读 0赞

## 堆排序（Heap Sort） ##

> 请先看看什么是堆, 以及如何实现二叉堆 : [《恋上数据结构与算法》笔记（十七）：二叉堆][Link 1]

### 一、概念 ###

*  `堆排序`可以认为是对`选择排序算法`中寻找`最小（大）元素`的`优化`。
 *  堆排序是利用`堆`这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为`O(nlogn)`，它也是`不稳定排序`。
 *  一般`升序`采用`大顶堆`，`降序`采用`小顶堆`。

**堆排序步骤 :**

1.  交换堆顶与尾元素。
2.  堆的元素数量减`1`。
3.  对`0`位置进行`siftDown`操作。
4.  重复执行`1-3`操作，直到`堆`的元素数量为`1`。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 1]  
    ![img][]

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

自下而上的下滤  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 3]

### 二、代码实现 ###

public class HeapSort { 
    
        private static int heapSize;
    
        public static void main(String[] args) { 
            int[] array = new int[]{ 5, 3, 2, 6, 0, 1};
            heapSort(array);
            for (int i : array) { 
                System.out.print(i + " ");
            }
        }
        
        private static void heapSort(int[] array) { 
            // 原地建堆, 让一个无序的数组, 变为一个二叉堆的结构
            heapSize = array.length;
            // 自下而上的下滤 (从第一个非叶子节点开始)
            for (int i = (heapSize >> 1) - 1; i >= 0; i--) { 
                siftDown(i, array);
            }
    
            // 此时已经将数组键堆完毕
    		/* 重复下面步骤, 直到对的元素数量为1 1、交换堆顶元素与尾元素 2、堆的元素数量减一 3、交换完之后, 对0位置的元素进行1次siftDown操作(恢复堆的性质) */
            while (heapSize > 1) { 
                // 交换堆顶元素和尾部元素 (因为堆顶元素肯定是最大值, 将最大的值, 放到最后)
                swap(0, heapSize - 1, array);
    
                heapSize --; // 堆元素数量-1
    
                // 对0位置进行siftDown（恢复堆的性质）
                siftDown(0, array);
            }
        }
    
        private static void siftDown(int index, int[] array) { 
            int element = array[index];
    
            // 非叶子节点索引,heapSize / 2
            int notLeafCount = heapSize >> 1;
            // index 必须是非叶子节点 (二叉堆-完全二叉树性质的堆结构)
            while (index < notLeafCount) { 
                // 左子节点的索引
                int childIndex = (index << 1) + 1;
                int child = array[childIndex];
    
                // 右子节点的索引 = 左子节点索引 + 1
                int rightIndex = childIndex + 1;
    
                // 右子节点比左子节点大 && 右子节点没有越界
                if (rightIndex < heapSize && array[rightIndex] > child) { 
                    childIndex = rightIndex;
                    child = array[rightIndex];
                }
    
                // 大于等于子节点
                if (element >= child) break;
    
                array[index] = child;
                // 重新设置index
                index = childIndex;
            }
            array[index] = element;
        }
    
        private static void swap(int v1, int v2, int[] array) { 
            int tmp = array[v1];
            array[v1] = array[v2];
            array[v2] = tmp;
        }
    }

[Link 1]: https://blog.csdn.net/m0_37989980/article/details/111773267
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]: /images/20221120/a6513a170c9647fa814c00cfc0cb3ebe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 1]: /images/20221120/f6e8a7b320564a2f9feb8e1491e36255.png
[img]: /images/20221120/9602bd36242942248d03501478276829.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 2]: /images/20221120/7c3a8c6ac21f454a8431f07b27830ef8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 3]: /images/20221120/b4178720ce224021af6074b99f5d75bd.png