partition函数实现,将给定数组的left到right之间的部分中的第一位放置在最终应该在的位置,并返回索引号。
def partition(nums,left,right):
key=nums[left]
while(left<right):
while(left<right and nums[right]>=key):
right-=1
nums[left]=nums[right]
while(left<right and nums[left]<=key):
left+=1
nums[right]=nums[left]
nums[left]=key
return left
递归函数中,找到start到end之间部分中的第一位的最终索引,然后对索引的左右半部分分别递归调用函数。
def main(nums,start,end):
if(start==end):
return
index=partition(nums,start,end)
if(index>start):
main(nums,start,index-1)
if(index<end):
main(nums,index+1,end)
测试代码:
class solution():
def partition(self,nums,left,right):
key=nums[left]
while(left<right):
while(left<right and nums[right]>=key):
right-=1
nums[left]=nums[right]
while(left<right and nums[left]<=key):
left+=1
nums[right]=nums[left]
nums[left]=key
return left
def main(self,nums,start,end):
if(start==end):
return
index=self.partition(nums,start,end)
if(index>start):
self.main(nums,start,index-1)
if(index<end):
self.main(nums,index+1,end)
nums=[3,4,5,1,4,6,1,8,2,9]
solution().main(nums,0,len(nums)-1)
print(nums)
快排通常时间复杂度为o(nlogn),但是当数组基本有序时,会退化成冒泡排序,时间复杂度是o(n*n)。