document.write('由于对一个有序的数组而言，能非常容易地找到数组中第k小的数，因此，可以通过对数组进行排序
的方法来找出第k小的数。同时，由于只要求第k小的数，因此，没有必要对数组进行完全排序，只
需要对数组进行局部排序就可以了。下面分别介绍这几种不同的实现方法。
方法一：排序法
最简单的方法就是首先对数组进行排序，在排序后的数组中，下标为k-1的值就是第k小的数。例
如：对数组[4,0,1,0,2,3]进行排序后的序列变为[0,0,1,2,3,4]，第3小的数就是排序后数组中下标为2
对应的数：1。由于最高效的排序算法(例如快速排序)的平均时间复杂度为O(Nlog2
N)，因此，此时
该方法的平均时间复杂度为O(Nlog2
N)，其中，N为数组的长度。
方法二：部分排序法
由于只需要找出第k小的数，因此，没必要对数组中所有的元素进行排序，可以采用部分排序的方
法。具体思路为：通过对选择排序进行改造，第一次遍历从数组中找出最小的数，第二次遍历从剩
下的数中找出最小的数(在整个数组中是第二小的数)，第k次遍历就可以从N-k+1 (N为数组的长度)
个数中找出最小的数(在整个数组中是第k小的)。这种方法的时间复杂度为O(N*k)。当然也可以采用
堆排序进行k趟排序找出第k小的值。
方法三：类快速排序方法
快速排序的基本思想为：将数组array[low..high]中某一个元素(取第一个元素)作为划分依据，然
后把数组划分为三部分：1)array[low...i-1](所有的元素的值都小于或等于array[i])、2)array[i]、3)
array[i+1...high](所有的元素的值都大于array[i])。在此基础上可以用下面的方法求出第k小的元
素：
(1)如果i-low==k-1，说明array[i]就是第k小的元素，那么直接返回array[i]；
(2)如果i-low>k-1，说明第k小的元素肯定在array[low...i-1]中，那么只需要递归地在
array[low...i-1]中找第k小的元素即可；
(3)如果i-low＜k-1，说明第k小的元素肯定在array[i+1...high]中，那么只需要递归地在
array[i+1...high]中找第k-(i-low)-1小的元素即可。
对于数组(4,0,1,0,2,3)，第一次划分后，划分为下面三部分：
(3,0,1,0,2), (4), ()
接下来需要在(3,0,1,0,2)中找第3小的元素，把(3,0,1,0,2)划分为三部分：
(2,0,1,0), (3), ()
接下来需要在(2,0,1,0)中找第3小的元素，把(2,0,1,0)划分为三部分：
(0,0,1), (2), ()
接下来需要在(0,0,1)中找第3小的元素，把(0,0,1)划分为三部分：
(0), (0), (1)
此时i=1, low=0; (i-1=1)＜(k-1=2)，接下来需要在(1)中找第k-(i-low)-1=1小的元素即可。显
然，(1)中第1小的元素就是1。
实现代码如下：
"""
方法功能: 在数组array中找出第k小的值
输入参数: array为整数数组, low为数组起始下标, high为数组右边界的下标, k为整数
返回值: 数组中第k小的值
"""
def findSmallK(array,low,high,k):
i=low
j=high
splitElem=array[i]
#把小于等于splitElem的数放到数组中splitElem的左边, 大于splitElem的值放到右边
while i＜j:
while i＜j and array[j]＞=splitElem:
j-=1
if i＜j:
array[i]=array[j]
i+=1
while i＜j and array[i]＜=splitElem:
i+=1
if i＜j:
array[j]=array[i]
j-=1
array[i]=splitElem
#splitElem在子数组array[low～high]中下标的偏移量
subArrayIndex=i-low
#splitElem在array[low～high]所在的位置恰好为k-1, 那么它就是第k小的元素
if subArrayIndex==k-1:
return array[i]
# splitElem在array [low～high]所在的位置大于k-1, 那么只需在array[low～i-1]中找第k小的元
素
elif subArrayIndex＞k-1:
return findSmallK(array, low, i-1, k)
#array[i+1～high]中找第k-i+low-1小的元素
else:
return findSmallK(array, i+1, high, k-(i-low)-1)
if __name__=="__main__":
k=3
array=[4,0,1,0,2,3]
print "第"+str(k)+"小的值为:"+str(findSmallK(array,0,len(array)-1,k))
程序的运行结果为：
第3小的值为：1
算法性能分析：
快速排序的平均时间复杂度为O(Nlog2
N)。快速排序需要对划分后的所有子数组继续排序处理，
而本方法只需要取划分后的其中一个子数组进行处理即可，因此，平均时间复杂度肯定小于
O(Nlog2
N)。由此可以看出，这种方法的效率要高于方法一。但是这种方法也有缺点：它改变了数
组中数据原来的顺序。当然可以申请额外的N(其中，N为数组的长度)个空间来解决这个问题，但是
这样做会增加算法的空间复杂度，所以，通常做法是根据实际情况选取合适的方法。
');