堆排序
时间: 2023-06-22 12:31:47 浏览: 66
堆排序是一种基于堆的排序算法,它将待排序序列构建成一个小根堆或大根堆,然后依次将堆顶元素与堆中最后一个元素交换位置,并将堆的大小减1,重复执行该操作直到堆为空。由于小根堆或大根堆的特性,每次交换后堆的性质仍然得以满足,因此可以保证最终得到一个有序序列。
具体来说,堆排序的过程如下:
1. 将待排序序列构建成一个小根堆或大根堆。
2. 将堆顶元素与堆中最后一个元素交换位置,并将堆的大小减1。
3. 对新的堆顶元素进行向下调整操作,使其重新满足小根堆或大根堆的性质。
4. 重复执行步骤2和步骤3,直到堆为空。
堆排序的时间复杂度为O(nlogn),其中n为待排序序列的长度。由于堆排序的操作都是在原地进行的,因此它不需要额外的存储空间,是一种空间复杂度为O(1)的排序算法。
以下是一个使用小根堆进行升序排序的例子:
```python
def heap_sort(nums):
# 构建小根堆
def heapify(nums, n, i):
smallest = i
left_child = 2 * i + 1
right_child = 2 * i + 2
if left_child < n and nums[left_child] < nums[smallest]:
smallest = left_child
if right_child < n and nums[right_child] < nums[smallest]:
smallest = right_child
if smallest != i:
nums[i], nums[smallest] = nums[smallest], nums[i]
heapify(nums, n, smallest)
n = len(nums)
# 构建小根堆
for i in range(n // 2 - 1, -1, -1):
heapify(nums, n, i)
# 依次将堆顶元素与堆中最后一个元素交换位置,并将堆的大小减1
for i in range(n - 1, 0, -1):
nums[0], nums[i] = nums[i], nums[0]
heapify(nums, i, 0)
return nums
```
对于输入序列[3, 5, 2, 8, 1, 7, 4, 6],经过堆排序后,得到的有序序列为[1, 2, 3, 4, 5, 6, 7, 8]。