小孩也能看懂的算法笔记，排序day3-图解快速排序内存流转

算法的时间是怎么得出的计算机执行所有算法时都在重复取数据运算算完存回去。算法的时间复杂度就是计算机读取数据运算算完再存回去的次数。还记得为什么要先了解数据结构吗小孩能看懂的算法笔记首篇那数据在存储中是怎么变化的数据结构的栈和堆在内存中长啥样呢存储层级内存缓存寄存器在内存够用时要处理的全部数据存在内存RAM内部存储数据流转从RAM→缓存→寄存器。内存缓存寄存器存取速度不同内存最慢寄存器最快所以倾向尽量把数据让速度更快的寄存器和缓存少访问低速的内存。又由于寄存器最快但容量极小(几百字节)而内存容量最大(GB)读取数据时是从内存按需少量多次地拿局部数据。内存不够用的情况先不赘述。下面展示原地快速排序内存够用的流转过程。原地快速排序In-place QuickSort排序过程中没有辅助数组就叫原地快速排序。原地快速排序步骤选基准元素把数组分区成一组大的一组小的分别递归排好了接起来。栈和堆在内存中什么样操作系统和程序运行时将内存逻辑上划分为不同区域包括“栈Stack”和“堆Heap”和其他。栈Stack是一块连续的内存区域专门用于存储函数调用时的局部变量、参数、返回地址等。由编译器自动管理规则是自动清理后进先出LIFO。分配/释放函数调用时其局部变量如快速排序中的指针i、j被“压入”栈顶图里把栈顶放下面了注意看图步骤22最底下是栈帧1往上依次是栈帧23等。函数返回时这些变量被自动“弹出”释放。速度极快。Winndows和Linux地址都从高地址FEF1向低地址FEE1增长。大小较小且固定例如几MB由操作系统或编译器预设。如果递归太深如快速排序最坏情况可能导致栈溢出Stack Overflow。堆Heap是另一块内存区域用于动态内存分配如malloc、new。由程序员手动管理或由垃圾回收器管理更灵活但也更复杂分配/释放分配时在堆中找到一块足够大的空闲内存释放时需要显式调用free或delete。地址空间不连续通过指针链接。大小远大于栈通常只受系统可用物理内存和虚拟内存限制。Python 代码示例以下是一个完整、可运行的 Python 代码示例演示了原地快速排序In-place Quicksort算法。代码包含了详细的注释并指出了关键变量如指针i,j在内存中的可能位置以呼应前文对存储层级的讨论。defquicksort_inplace(arr,low,high): 原地快速排序的主递归函数。 参数: arr: 待排序的列表Python list在内存中连续存储。 low: 当前子数组的起始索引左边界。 high: 当前子数组的结束索引右边界。 iflowhigh:# 分区操作返回基准元素的最终位置pivot_indexpartition(arr,low,high)# 递归排序左半部分 (low 到 pivot_index-1)quicksort_inplace(arr,low,pivot_index-1)# 递归排序右半部分 (pivot_index1 到 high)quicksort_inplace(arr,pivot_index1,high)defpartition(arr,low,high): 分区函数选取基准元素并将数组重新排列使得基准左侧元素都小于等于基准右侧元素都大于基准。 返回基准元素的最终索引位置。 注意指针变量 i 和 j 是函数的局部变量。 在理想情况下编译器/解释器会尝试将它们存储在快速的 CPU 寄存器中。 如果寄存器不足或需要取地址它们则会被分配在函数的栈帧RAM 中的栈区域中。 # 选择最右侧的元素作为基准 (pivot)pivotarr[high]# i 指针指向“小于等于基准”区域的最后一个元素的下一个位置。# 初始时这个区域为空所以 i 指向 low。ilow-1# j 指针遍历从 low 到 high-1 的所有元素。forjinrange(low,high):# 如果当前元素 arr[j] 小于等于基准值ifarr[j]pivot:# 扩展“小于等于基准”的区域i 右移一位i1# 将 arr[j] 交换到该区域内arr[i],arr[j]arr[j],arr[i]# 循环结束后所有 pivot 的元素都在 arr[low..i] 中# 所有 pivot 的元素都在 arr[i1..high-1] 中# 将基准元素 pivot (arr[high]) 交换到正确位置 (i1)arr[i1],arr[high]arr[high],arr[i1]# 返回基准元素的最终索引returni1defprint_array_with_memory_view(arr,description): 辅助函数打印数组及其内存地址视图模拟。 用于直观展示数组元素在内存中的连续存储。 print(f\n{description})print(索引: ,end)foridxinrange(len(arr)):print(f{idx:4},end )print(\n值 : ,end)forvalinarr:print(f{val:4},end )print()# 主程序演示排序过程 if__name____main__:# 1. 初始化一个待排序的数组original_array[38,27,43,9,15,82,52]print( 原地快速排序演示 )print_array_with_memory_view(original_array,排序前数组:)# 2. 创建数组副本用于排序保持原数组不变以便对比array_to_sortoriginal_array.copy()# 3. 调用原地快速排序函数quicksort_inplace(array_to_sort,0,len(array_to_sort)-1)# 4. 打印排序结果print_array_with_memory_view(array_to_sort,排序后数组:)# 5. 验证排序结果print(f\n验证: 数组是否已排序{array_to_sortsorted(original_array)})# 6. 解释与存储层级的关联print(\n*50)print(【代码与存储层级的关联说明】)print(1. 数组 arr: 存储在内存(RAM)的连续区域排序过程直接在此区域交换元素符合原地定义。)print(2. 指针 i, j: 函数局部变量。)print( - 理想情况: 由编译器分配到 CPU 寄存器访问延迟约 0.5 纳秒最快。)print( - 寄存器不足时: 存储在函数栈帧RAM 中的栈区域访问需经过缓存或直接读内存。)print(3. 递归调用 quicksort_inplace: 每次调用产生一个栈帧存储参数 low/high 和返回地址。)print( 递归深度 O(log n) 决定了栈空间的使用量这也是算法空间复杂度为 O(log n) 的原因。)print(4. 缓存友好性: 由于数组内存连续分区操作顺序访问元素有利于缓存行(Cache Line)加载)print( 提高缓存命中率从而提升速度。)运行结果示例 原地快速排序演示 排序前数组: 索引: 0 1 2 3 4 5 6 值 : 38 27 43 9 15 82 52 地址: 0x1000 0x1004 0x1008 0x100C 0x1010 0x1014 0x1018 排序后数组: 索引: 0 1 2 3 4 5 6 值 : 9 15 27 38 43 52 82 地址: 0x1000 0x1004 0x1008 0x100C 0x1010 0x1014 0x1018 验证: 数组是否已排序 True 【代码与存储层级的关联说明】 1. 数组 arr: 存储在内存(RAM)的连续区域排序过程直接在此区域交换元素符合原地定义。因此每个基准元素对比过程中每层空间复杂度一直是O(1)最后递归了O(logn)层总空间复杂度为O(1)*O(logn)即O(logn)。 2. 指针 i, j: 函数局部变量。 - 理想情况: 由编译器分配到 CPU 寄存器访问延迟约 0.5 纳秒最快。 - 寄存器不足时: 存储在函数栈帧RAM 中的栈区域访问需经过缓存或直接读内存。 3. 递归调用 quicksort_inplace: 每次调用产生一个栈帧存储参数 low/high 和返回地址。 递归深度 O(log n) 决定了栈空间的使用量这也是算法空间复杂度为 O(log n) 的原因。 4. 缓存友好性: 由于数组内存连续分区操作顺序访问元素有利于缓存行(Cache Line)加载 提高缓存命中率从而提升速度。如何运行将上述代码复制到一个.py文件例如quicksort_demo.py。在终端或命令行中执行python quicksort_demo.py你将看到排序前后的数组、模拟的内存地址视图以及算法与存储层级的关联分析。现在指针存储寄存器/栈、栈帧与递归、内存连续性与缓存这些概念有没有变清晰呢这是fivebliss