三路快排

1. 回忆快排

快排的核心思想是，每次选取一个基准值，然后将数组分成两部分，一部分小于基准值，一部分大于基准值，然后递归处理这两部分。

class Solution:# 快速排序def paviot(self,nums:List[int],lo:int,hi:int):# 随机选取一个值作为pivot，避免退化为O(n^2)         i = random.randint(lo,hi) nums[i],nums[hi] = nums[hi],nums[i] pivot = nums[hi]less = great = lowhile(great < hi):if nums[great] < pivot:  # 如果当前值小于pivot（pivot为最后一个值）nums[less],nums[great] = nums[great],nums[less] # 如果存在大量重复值，这里会导致大量交换,导致超时less += 1great += 1nums[less],nums[hi] = nums[hi],nums[less]return lessdef quickSort(self,nums:List[int],lo:int,hi:int):if lo > hi:returnindex = self.paviot(nums,lo,hi)self.quickSort(nums,lo,index-1)self.quickSort(nums,index+1,hi)def sortArray(self, nums: List[int]) -> List[int]:self.quickSort(nums,0,len(nums)-1)return nums

• 快排在处理大量重复值的时候，会导致大量的交换，导致超时。
• 如果数组本身就是有序的，那么快排的时间复杂度会退化到O(n^2)。

2. 三路快排

三路快排的核心思想是，每次选取一个基准值，然后将数组分成三部分，一部分小于基准值，一部分大于基准值，一部分等于基准值，然后递归处理这三部分。

相比于快排，三路快排在处理大量重复值的时候，不会导致大量的交换，因此不会导致超时。

from cn.Python3.mod.preImport import *
import random
# @test([5,2,3,1])=[1,2,3,5]
# @test([5,1,1,2,0,0])=[0,0,1,1,2,5]
class Solution:# 三路快排def threeway_quick_sort(self,nums:List[int],lo:int,hi:int):if lo >= hi:returnj = random.randint(lo,hi)nums[j],nums[hi] = nums[hi],nums[j]pivot = nums[hi]i = loless = logreat = hiwhile(i<=great):if nums[i] < pivot:nums[i],nums[less] = nums[less],nums[i]less += 1i += 1elif nums[i] > pivot:nums[i],nums[great] = nums[great],nums[i]great -= 1else:i += 1self.threeway_quick_sort(nums,lo,less-1)self.threeway_quick_sort(nums,great+1,hi)def sortArray(self, nums: List[int]) -> List[int]:self.threeway_quick_sort(nums,0,len(nums)-1)return nums