堆排序思想分享

                                                                      

      🌈个人主页：人不走空      

💖系列专栏：算法专题

⏰诗词歌赋：斯是陋室，惟吾德馨

目录

      🌈个人主页：人不走空      

💖系列专栏：算法专题

⏰诗词歌赋：斯是陋室，惟吾德馨

堆排序的基本思想

堆排序的步骤

代码示例（Java）

代码解释

运行结果

堆排序的特点

总结

作者其他作品：

---

 

堆排序（Heap Sort）是一种基于堆数据结构的比较排序算法。堆是一棵完全二叉树，具有堆属性：对于最大堆，每个节点的值都大于或等于其子节点的值；对于最小堆，每个节点的值都小于或等于其子节点的值。堆排序利用了堆的这一特性来实现高效的排序。

堆排序的基本思想

堆排序的基本思想是先将待排序的数组构造成一个最大堆（或最小堆），然后通过不断地取出堆顶元素（最大值或最小值），重建堆，从而完成排序。

堆排序的步骤

1. 构建最大堆：

   • 从数组的中间开始（即最后一个非叶子节点），向前遍历，将每个节点和其子节点重新排列，使得整个数组符合最大堆的特性。

2. 排序：

   • 将堆顶元素（最大值）与数组末尾元素交换，这样最大值就放到了最终的位置。
   • 将数组长度减 1（排除已经放置到最终位置的元素），重新调整堆，使其再次满足最大堆的特性。
   • 重复上述步骤，直到整个数组有序。

代码示例（Java）

public class HeapSort {
    public static void heapSort(int[] array) {
        int n = array.length;
        
        // 构建最大堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(array, n, i);
        }
        
        // 一个一个从堆顶取出元素，放到已排序区域
        for (int i = n - 1; i > 0; i--) {
            // 交换当前堆顶元素和当前未排序部分的最后一个元素
            swap(array, 0, i);
            
            // 调整剩下的堆，长度减 1
            heapify(array, i, 0);
        }
    }
 
    private static void heapify(int[] array, int n, int i) {
        int largest = i;        // 假设当前节点 i 是最大值
        int left = 2 * i + 1;   // 左子节点索引
        int right = 2 * i + 2;  // 右子节点索引
        
        // 如果左子节点存在且大于当前节点，则更新 largest
        if (left < n && array[left] > array[largest]) {
            largest = left;
        }
        
        // 如果右子节点存在且大于当前节点，则更新 largest
        if (right < n && array[right] > array[largest]) {
            largest = right;
        }
        
        // 如果 largest 不是当前节点 i，交换它们并继续调整
        if (largest != i) {
            swap(array, i, largest);
            heapify(array, n, largest);
        }
    }
 
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
 
    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6, 7};
        System.out.println("Original array: ");
        printArray(array);
        
        heapSort(array);
        
        System.out.println("Sorted array: ");
        printArray(array);
    }
 
    private static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

代码解释

1. heapSort 方法：这是堆排序的主方法。首先，通过 heapify 函数构建最大堆，然后不断将堆顶元素移到数组末尾，调整剩余的堆。

2. heapify 方法：调整以 i 为根的子树，使其成为最大堆。它检查 i 节点和其子节点的值，确保最大的值在 i 位置。如果 i 位置不是最大值，交换它和最大子节点的位置，并递归调整交换后的子树。

3. swap 方法：交换数组中两个元素的位置。

4. main 方法：演示如何使用 heapSort 方法排序一个整数数组，并打印排序前后的数组。

5. printArray 方法：用于打印数组元素。

运行结果

Original array: 
12 11 13 5 6 7 
Sorted array: 
5 6 7 11 12 13 

堆排序的特点

• 时间复杂度：堆排序在最坏、平均和最好情况下的时间复杂度均为 O(nlog⁡n)O(n \log n)O(nlogn)。
• 空间复杂度：堆排序的空间复杂度为 O(1)O(1)O(1)，因为它只需要常量级的额外空间。
• 稳定性：堆排序不是稳定的排序算法，因为在排序过程中，元素的相对顺序可能会改变。

总结

堆排序是一种高效的排序算法，尤其适用于大数据量的排序。它利用堆这种数据结构的特点，保证了较好的时间复杂度和低空间消耗。虽然它不如快速排序常用，但在需要稳定的性能和低空间开销时，堆排序是一个不错的选择。

---

作者其他作品：

【Java】Spring循环依赖：原因与解决方法

OpenAI Sora来了，视频生成领域的GPT-4时代来了

[Java·算法·简单] LeetCode 14. 最长公共前缀 详细解读

【Java】深入理解Java中的static关键字

[Java·算法·简单] LeetCode 28. 找出字a符串中第一个匹配项的下标 详细解读

了解 Java 中的 AtomicInteger 类

算法题 — 整数转二进制，查找其中1的数量

深入理解MySQL事务特性：保证数据完整性与一致性

Java企业应用软件系统架构演变史