为什么对已排序数组执行quicksort时会出现n1=0、n2=n-1的情况？

这个规律成立的前提是你使用的快速排序实现默认选择数组端点（最左/最右元素）作为基准值（pivot），对应的拆分逻辑如下：

• 快排每一轮拆分的核心是：选一个基准值，将当前区间内所有小于基准值的元素移到基准左侧，大于的移到右侧，拆分完成后基准值就落在自己的最终排序位置上，不会再参与后续的拆分计算
• 当输入数组本身已经是完全有序（正序/逆序）时，你选的端点基准值天然就是当前整个区间的最小值或最大值

举个具体的正序数组例子，初始数组长度为n，默认选最左元素为基准：

1. 第一轮拆分时，基准是整个数组的最小值，拆分后左侧子区间长度为0，仅基准元素占1个位置，剩下所有n-1个元素都落在右侧子区间，也就是你说的n2 = n-1
2. 接下来处理长度为n-1的右子区间，它本身也是有序的，同样选最左元素作为基准，拆分后右子区间长度变为(n-1)-1 = n-2
3. 以此类推，每一轮拆分后的子区间长度都会减1，直到区间长度为1终止。

你附图里的拆分过程完全符合上述逻辑，这种场景就是快速排序的最坏时间复杂度场景，总时间复杂度会达到O(n²)，因为每一轮拆分需要遍历当前区间的所有元素，总遍历次数为等差数列求和：n + (n-1) + (n-2) + ... +1 = n(n+1)/2，属于平方级复杂度。

内容的提问来源于stack exchange，提问作者algor