数据结构-排序

排序的基本概念

把一堆数据元素按照它们的关键字递增或者递减的顺序把它们重新给排列一遍

排序算法执行可视化网站

插入排序

所有的辅助变量所需要的空间都是常数级的，和问题规模n没有关系

之前设计的折半查找的规则，当我们找到一个和目标关键字相同的关键字的时候，就会停止折半查找。

但是在这，为了保证插入排序的稳定性，当发现一个和当前处理元素值相同的元素，还应该往这个元素的右半区间内继续查找来确定当前元素的插入位置

希尔排序（Shell Sort）

记得耐下性子自己去分析一下

直接把i++换成i+=d也可以噢~【应该可以实现第二趟的时候把同一子表4个直接排好】有待研究

这个ppt动画是真的强

随机存取

所谓的代码就是对处理问题的逻辑用计算机语言把它描述一遍，仅此而已

算法的逻辑缕清了，代码就是逻辑的一个外化体现而已

交换排序

基于“交换”的排序：根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置

冒泡排序

如果说两个元素的值相同的话，不应该交换他们两的位置，这么做可以保证算法的稳定性

这个代码是从后往前冒泡，自己实现从前往后冒

如果一趟冒泡排序中没有发生任何一次交换，就可以提前让算法结束

冒泡中每一趟的处理都会使一个最大或者最小的元素确定最终位置

快速排序

每一次都会使一个中间元素确定它的最终位置

记录#96是为了一会儿partition函数，return返回之后，能够知道接下来应该执行的是哪一行

对快排算法，要研究其时间和空间复杂度，都必须研究它的递归层数、递归深度有什么样的规律

我哩个豆

快速排序算法的实现，分为两部分：分区函数 Partition() 和主排序函数 QuickSort()。

Partition() 函数详解

功能

Partition() 函数的主要功能是对数组 A[] 中指定范围 [low, high] 内的元素进行划分，以第一个元素作为枢轴（pivot），并将数组划分为两个部分：一部分包含小于等于枢轴的元素，另一部分包含大于枢轴的元素。最后，函数返回枢轴的最终位置索引。

参数说明

int A[]: 待排序的整型数组。
int low: 数组的起始索引。
int high: 数组的结束索引。

实现步骤

初始化 pivot = A[low]，即将数组的第一个元素设为枢轴。
使用双指针法，分别从两端向中间扫描：
当 low < high && A[high] >= pivot 时，high--；否则，跳出内层循环。
当 low < high && A[low] <= pivot 时，low++；否则，跳出内层循环。
在退出内层循环后，交换 A[low] 和 A[high] 的值，使枢轴右侧的元素均大于枢轴，左侧的元素均不大于枢轴。
返回 low，即枢轴的最终位置。

QuickSort() 函数详解

功能

QuickSort() 函数实现了快速排序的核心逻辑，通过递归调用自身来对数组的不同子区间进行排序。

参数说明

int A[]: 待排序的整型数组。
int low: 数组的起始索引。
int high: 数组的结束索引。

实现步骤

判断终止条件：若 low >= high，则直接返回，不再继续分割。
否则，调用 Partition(A, low, high) 获取枢轴的最终位置 pivottpos。
分别对枢轴左侧 (low 至 pivottpos - 1) 和右侧 (pivottpos + 1 至 high) 的子数组进行递归排序。

递归工作栈解析

递归过程中，每一次递归调用都会创建一个新的栈帧，保存当前函数的状态（如局部变量、参数等）。随着递归深度增加，栈帧逐级嵌套，形成了递归的工作栈。

示例流程

假设我们要对数组 [4, 2, 5, 1, 3] 进行快速排序，初始调用 QuickSort(A, 0, 4)。

第一次调用 QuickSort(A, 0, 4)：

调用 Partition(A, 0, 4)，返回枢轴位置 pivottpos。
继续递归调用 QuickSort(A, 0, pivottpos - 1) 和 QuickSort(A, pivottpos + 1, 4)。

对左侧子数组 [2, 1] 进行排序：

调用 QuickSort(A, 0, 0)，因 low == high 直接返回。
调用 QuickSort(A, 1, 1)，同样因 low == high 直接返回。

对右侧子数组 [5, 3] 进行排序：

调用 QuickSort(A, 2, 2)，因 low == high 直接返回。
调用 QuickSort(A, 3, 3)，同样因 low == high 直接返回。

至此，整个数组已完全排序完毕，递归调用逐步返回，直到最初调用的 QuickSort(A, 0, 4) 结束。

总结

快速排序通过递归地应用分区策略，有效地将大规模排序问题分解成较小规模的问题，直至问题足够小可以直接解决为止。递归工作栈帮助跟踪每一级递归调用的状态，确保排序过程有序进行。

ok递归、函数、指针知道自己很差了Qwq

ok呀，边学边补，补一下递归算法

什么是递归调用栈

当一个函数进行递归调用时，系统会为每一次的函数调用开辟一块独立的内存空间来存储该次调用的相关信息，如局部变量、参数值以及函数执行到的位置等。这些为每次递归调用所分配的内存空间就构成了一个栈结构，被称为递归调用栈。

递归调用栈的工作原理

入栈操作：

当一个函数开始执行递归调用时，当前函数的执行状态（包括局部变量的值、当前执行到的代码行等信息）会被压入递归调用栈。这就好比在栈顶添加了一个新的元素。
例如，有一个计算阶乘的递归函数 factorial(n)，当我们调用 factorial(5) 时，首先会将 factorial(5) 的执行状态压入栈。然后在函数内部，如果 n > 1，会继续调用 factorial(4)，此时 factorial(4) 的执行状态又会被压入栈，位于 factorial(5) 的执行状态之上。

出栈操作：

当一次递归调用完成（即遇到递归终止条件并执行完相应的返回操作）后，对应的函数执行状态会从递归调用栈中弹出。这类似于从栈顶取出一个元素。
继续以 factorial 函数为例，当 factorial(1) 的计算完成并返回结果后，它的执行状态就会从栈顶弹出。然后程序会回到上一次调用它的地方（也就是 factorial(2) 中调用 factorial(1) 的位置）继续执行，此时 factorial(2) 的执行状态成为栈顶元素，接着它会完成后续的计算并可能再次进行出栈操作，如此反复直到整个递归过程结束。

递归调用栈的示例：斐波那契数列计算

以下是一个用递归方式计算斐波那契数列的例子，来更直观地说明递归调用栈的工作情况：

python
def fibonacci(n):if n == 0 or n == 1:return nreturn fibonacci(n - 1) + fibonacci(n - 2)print(fibonacci(5))
当我们调用 fibonacci(5) 时：

首先，fibonacci(5) 的执行状态被压入递归调用栈。
因为 n!= 0 且 n!= 1，所以它会分别调用 fibonacci(4) 和 fibonacci(3)，这两个函数的执行状态依次被压入栈，此时栈顶元素是 fibonacci(3)，栈的情况大致如下（从栈顶向下看）：
fibonacci(3)
fibonacci(4)
fibonacci(5)
对于 fibonacci(3)，又会继续调用 fibonacci(2) 和 fibonacci(1)，它们的执行状态也被压入栈。同样，fibonacci(4) 会调用 fibonacci(3)（这里是另一次对 fibonacci(3) 的调用，与前面的不同实例）、fibonacci(2) 等，不断有新的执行状态压入栈。
当递归调用到达 fibonacci(0) 或 fibonacci(1) 时，满足终止条件，这些函数会返回结果并开始出栈操作。例如，当 fibonacci(0) 返回 0 后，它的执行状态出栈，程序回到调用它的地方（比如 fibonacci(1) 中调用 fibonacci(0) 的位置）继续执行，然后 fibonacci(1) 也返回结果并出栈，依次类推，直到整个 fibonacci(5) 的计算完成，递归调用栈被清空。

递归调用栈的深度限制

在实际应用中，递归调用栈的大小是有限制的。不同的编程语言和运行环境可能有不同的默认栈大小设置。如果递归调用的层数太深，可能会导致栈溢出（Stack Overflow）错误。

例如，在上述斐波那契数列的递归计算中，如果我们尝试计算 fibonacci(1000)（具体的临界值因环境而异），很可能会因为递归调用栈太深而出现栈溢出问题，因为每一次递归调用都会增加栈的深度，而计算较大的斐波那契数需要大量的递归调用。

为了避免栈溢出，可以考虑使用迭代的方式来实现类似功能（如用循环计算斐波那契数列），或者对递归进行优化（如使用尾递归优化，不过并非所有语言都支持尾递归优化且其实现方式也因语言而异）。

递归调用栈是理解递归函数执行机制的关键，它清晰地展示了递归过程中函数调用的层次和状态保存与恢复的过程。