快速排序之3路快排

3路快排对比常规快排

常规快排就是2路快排，或叫双路快排，通过下界low指针和上界high指针的夹逼直至重合，指向基元base的目标位置，将待排数组分为 <=基元 以及 >基元 这两部分

3路快排的思想是将待排数组划分为 <、=以及> 基元 3个部分，即将2路排序的<=部分 一分为二形成<和=基元两部分，加上>基元部分，共三部分
优点：因为=部分无需参与后续的排序，所以相比2路排序，3路排序减少了很多不必要的工作。在面对大量重复元素的排序时，3路快排具有较明显的优势

3路快排的实现思路

| 小于基元（乱序） | 等于基元 | 大于基元（乱序） |

显然，需要对小于基元部分和大于基元部分继续进行3路快排，等于基元部分可以不用管了

那么，需要一个指针lt指向小于基元部分的右边界，还需要一个指针gt指向大于基元部分的左边界，以标记这两块需要继续排序部分的边界

• 1.初始化lt和gt指针，分别指向待排数组的头尾之外
• 2.使用指针i从前往后扫描数组的每一个元素，直到i指针碰到gt指针为止
  • 2.1 当前元素小于base，将当前元素与等于base部分的第一个元素交换位置 + lt自增1，然后i自增继续向前扫描
  • 2.2 当前元素等于base，lt、gt都不变，i自增继续向前扫描即可
  • 2.3 当前元素大于base，将当前元素与gt指向的前一个元素交换位置 + gt自减1。然后i无需自增继续向前扫描，因为i指向的元素被换了，要对换过来的元素做一次判断

# 返回less than base部分的上界和greater than base部分的下界
def _partition_3(self, nums, left, right):
        # 选择基元
        base = nums[left]
        # lt ，less than，严格小于，初始时指向头之外（因为还没有严格小于base的部分）
        lt = left - 1
        # gt，great than，严格大于，初始指向末尾之外（因为还没有严格大于base的部分）
        gt = right + 1
        # i 指针，用于遍历数组base以后的元素
        i = left + 1
        # 开始遍历---i与gt夹逼
        while i < gt:
            # 当前元素小于base，将当前元素与等于base部分的第一个元素交换位置 + lt自增1
            if nums[i] < base:
                # lt自增1，此时指向了等于base部分的第一个元素
                lt += 1
                # 当前扫描的元素与等于base部分的第一个元素交换位置
                nums[i], nums[lt] = nums[lt], nums[i]
                i += 1
            
            # 当前元素等于base，lt\gt都不变
            elif nums[i] == base:
                i += 1
            # 当前元素大于base，gt自减1
            else:
                gt -= 1
                # 交换元素
                nums[i], nums[gt] = nums[gt], nums[i]
        # 打印结果
        print(nums)
        print(lt, gt)
        return lt, gt