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

这是一道经典的算法题，有多种解法。下面介绍两种比较常见的解法。

解法一：快速选择算法

快速选择算法是快速排序算法的变种，其思想是通过一次快速排序的划分过程，找到第k小的元素所在的位置，然后递归地在左边或右边继续查找。具体步骤如下：

1. 选择数组中的一个元素pivot，将数组划分为两个部分：小于pivot的元素和大于等于pivot的元素。可以使用快速排序的划分方法，即选定一个pivot，然后维护两个指针i和j，i从左往右扫描，找到第一个大于等于pivot的元素，j从右往左扫描，找到第一个小于pivot的元素，然后交换a[i]和a[j]，直到i>=j，此时将pivot和a[j]交换。

2. 比较j和k的大小关系，如果j=k则a[j]就是要找的第k小的元素；如果j<k，则在a[j+1..n]中递归查找第k-j-1小的元素；如果j>k，则在a[1..j-1]中递归查找第k小的元素。

时间复杂度：平均时间复杂度为O(n)，最坏情况下时间复杂度为O(n^2)。

Python代码如下：

def quick_select(a, k):
n = len(a)
if k < 1 or k > n: # k不在合法范围内
return None
if n == 1: # 数组只有一个元素
return a[0]
pivot = a[0]
i, j = 0, n-1
while i < j:
while i < j and a[j] >= pivot:
j -= 1
a[i] = a[j]
while i < j and a[i] < pivot:
i += 1
a[j] = a[i]
a[i] = pivot
if k == i+1:
return pivot
elif k < i+1:
return quick_select(a[:i], k)
else:
return quick_select(a[i+1:], k-i-1)

# 测试代码
a = [20,43,32,67,48,89,36,47,15]
k = 3
print(quick_select(a, k)) # 输出32

解法二：堆排序算法

堆排序算法也可以用来解决这个问题。具体步骤如下：

1. 建立一个大小为k的小根堆，将数组a的前k个元素插入到小根堆中。

2. 依次将a[k+1..n]中的元素和堆顶元素比较，如果小于堆顶元素，则将堆顶元素弹出，插入该元素；否则不做处理。

3. 最后堆顶元素就是第k小的元素。

时间复杂度：平均时间复杂度为O(nlogk)，最坏情况下时间复杂度为O(nlogn)。

Python代码如下：

import heapq

def heap_select(a, k):
n = len(a)
if k < 1 or k > n: # k不在合法范围内
return None
if n == 1: # 数组只有一个元素
return a[0]
heap = a[:k]
heapq.heapify(heap)
for i in range(k, n):
if a[i] < heap[0]:
heapq.heapreplace(heap, a[i])
return heap[0]

# 测试代码
a = [20,43,32,67,48,89,36,47,15]
k = 3
print(heap_select(a, k)) # 输出32