今日事项-2024年7月19日

吃透一个算法-堆排序

代码、代码注释与详细解释：

def heapify(arr, n, i):
    """
    调整堆的函数，确保堆的性质。
    
    参数:
    arr (list): 待排序的数组。
    n (int): 数组的长度。
    i (int): 当前节点的索引。
    """
    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 heap_sort(arr):
    """
    堆排序算法实现。
    
    参数:
    arr (list): 待排序的数组。
    """
    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 = [4, 10, 3, 5, 1]，我们使用堆排序对其进行排序。

1. 构建最大堆：

   • 初始数组：[4, 10, 3, 5, 1]
   • 调整后：[10, 4, 3, 5, 1]（将前四个元素调整为最大堆）
   • 继续调整：[10, 5, 3, 4, 1]（继续调整前三个元素）

2. 交换堆顶元素与最后一个元素：

   • 交换后：[1, 5, 3, 4, 10]
   • 重新调整堆：[5, 1, 3, 4, 10]

3. 重复步骤2：

   • 交换后：[4, 1, 3, 5, 10]
   • 重新调整堆：[4, 1, 3, 5, 10]（已经是有序的）

4. 最终结果：

   • 排序后的数组：[1, 3, 4, 5, 10]

中间涉及到的语法知识点：

1. 函数定义：

   • 使用def关键字定义函数。
   • 函数名和参数列表。

2. 参数传递：

   • 函数参数arr, n, i的传递。

3. 条件判断：

   • 使用if语句进行条件判断。

4. 索引计算：

   • 计算左子节点和右子节点的索引。

5. 变量赋值：

   • 使用赋值语句更新变量值。

6. 交换元素：

   • 使用元组解包进行元素交换：arr[i], arr[largest] = arr[largest], arr[i]。

7. 递归调用：

   • 函数heapify的递归调用。

8. 循环结构：

   • 使用for循环进行迭代。

9. 数组长度获取：

   • 使用len(arr)获取数组长度。

10. 数组元素访问：

    • 使用索引访问数组元素。

11. 数组元素修改：

    • 直接通过索引对数组元素进行修改。

12. 注释：

    • 使用#进行单行注释，使用"""进行多行注释。

详细讲解可以参考：姬如祎-十大经典排序算法—-堆排序（超详细）

看抓包方面的资讯

看SQL server 2014中sql语句的执行过程