堆排序python代码
时间: 2023-11-09 21:59:39 浏览: 42
以下是堆排序的Python代码示例:
```python
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[i] < arr[left]:
largest = left
if right < n and arr[largest] < arr[right]:
largest = right
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):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
return arr
# 测试示例
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = heapSort(arr)
print(sorted_arr)
```
相关问题
写一个堆排序python代码
### 回答1:
这是一个堆排序的 Python 代码:
```
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
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, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("排序后的数组是:")
for i in range(len(arr)):
print("%d" %arr[i]),
```
### 回答2:
堆排序(Heap Sort)是一种基于二叉堆(Heap)数据结构的经典排序算法。在堆排序中,首先需要将待排序的序列构建成一个大顶堆或小顶堆,然后将堆顶元素与最后一个元素交换位置,并重新调整堆,反复执行这个过程直到所有元素有序。
以下是基于Python的堆排序实现代码:
```python
def heapify(arr, n, i):
largest = i # 根节点
left = 2 * i + 1 # 左子节点
right = 2 * i + 2 # 右子节点
# 判断左子节点是否存在且大于根节点
if left < n and arr[i] < arr[left]:
largest = left
# 判断右子节点是否存在且大于根节点和左子节点
if right < n and arr[largest] < arr[right]:
largest = right
# 如果最大值不是根节点,则交换根节点和最大值,并继续调整堆
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[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
# 示例使用:
arr = [4, 10, 3, 5, 1]
heapSort(arr)
print(arr)
# 输出结果: [1, 3, 4, 5, 10]
```
以上代码中,`heapify`函数用于调整堆,`heapSort`函数用于构建和排序堆。首先构建一个大顶堆,然后依次将堆顶元素与最后一个元素交换,并重新调整堆,最终得到有序序列。
注意:在堆排序中,为了简化代码,省略了对输入参数的合法性判断。实际使用中,可以添加相应判断来确保输入的正确性和安全性。
### 回答3:
堆排序是一种基于二叉堆的排序算法,其基本思想是将待排序的数组构建成一个大(小)顶堆,然后依次取出堆顶元素,再调整剩余元素,重复此过程直至排序完成。
下面是一个使用Python编写的堆排序代码示例:
```python
# 构建大顶堆
def heapify(arr, n, i):
largest = i # 初始化最大值为根节点
left = 2 * i + 1
right = 2 * i + 2
# 左子节点比根节点大
if left < n and arr[left] > arr[largest]:
largest = left
# 右子节点比当前最大值大
if right < n and arr[right] > arr[largest]:
largest = right
# 如果最大值不是根节点,则进行交换,并继续调整子节点
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[i], arr[0] = arr[0], arr[i] # 将最大值放到数组末尾
heapify(arr, i, 0) # 调整剩余元素为大顶堆
# 测试代码
arr = [6, 3, 8, 2, 9, 1]
heap_sort(arr)
print("排序结果:", arr)
```
以上代码中,`heapify`函数用于调整以`arr[i]`为根节点的子树为大顶堆,`heap_sort`函数则通过构建初始大顶堆和重复调整堆的过程实现堆排序。最后,通过调用`heap_sort`函数对输入的数组进行排序,并打印排序结果。
python堆排序代码
### 回答1:
很高兴回答您的问题。Python堆排序的代码如下:def heapify(arr, n, i):
largest = i # 初始化最大值
l = 2 * i + 1 # 左子节点
r = 2 * i + 2 # 右子节点
# 找出最大的节点
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
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[i], arr[0] = arr[0], arr[i] # 交换
heapify(arr, i, 0)
arr = [ 12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print ("排序后:")
for i in range(n):
print ("%d" %arr[i]),
### 回答2:
堆排序(Heap Sort)是一种基于二叉堆数据结构的排序算法。它的基本思想是将待排序的序列构建成一个大顶堆(或小顶堆),然后将根节点与最后一个节点交换位置,再对剩下的n-1个节点重新构建堆,依此类推,直到完成排序。
以下是Python实现堆排序的代码:
```python
# 调整堆,使其满足大顶堆的性质
def heapify(arr, n, i):
largest = i # 初始化最大值为根节点
left = 2 * i + 1
right = 2 * i + 2
# 如果左子节点存在且大于根节点,则更新最大值
if left < n and arr[i] < arr[left]:
largest = left
# 如果右子节点存在且大于根节点和左子节点,则更新最大值
if right < n and arr[largest] < arr[right]:
largest = right
# 如果最大值不是根节点,则交换根节点和最大值,并继续调整堆
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[i], arr[0] = arr[0], arr[i] # 交换
heapify(arr, i, 0)
return arr
# 测试代码
arr = [9, 5, 2, 8, 3, 1, 6]
sorted_arr = heapSort(arr)
print(sorted_arr)
```
上述代码中,`heapify()`函数用于调整堆,保持大顶堆的性质。`heapSort()`函数首先构建大顶堆,然后通过循环将堆顶元素与最后一个元素交换,并重新调整堆,最终得到有序序列。测试代码中打印输出的是排序后的序列。
需要注意的是,在堆排序中,序列的索引是从0开始的,因此在计算左子节点和右子节点索引时需要做相应的调整。此外,最后一个非叶子节点的索引是`(n // 2 - 1)`。
### 回答3:
请看以下Python堆排序的代码:
```python
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[i] < arr[left]:
largest = left
if right < n and arr[largest] < arr[right]:
largest = right
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[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
print("排序后的数组:")
for i in arr:
print("%d" % i)
```
上述代码实现了堆排序算法。首先,定义了一个`heapify`函数来构建最大堆,该函数接受三个参数:`arr`表示待排序的数组,`n`表示数组的长度,`i`表示根节点的索引。`heapify`函数通过比较根节点与其左右子节点的大小关系,将最大值交换至根节点,然后递归调用`heapify`函数来对交换后的子节点进行调整。其次,定义了`heapSort`函数来实现堆排序。该函数首先将数组构建为最大堆,然后依次将堆顶元素(最大值)与最后一个元素交换,并对交换后的二叉树进行调整,重复该过程直到数组完全有序。最后,定义了一个示例数组`arr`,调用`heapSort`函数对其进行排序,并输出排序后的结果。