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就體現出它的價值了。”
新聞熱點
疑難解答
