分治算法 ：找第K小元素Python

以下是使用分治算法找第K小元素的Python代码：

def find_kth_smallest(arr, k):
    if len(arr) == 1:
        return arr[0]
    pivot = arr[len(arr)//2]
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    if k <= len(left):
        return find_kth_smallest(left, k)
    elif k <= len(left) + len(mid):
        return mid[0]
    else:
        return find_kth_smallest(right, k - len(left) - len(mid))

arr = [9, 8, 7, 6, 5, 4, 3, 2, 1]
k = 3
print(find_kth_smallest(arr, k)) # Output: 3

在这个算法中，我们首先找到数组的中间元素作为中心点，然后将数组分成三个部分：左边的部分比中心点小，中间的部分与中心点相等，右边的部分比中心点大。接下来，我们根据k与左、中、右三部分的大小关系选择继续在左、中、右三部分中查找第k小的元素，直到找到为止。由于每次查找都将数组分成三个部分，因此时间复杂度为O(nlogn)。