数据结构和算法(3)

递归、快速排序

递归

函数调用自身，就称为递归。
递归看起来很简单，其实一点也不一般。
它可以代替循环,例如我们要计算某个数的阶乘

1
2
3
4
5
6

int jiecheng(int num){
    if(num == 1)
       return 1;
    else
       return num * jiecheng(num-1);
    }

怎么看懂递归？

就拿上述代码举例，一步一步分析。

• 假如我们想计算4的阶乘jiecheng(4)
• 首先判断传进来的数字是否为1，这里显然不是，而这个条件又很重要，它决定着不再进行递归，这个情形被称为基准情形
• 接着将这个数和jiecheng(3)相乘
• 然后jiecheng(3)再重复上述步骤
• 直到数字为1，停止递归，返回jiecheng(4)的值

通过以上的流程，我们可以总结一下：
1、在一个递归当中，一定会有基准情形，它决定着递归什么时候该结束
2、通过基准情形，我们只需要知道调用一次时函数在干什么，便可知道整个递归在干什么

计算机中的递归

计算机会用栈来记录每个调用中的函数，这个栈叫做调用栈

计算机最开始会调用jiecheng(4),之后会调用jiecheng(3),计算机为了使自己记得还在jiecheng(4)中，会将此事压入到调用栈中。以此类推，接着压入jiecheng(3)，直到调用到jicheng(1)时，遇到基准情形，不需要再调用便可以返回了。接着计算机再一个一个处理栈顶的事件，直到整个程序完成。

而无限递归的程序会一直将同一方法压入到调用栈上，直到计算机的内存空间不足，最终导致栈溢出的错误。

在现实中，大多数编程语言都自带数组排序的函数，其中很多都是采用的快速排序，其中便运用了递归来给算法进行提速。这里我们通过了解它的原理，来更深入的理解递归。

分区

分区（Partition）是快速排序中的一个核心概念，它将数组分解为较小的子数组，从而逐步实现整个数组的排序。

1、选择一个基准值（Pivot）：

基准值的选择有多种方法，常见的有：

• 选择数组的第一个元素。
• 选择数组的最后一个元素。
• 选择数组的中间元素。
• 随机选择一个元素。
• 三数取中法（取数组的第一个、中间和最后一个元素的中值作为基准值）。

基准值的选择会影响分区的效率和算法的性能。理想情况下，基准值应该是数组的中值，这样可以将数组均匀地分为两部分。

2、 霍尔（Hoare）分区法

这是快速排序的经典分区方法，由算法发明者C. A. R. Hoare提出。
步骤：

• 选择一个基准值。
• 初始化两个指针，i指向数组的起始位置，j指向数组的末尾位置。
• 从j开始向左扫描，找到第一个小于或等于基准值的元素，就停下来。
• 然后从i开始向右扫描，找到第一个大于基准值的元素，就停下来。
• 将基准值与i、j位置的元素交换
• 重复上述步骤，直到两指针重合，或左指针 到右指针右边。
• 将基准值和左指针的值交换位置，完成分区

为了方便理解，我们用AI生成一段形象点的例子：

• 假设水果摊上的水果价格如下（从左到右）
  [12, 7, 5, 11, 9, 8]

• 这里我们选择基准价格为8元。

• 初始状态：
  [12, 7, 5, 11, 9, 8]
  左指针 i 在第一个水果的左边，右指针 j 在最后一个水果的右边。

• 左指针扫描：
  从左向右扫描，找到第一个价格大于8元的水果，是12元的水果。
  左指针 i 停在12的位置。

• 右指针扫描：
  从右向左扫描，找到第一个价格小于或等于8元的水果，是5元的水果。
  右指针 j 停在的位置。

• 交换水果：
  因为两个指针都停住了，所以交换5元的水果和12元的水果，水果摊变为：
  [5, 7, 12, 11, 9, 8]

• 继续扫描：
  左指针继续向右扫描，找到12元的水果。
  此时左指针和右指针重合。我们再比较左指针和基准值，12>8，所以与基准值交换
  交换这两个水果，水果摊变为：
  [5, 7, 8, 11, 9, 12]
  虽然并没有完全排好序，但是基准值已经处于正确的位置上。左边的都小于基准值，右边的都大于基准值。

快速排序

快速排序建立在分区之上，运作方式如下：
1、把数组分区，将基准值移到正确的位置上
2、对基准值左右两个子数组递归地重复第一、二步，两子数组都各自分区，并形成各自的基准值以及由基准值分隔的更小的子数组。以此类推
3、当分出的子数组长度为0或1时，即达到基准情形，无需进行下一步的操作。
可以自己推理下上述的分水果的例子，这里就不过多的赘述了。

快速排序的效率

• 平均情况
  在平均情况下，快速排序的时间复杂度为 O(n log n)。这是因为每次分区操作都将数组分成两个大致相等的部分，递归树的深度为 log n，每一层的分区操作总时间为 O(n)。所以总的时间复杂度为 O(n log n)。例如，对于一个长度为 8 的数组，分区操作将数组分成两个长度为 4 的子数组，然后再分别对这两个子数组进行分区操作，分成四个长度为 2 的子数组，以此类推。每一层的分区操作总共需要比较和交换的次数与数组长度成正比，而递归树的深度为 log₂8 = 3 层。

• 最好情况
  最好情况下，每次分区都能将数组均匀地分成两个相等的部分。此时，时间复杂度是 O(n log n)。这是快速排序在理想情况下的表现，效率非常高。

• 最坏情况
  最坏情况下，每次分区操作只能将数组分成一个大小为 1 和一个大小为 n - 1 的子数组。例如，当数组已经有序或完全逆序时，如果选择数组的第一个或最后一个元素作为基准值，就会出现这种情况。每一层的分区操作时间为 O(n)，所以总的时间复杂度为 O(n²)。
  例如，对于一个已经从小到大有序的数组，每次分区只能将最后一个元素与基准值交换，然后递归地对剩下的 n - 1 个元素进行排序，这种情况下快速排序的效率会大幅下降

所以，我们可知，决定快速排序的核心因素就是选好基准值，基准值选的恰到好处，算法的效率便会大大提升。