作者:zhanhailiang 日期:2012-12-17
问题:已知序列A[1…n],及整数k, 1?k?n,试查找A中第k小的数
这个问题一般被称为顺序统计或选择问题。常规思路是对A[1…n]进行排序取第k的元素即可。但本文将介始一种算法来高效的获取第k小的元素。该算法思想和快速排序相同。在快速排序中,序列被支点分割成两个子序列,然后分别对这两个子序列递归排序。现在我们要先确定第k小的元素在哪个子序列中,然后只需对那个子序列递归排序即可。不必考虑其余的数。
/**************************************************************** 算法:selection(A, n, k) 输入:A[1...n],k 输出:第k小的元素 select(A, 1, n, k) select(A, low, high, k) if low == high return low; else split(X, low, high); // 用X[low]来分割数组X Let middle be the output of Partition if middle - low + 1 >= k then return select(A, low, middle, k); else return select(A, middle + 1, high, k-(middle-low+1)); end ****************************************************************/ function split(array, low, high) { var i = low; var x = array[low]; for(var j = low + 1; j <= high; j++) { if(array[j] <= x) { i ++; if(i != j) { var temp = array[i]; array[i] = array[j]; array[j] = temp; } } } temp = array[low]; array[low] = array[i]; array[i] = temp; return [array, i]; } function select(array, low, high, k) { if(low === high) { return low; } else { var result = split(array, low, high); array = result[0]; var mid = result[1]; if(mid - low + 1 >= k) { return select(array, low, mid, k); } else { return select(array, mid+1, high, k - (mid-low+1)); } } } console.log(select([5,4,3,2,1,-1], 0, 5, 3));
以上算法很明显是一种理想的讨论,并没有考虑一些边缘的情况,如数组中第k小的元素存在多个,还有就是数组很短时完全可以直接通过排序来获取第k小的元素。故接下来我们将改进查找第k小元素的优化算法。
首先,若元素个数小于44,则算法使用直接的排序方法来计算第k小的元素。(44这个阈值的计算请参见算法设计技巧与分析)。下一步把n个元素划分成int(n/5)组,每组由5个元素组成,若n不是5的倍数,则剩余的元素单独构成一组,这应当不影响算法的执行。每组进行排序并取出它的中项即第3个元素。接着把这些中项序列中的中项元素记为mm(它是通过递归获取的)。算法的步骤6将数组A中的元素划分成3个数组A1,A2,A3,其中分别包含小于,等于和大于mm的元素。最后在第7步中,求出第k小的元素出现在3个数组中的哪一个,并根据测试结果,算法返回第k小的元素,或者在A1,A3上递归。
算法:select 输入:A[1...n],整数k,1<=k<=n 输出:A的第k小的元素 select(A, 1, n, k); 过程 select(A, low, high, k) 1.p = high - low + 1; 2.if p < 44 then 将A排序,返回A[k]; 3.令q=int(p/5)。将A分成q组,每组5个元素,若5不整除p,则剩余的元素单独一组 4.将q组中每一组单独排序,找出中项,所有中项的集合为M 5.mm = select(M, 1, q, int[q/2]) // mm为中项集合的中项 6.将A{low...high}分成3组 A1 = {a|a<mm}; A2 = {a|a==mm}; A3 = {a|a>mm}; 7.case |A1| >= k: return select(A1, 1, |A1|, k); |A1|+|A2| >= k: return mm; |A1|+|A2| < k: return select(A3, 1, |A3|, k-|A1|-|A2|);