对于给定的n个元素的数组a[1..n]，要求从中找出第k小的元素。 【输入样例】 a={20, 43, 32, 67 ,48, 89, 36, 47, 15} k=3 【输出样例】 32

一、暴力法

最简单直接的方法就是对数组进行排序，然后返回第k个元素。时间复杂度为O(nlogn)，空间复杂度为O(1)。这里就不再具体讲解。

二、快速选择算法

快速选择算法和快速排序算法有些类似，都是基于分治的思想，但是快速选择算法只需要找到第k小的元素，而无需对数组进行完整的排序。

1.基本思想

快速选择算法的基本思想是：随机选取一个元素pivot，将小于等于pivot的元素放在pivot左边，大于pivot的元素放在pivot右边，然后判断pivot的位置与k的大小关系，如果pivot的位置小于k，则在pivot右边继续查找第k小的元素；如果pivot的位置大于k，则在pivot左边继续查找第k小的元素；如果pivot的位置等于k，则返回pivot。

2.代码实现

快速选择算法的代码实现跟快速排序算法很像，只需要在快速排序算法的基础上稍微修改即可。

具体来说，我们可以定义一个函数quickSelect，用于查找第k小的元素。该函数的输入参数包括数组a、数组的起始下标low、数组的终止下标high以及要查找的第k小的元素。

在函数内部，我们先随机选取一个元素pivot，并将小于等于pivot的元素放在pivot左边，大于pivot的元素放在pivot右边。然后判断pivot的位置与k的大小关系。如果pivot的位置小于k，则在pivot右边继续查找第k小的元素；如果pivot的位置大于k，则在pivot左边继续查找第k小的元素；如果pivot的位置等于k，则返回pivot。

下面是快速选择算法的代码实现：

def quickSelect(a, low, high, k):
if low == high:
return a[low]
pivotIndex = partition(a, low, high)
if pivotIndex == k - 1:
return a[pivotIndex]
elif pivotIndex > k - 1:
return quickSelect(a, low, pivotIndex - 1, k)
else:
return quickSelect(a, pivotIndex + 1, high, k)

def partition(a, low, high):
pivot = a[low]
i = low + 1
j = high
while True:
while i <= j and a[i] <= pivot:
i += 1
while i <= j and a[j] >= pivot:
j -= 1
if i <= j:
a[i], a[j] = a[j], a[i]
else:
break
a[low], a[j] = a[j], a[low]
return j

a = [20, 43, 32, 67, 48, 89, 36, 47, 15]
k = 3
print(quickSelect(a, 0, len(a) - 1, k))

三、时间复杂度分析

快速选择算法的时间复杂度跟快速排序算法相同，最坏情况下为O(n^2)，平均情况下为O(n)。但是，由于我们随机选取pivot，因此快速选择算法的平均时间复杂度很接近于O(n)。