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