快速排序

• V3.0版本的时间复杂度$O(NlogN)$，V1.0和V2.0版本的时间复杂度为 $O(N^2)$

V1.0版本

先以最后一个数为标的排序，左侧为小于区域，右侧为大于区域，再将该标的和右侧区域第一个数字换位（可以肯定的是该标的值一定是在这里），以这里为分界，两边分别递归重复上述步骤。

V2.0版本

2.0版本：比快排1.0版本多一个等于区域，也同样交换标的和大于区域的第一个值，后以该等于区域边界为两边的界，重复递归。（和荷兰国旗问题设置和思路一致）

V1.0和V2.0的速度比较

2.0版本相对1.0版本更快一点。两者的时间复杂度都是$O(N^2)$，最差的例子都是有序数组，最后的标的都是当前数组最大值.(划分值找的很不好就会造成最差情况，而划分值取到中点，就是$O(NlogN)$（最好情况）

V3.0版本

标的值随机选，之后和最后位置的换，重复2.0版本。

3.0版本的随机性有什么用？

3.0版本引入随机，而随机就会涉及到概率（即无法人为构建最差例子了，而1.0和2.0可以），无论是找到最好还是最差或者其他，他们都是等概率的，这样就会降低其时间复杂，其时间复杂度的计算为长期期望。其时间复杂度为$O(NlogN)$。 其空间复杂度也是 $O(logN)$ 级别的，计算也是涉及到了概率累加（对于递归的，要看递归最多能加到几层）

V3 版本实现：

几个坑：

1. 必需用 self. num 实现，即原地改变位置。如果递归函数返回返回值，会非常乱，而且判断的东西非常多，很复杂，所以为了简单，直接原地改变。
2. V1.0 和 2.0 都是两个区域的版本，即只有大于和小于，我复现不出来，因为如果不把等于的放在一起，会爆栈，一直递归。因此，只学 3.0，不学 2.0
3. 注意区间的包含关系

from random import randint
class Solution:
    def targetIndices(self, nums: List[int], target: int) -> List[int]:
        self.nums = nums  
        self.my_sort(0, len(self.nums)-1)
        return self.nums
 
    def my_sort(self, left, right):
        if left < right:
            pivot_idx = randint(left, right) # 随机选择标的
            self.nums[right], self.nums[pivot_idx] = self.nums[pivot_idx], self.nums[right] # 标的交换到最后
            # 根据pivot值进行分区，得到分区边界
            (p1, p2) = self.parti(left, right)
            # 分别递归大于区域和小于区域，等于区域不用管了。
            if p2 <= right:  # 如果没有大于区，则p2 = right + 1, 因此需要判断
                self.my_sort(p2, right)
            if p1 >= left:
                self.my_sort(left, p1)
    
    def parti(self, left, right):
        pivot = self.nums[right]
        p1 = left - 1 # 小于区域，含p1：小于区域[left, p1]，两边都含
        p = left      # 正常指针
        p2 = right+1  # 大于区域，含p2：[p2, right]，两边都含
        while(p < p2): # 不用p2，因为p2是大于区域的边界，且含在大于区域中
            if self.nums[p]<pivot:
                self.nums[p1+1], self.nums[p] = self.nums[p], self.nums[p1+1]
                p1 += 1
                p += 1
            elif self.nums[p] > pivot:
                self.nums[p], self.nums[p2-1] = self.nums[p2-1], self.nums[p]
                p2 -= 1
            else:
                p += 1
        return (p1, p2)  # 返回两个边界