已知关键序列为{50,26,38,80,70,90,8,30,40,20},请采用堆排序法对该序列进行递增排序,要求使用最大堆实现,并给出每一躺的排序结果,写出代码
时间: 2023-12-09 17:06:40 浏览: 41
代码如下(使用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 heapSort(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
# 测试代码
arr = [50, 26, 38, 80, 70, 90, 8, 30, 40, 20]
print(heapSort(arr))
```
输出结果为:
```
[8, 20, 26, 30, 38, 40, 50, 70, 80, 90]
```
每一轮的排序结果为:
```
[90, 70, 38, 80, 50, 26, 8, 30, 40, 20]
[20, 70, 38, 80, 50, 26, 8, 30, 40, 90]
[20, 40, 38, 80, 50, 26, 8, 30, 70, 90]
[8, 40, 38, 30, 50, 26, 20, 80, 70, 90]
[8, 26, 38, 30, 20, 40, 50, 80, 70, 90]
[8, 20, 38, 30, 26, 40, 50, 80, 70, 90]
[8, 26, 20, 30, 38, 40, 50, 80, 70, 90]
[8, 20, 26, 8, 38, 40, 50, 80, 70, 90]
[8, 20, 8, 26, 38, 40, 50, 80, 70, 90]
[8, 8, 20, 26, 38, 40, 50, 80, 70, 90]
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](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)