分类

• 归并排序

• 快速排序

归并排序

时间复杂度

流程：

代码：

快速排序

时间复杂度

• 影响因素：依赖于基准元素的选择

• 最坏情况的时间复杂度为 O(n^2)，这通常发生在基准元素每次选取时都是最小或最大的元素，如已排序的数组。

• 平均情况的时间复杂度为 O(nlogn)，这是在基准选择较为平均的情况下。

• 最好情况的时间复杂度同样是 O(nlogn)，在理想的基准选择下发生，即基准每次都能将数组均等分割。

流程：

代码:

应用——快速选择：

时间复杂度

• 最坏情况的时间复杂度为 O(n^2)，这类似于快速排序，在基准选择不佳的情况下发生。

• 平均情况的时间复杂度为 O(n)，因为它通常不需要遍历整个数组。

• 最好情况的时间复杂度也是 O(n)，在每次递归都能完美切分数组的情况下实现。

代码