寻找序列中最小的第N个元素（partition函数实现）

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< || k>p2-p1+) return -;

if (p1 >= p2) return a[p1];

//若a[p1]~a[p2] 只有一个元素，则返回该元素

p = Partition(a, p1, p2);

num = p-p1;

if (k == num + ) return a[p]; //第k小元素为分割点

if (k <= num) return OrderStatistics(a, p1, p-, k); //第k小元素在前部

return OrderStatistics(a, p+, p2, k-num-); // 第k 小元素在后部

}

Python cookbook 中给出了这一方法的python 实现，如下所示:

import random

def 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就体现出它的价值了。”

巴特西

寻找序列中最小的第N个元素（partition函数实现）

最新文章

热门文章