三路快排
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 = lo
while(great < hi):
if nums[great] < pivot: # 如果当前值小于pivot(pivot为最后一个值)
nums[less],nums[great] = nums[great],nums[less] # 如果存在大量重复值,这里会导致大量交换,导致超时
less += 1
great += 1
nums[less],nums[hi] = nums[hi],nums[less]
return less
def quickSort(self,nums:List[int],lo:int,hi:int):
if lo > hi:return
index = 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:return
j = random.randint(lo,hi)
nums[j],nums[hi] = nums[hi],nums[j]
pivot = nums[hi]
i = lo
less = lo
great = hi
while(i<=great):
if nums[i] < pivot:
nums[i],nums[less] = nums[less],nums[i]
less += 1
i += 1
elif nums[i] > pivot:
nums[i],nums[great] = nums[great],nums[i]
great -= 1
else:
i += 1
self.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