快速排序

快速排序

快速排序最差情况

每一轮的partition没有起到作用，理想的分段是将数组均分，现在是全部都在一遍 所以partition是失败的

image

partition示意图

image

弊端

容易出现的失败的partition 标定点位于数组的两边

image

双路partition示意图

对于相等的元素也会停下来 执行交换 保证了partition的性能 标定点可以位于中间

等于pivot的元素分散到了左右两个部分

代码中的细节：

• 为啥左右指针可以相等？？

  还是需要明确变量的定义

  我们始终维护的是 [l+1,i-1]<v 对于arr[i]不明确它的大小

  同样 arr[j+1,r]>v (下图写错了) 对于arr[j]不明确它的大小

  所以当i==j时 我们还没有去判断arr[i] 怎么能就此结束这个数有可能大于v也有可能小于v

  这两种情况显然对应不同的状况 所以还需要一轮的判断决定这个数是大于v还是小于v

• 为啥nums[i] < pivot不加等号

  • 对于相等的元素依然需要交换 因为对于出现大量重复元素的情况，保证了标定点可以位于中间而不是两边

while i <= j and nums[i] < pivot: # 这里不加等于号
    i += 1

image

三路快速排序示意图

很好的解决等于的元素

image

def quickSort2Ways(nums):
    def quickSort(left, right):
        if left >= right:
            return
        parti = partition2Ways(left, right)
        quickSort(left, parti - 1)
        quickSort(parti + 1, right)

    def partition2Ways(left, right):
        pivot = nums[left]
        l, r = left + 1, right  # l r 指向的位置都是当前不确定大于还是小于的位置
        # while True:
        #     while l <= r and nums[l] < pivot:
        #         l += 1
        #     while l <= r and nums[r] > pivot:
        #         r -= 1
        #     if l > r:  # 终止条件是两指针交叉
        #         break
        #     else:
        #         nums[l], nums[r] = nums[r], nums[l]
        #         l += 1
        #         r -= 1

        # 这里为啥要加等号 因为num[l] 这个数字没有判断过大小 事还没办完
        while l <= r: # 拆分成三种基本情况
            if nums[l] < pivot:
                l += 1
            elif nums[r] > pivot:
                r -= 1
            else:
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
                r -= 1
        nums[left], nums[r] = nums[r], nums[left]
        return r

    return quickSort(0, len(nums - 1))

def quickSort3Ways(nums):
    def quickSort(left, right):
        if left > right:
            return
        lt, gt = partition3Ways(left, right)
        quickSort(left, lt)
        quickSort(gt, right)

    def partition3Ways(left, right):
        pivot = nums[left]
        # [left+1,lt] < v  [lt+1, i-1] = v 定义i是一个还没有判断大小的数 [gt,right] > v
        lt, i, gt = left, left + 1, right + 1  # 初始化需要保证上面的定义成立
        # while True:
        #     while i < gt and nums[i] < pivot:
        #         nums[lt + 1], nums[i] = nums[i], nums[lt + 1]
        #         lt += 1
        #         i += 1
        #     while i < gt and nums[i] == pivot:
        #         i += 1
        #     while i < gt and nums[i] > pivot:
        #         nums[gt - 1], nums[i] = nums[i], nums[gt - 1]
        #         gt -= 1
        #         i += 1
        #     if i >= gt:
        #         break

        while i < gt: #  这里为什么不需要等号 因为gt是闭区间 nums[gt]这个数字已经判断过大小
            if nums[i] < pivot:
                nums[lt + 1], nums[i] = nums[i], nums[lt + 1]
                lt += 1
                i += 1
            elif nums[i] == pivot:
                i += 1
            else:
                nums[gt - 1], nums[i] = nums[i], nums[gt - 1]
        nums[left], nums[lt] = nums[lt], nums[left]
        lt -= 1
        return lt, gt