LeetCode 堆排序 题解

LeetCode 堆排序 题解题目描述实现堆排序算法对一个整数数组进行排序。示例 1输入nums [5,2,3,1] 输出[1,2,3,5]示例 2输入nums [5,1,1,2,0,0] 输出[0,0,1,1,2,5]解题思路方法堆排序思路堆排序是一种基于比较的排序算法它利用堆这种数据结构来进行排序。堆是一种特殊的完全二叉树其中每个节点的值都大于或等于或小于或等于其子节点的值。堆排序的工作原理是首先将数组构建成一个最大堆然后将堆顶元素最大值与堆的最后一个元素交换然后将堆的大小减 1并重新调整堆重复这个过程直到堆的大小为 1。复杂度分析时间复杂度O(n log n)其中 n 是数组的长度。构建堆的时间复杂度是 O(n)调整堆的时间复杂度是 O(n log n)。空间复杂度O(1)只需要常数级的额外空间。代码实现方法堆排序def heap_sort(nums): n len(nums) # 构建最大堆 for i in range(n // 2 - 1, -1, -1): heapify(nums, n, i) # 逐个提取元素 for i in range(n - 1, 0, -1): # 将堆顶元素与最后一个元素交换 nums[i], nums[0] nums[0], nums[i] # 调整剩余的堆 heapify(nums, i, 0) return nums def heapify(nums, n, i): # 初始化最大元素的索引为当前节点 largest i # 左子节点的索引 left 2 * i 1 # 右子节点的索引 right 2 * i 2 # 如果左子节点存在且大于当前最大元素 if left n and nums[left] nums[largest]: largest left # 如果右子节点存在且大于当前最大元素 if right n and nums[right] nums[largest]: largest right # 如果最大元素不是当前节点交换它们并继续调整堆 if largest ! i: nums[i], nums[largest] nums[largest], nums[i] # 递归调整受影响的子堆 heapify(nums, n, largest) # 测试 nums1 [5,2,3,1] print(heap_sort(nums1)) # 输出[1,2,3,5] nums2 [5,1,1,2,0,0] print(heap_sort(nums2)) # 输出[0,0,1,1,2,5]测试用例测试用例 1输入nums [5,2,3,1]输出[1,2,3,5]测试用例 2输入nums [5,1,1,2,0,0]输出[0,0,1,1,2,5]总结本题是排序算法的经典问题主要考察对堆排序算法的理解和实现。堆排序是一种基于比较的排序算法它利用堆这种数据结构来进行排序。堆排序的核心思想是首先将数组构建成一个最大堆然后将堆顶元素最大值与堆的最后一个元素交换然后将堆的大小减 1并重新调整堆重复这个过程直到堆的大小为 1。这种方法的时间复杂度为 O(n log n)是一种不稳定的排序算法适用于大规模数据的排序。掌握堆排序的原理对于理解堆数据结构和排序算法非常重要。