复习快排-python实现

1,131 阅读1分钟

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)。