Partition为分割算法，用于将一个序列a[n]分为三部分：a[n]中大于某一元素x的部分，等于x的部分和小于x的部分。
Partition程序如下：
longPartition (longa[],longp1,longp2)
{//对a[p1]~a[p2]进行分割，返回分割点的序号, p1, p2分别为元组的第一//个和最后一个元素longi, j;intx;
i=p1;
j=p2;
x=a[i];while(i<j)
{while( a[j] >= x && i,j) j--;if(i<j) {a[i] = a[j]; i++;}while(a[i] <= x && i<j) i++;if(i<j) {a [j] = a[i]; j--;}
}
a[i]=x;returni;
}
则利用partition 函数来实现查找第n个元素的程序如下所示：
longOrderStatistics(longa[],longp1,longp2,longk)
{//在a[p1]~a[p2] 中， 找出最小值，并返回值longp, num;if(k<1|| k>p2-p1+1)return-1;if(p1 >= p2)returna[p1];//若a[p1]~a[p2] 只有一个元素，则返回该元素p =Partition(a, p1, p2);
num= p-p1;if(k == num +1)returna[p];//第k小元素为分割点if(k <= num)returnOrderStatistics(a, p1, p-1, k);//第k小元素在前部returnOrderStatistics(a, p+1, p2, k-num-1);//第k 小元素在后部}
Python cookbook 中给出了这一方法的python 实现， 如下所示:
importrandomdefselect(data, n):#创建一个新列表， 处理小于0的索引, 检查索引的有效性data =list(data)ifn<0:
n+=len(data)ifnot0 <= n <len(data):raiseValueError,"can't get rank %d out of %d"%(n, len(data))#主循环， 看上去类似于排序但不需要递归whileTrue:
pivot=random.choice(data)
pcount=0
under, over=[], []
uappend, oappend=under.append, over.appendforelemindata:ifelem <pivot:
uappend(elem)elifelem >pivot:
oappend(elem)else:
pcount+= 1numunder=len(under)ifn <numunder:
data=underelifn < numunder +pcount:returnpivotelse:
data=over
n-= numunder +pcount
作者提到，也可以通过下面的简单方法实现第k个元素的查找：
defselsor(data, n):
data=list(data)
data.sort()returndata[n]
以上两种方法都可以实现，但是“基于列表的sort方法的实现的确简单的多， 实现select也确实需要多付出一点力气， 但如果n足够大而且比较操作的开销也无法忽略的话，select就体现出它的价值了。”