“选择算法”

翻译自维基百科&＃xff1a;http://en.wikipedia.org/wiki/Selection_algorithm

        在计算机科学里&＃xff0c;选择算法&＃xff08;selection algorithm&＃xff09;是一种用于在一个列表中查找第K小的数的算法&＃xff08;这个数也被称之为第K个顺序统计量&＃xff09;。这类算法包括查找最小值、最大值和中值三类。这里有一些最坏时间复杂度为O(n)的选择算法。选择问题是更为复杂的问题&＃xff0c;例如最近邻问题和最短路径问题的子问题。

        术语“选择”也被用在计算机科学界得其它上下文中。比如&＃xff0c;遗传算法中的选择&＃xff0c;是指从一代个体中选取的用于繁殖下一代个体的基因。本篇文章仅涉及如何确定顺序统计量的问题。

1、通过排序实现选择。

        选择问题可以通过对列表中的数据进行排序&＃xff0c;然后提取需要的数值来简化为一个排序问题。当需要对列表中的数据进行排序时&＃xff0c;该方法十分有效。在这种情况下&＃xff0c;仅需要一个初始的、计算时间昂贵的排序算法和一些列后续的提取操作就可以完成目标。总的来说&＃xff0c;这种方法的时间复杂度为O(n log n)&＃xff0c;这里的n指代列表的长度。

2、非线性的通用选择算法

   利用与求解最大、最小值相似的思想&＃xff0c;我们可以实现一个简单&＃xff0c;但是费时的用于在一个列表中查找第K小或第K大的数。这种方法的时间复杂度为O(kn)&＃xff0c;当K的值较小时很有效。为了实现该算法&＃xff0c;我们仅需要简单的在列表中找出最小或最大值&＃xff0c;并将它移动到列表的开头&＃xff0c;知道我们得到想要的第K个数。这可以看做是一种选择排序&＃xff0c;下面给出选择第K小的数的算法&＃xff1a;

function select(list[1..n], k)for i from 1 to kminIndex &＃61; iminValue &＃61; list[i]for j from i&＃43;1 to nif list[j] return list[k] 该算法的其它一些优势在于&＃xff1a;

&＃xff08;1&＃xff09;在定位到第j小的数后&＃xff0c;便仅需要O(j &＃43; (k-j)²)的时间来定位第K小的数&＃xff0c;或者当k <&＃61; j 时&＃xff0c;仅需要O(k)的时间来提取第k小的数。

&＃xff08;2&＃xff09;该算法可以借助链表数据结构来实现。然而基于分割的方法则需要有直接存取的功能。

3、基于分割的通用选择算法

    一个在实际中很有效的通用的选择算法&＃xff0c;但是在最坏情况下有较高时间复杂度的算法&＃xff0c;是由快速排序的发明者C.A.R. Hoare构想出来的。该选择算法被称为Hoare&＃39;s selection algorithm 或者被称为quickselect。

在快速排序算法中&＃xff0c;有一个叫做分割的子过程&＃xff0c;它能够在线性的时间内&＃xff0c;将范围从left到right的列表分割为两个部分&＃xff0c;即小于某一特定值的为一部分&＃xff0c;大于等于某一特定值的为另一部分。下面的伪代码执行关于元素list[pivotIndex]的分割过程&＃xff1a;

function partition(list, left, right, pivotIndex)pivotValue :&＃61; list[pivotIndex]swap list[pivotIndex] and list[right] // Move pivot to endstoreIndex :&＃61; leftfor i from left to rightif list[i] // Move pivot to its final placereturn storeIndex     在快速排序算法中&＃xff0c;我们递归的对两个分支进行排序&＃xff0c;获得了最好的
Ω(n log n) 的时间复杂度。但是在选择问题中&＃xff0c;我们只需要知道想要的元素在哪一个分支里面&＃xff0c;因为枢纽元素处于最终排序完成的位置时&＃xff0c;位于它左边的元素是有序的&＃xff0c;位于它右边的元素也是有序的。因此&＃xff0c;只需要在正确的分支里进行一次递归调用就可以找到所需的元素了。

function select(list, left, right, k)if left &＃61; right // If the list contains only one elementreturn list[left] // Return that elementselect pivotIndex between left and rightpivotNewIndex :&＃61; partition(list, left, right, pivotIndex)pivotDist :&＃61; pivotNewIndex - left &＃43; 1 // The pivot is in its final sorted position, // so pivotDist reflects its 1-based position if list were sortedif pivotDist &＃61; k return list[pivotNewIndex]else if k return select(list, left, pivotNewIndex - 1, k)elsereturn select(list, pivotNewIndex &＃43; 1, right, k - pivotDist)

注意它与快速排序算法的相似之处&＃xff1a;正如基于最小值的选择算法是一种部分选择算法一样&＃xff0c;该方法是一种部分快速排序方法。相比于快速排序里O(n)的分割时间&＃xff0c;这里仅需要O(logn)的时间。这个简单的算法有着线性的表现&＃xff0c;正如快速排序一样&＃xff0c;在实际应用中有着很好的表现。它同时也是一个in-place算法&＃xff0c;仅需要常数级的内存开销&＃xff0c;因为尾递归可以使用下面的方法来消除&＃xff1a;

function select(list, left, right, k)loopselect pivotIndex between left and rightpivotNewIndex :&＃61; partition(list, left, right, pivotIndex)pivotDist :&＃61; pivotNewIndex - left &＃43; 1if pivotDist &＃61; kreturn list[pivotNewIndex]else if k elsek :&＃61; k - pivotDistleft :&＃61; pivotNewIndex &＃43; 1 像快速排序算法一样&＃xff0c;该算法对于枢纽元素
pivot的选择十分敏感。如果常常选择的是不好的枢纽元素&＃xff0c;该算法将会退化到和之前所述的基于最小值的选择算法一样&＃xff0c;
时间复杂度为
O(n²)。David Musser描述的“median-of-3 killer”序列能够使得著名的三数取中位数的枢纽元素选取方法失效。

4、线性通用选择算法--中位数的中位数算法

未完待续。。。