堆排序
时间: 2023-06-21 16:11:47 浏览: 60
堆排序是一种基于堆的排序算法,它的时间复杂度为 O(nlogn)。堆排序的基本思想是:将待排序的序列构造成一个大顶堆或小顶堆,此时整个序列的最大值或最小值就是堆顶的根节点。然后将其与堆的最后一个节点交换位置,将堆的大小减 1,再对堆进行调整使其满足堆的性质,然后重复执行交换和调整操作,直到整个序列有序。
堆排序具体步骤如下:
1.将待排序的序列构造成一个大顶堆或小顶堆。
2.将堆顶元素与堆的最后一个元素交换位置,将堆的大小减 1。
3.对新的堆顶元素进行调整,使其满足堆的性质。
4.重复执行步骤 2 和步骤 3,直到整个序列有序。
下面是堆排序的 Python 代码实现:
```python
def heapify(arr, n, i):
largest = i # 初始化最大值
l = 2 * i + 1 # 左子节点的索引
r = 2 * i + 2 # 右子节点的索引
# 判断左子节点是否大于根节点
if l < n and arr[l] > arr[largest]:
largest = l
# 判断右子节点是否大于根节点
if r < n and arr[r] > arr[largest]:
largest = r
# 如果最大值不是根节点,则交换它们的位置
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
# 递归调整堆
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# 构造大顶堆
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 逐个将堆顶元素与堆的最后一个元素交换位置,并调整堆
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
return arr
```
在这个实现中,我们首先构造一个大顶堆,然后逐个将堆顶元素与堆的最后一个元素交换位置,并调整堆,直到整个序列有序。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)