快排 + 二分

一直觉得快排跟二分很像，大家也都有很多变种，在此整理一下
快排的特点是，需要一个pivort，让左边比他大，右边比他小（反之亦然），每次排序都有一个数的位置被确定
两种写法其实是一种

经典partition写在一个函数里

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quicksort(start,end):
            idx = random.randint(start,end)
            nums[start], nums[idx] = nums[idx], nums[start]
            l,r = start,end
            while l < r:
                while l < r and nums[r] <= nums[start]:
                    r -= 1
                while l < r and nums[l] >= nums[start]:
                    l += 1
                nums[l],nums[r] = nums[r], nums[l]
            nums[l],nums[start] = nums[start] , nums[l]
            if l == k - 1:
                return nums[l]
            elif l < k - 1:
                return quicksort(l + 1, end)
            else:
                return quicksort(start, l - 1)
        return quicksort(0,len(nums) -1)

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        l, r = 0 ,len(nums) - 1
        def partition(l,r):
            pivot = random.randint(l,r)
            nums[pivot] , nums[l] = nums[l],nums[pivot]
            s,e = l ,r
            while s < e:
                while s < e and nums[e] <= nums[l]:
                    e -= 1
                while s < e and nums[s] >= nums[l]:
                    s += 1
                nums[s], nums[e] = nums[e], nums[s]
            nums[s], nums[l] = nums[l], nums[s]
            return s
        while True:
            idx = partition(l,r)
            if idx == k - 1:
                return nums[idx]
            elif idx < k - 1:
                l = idx + 1
            else:
                r = idx - 1

全部排列代码如下

def findk3(nums):
    def quicksort(start,end):
        if start >= end:
            return
        idx = random.randint(start,end)
        nums[start], nums[idx] = nums[idx], nums[start]
        l,r = start,end
        while l < r:
            while l < r and nums[r] <= nums[start]:
                r -= 1
            while l < r and nums[l] >= nums[start]:
                l += 1
            nums[l],nums[r] = nums[r], nums[l]
        nums[l],nums[start] = nums[start] , nums[l]
        quicksort(l + 1, end)
        quicksort(start, l - 1)

    return quicksort(0,len(nums) -1)
findk3(nums)
print(nums)

全部排序代码如下

def findk4(nums):
    def quicksort(l,r):
        if l > r:
            return
        idx = partition(l,r)
        quicksort(idx + 1,r)
        quicksort(l,idx - 1)
    def partition(l,r):
        pivot = random.randint(l,r)
        nums[pivot] , nums[l] = nums[l],nums[pivot]
        s,e = l ,r
        while s < e:
            while s < e and nums[e] <= nums[l]:
                e -= 1
            while s < e and nums[s] >= nums[l]:
                s += 1
            nums[s], nums[e] = nums[e], nums[s]
        nums[s], nums[l] = nums[l], nums[s]
        return s
    return quicksort(0,len(nums) - 1)