寻找第k小元素

n个已排序的序列A[1...n]的中项是这个序列的第[n/2]（向上取整）小的元素。最直接的方法是对这个序列进行排序并取出该元素，这个方法需要O(n log n)的时间。

选择算法是找出序列中的第k小的元素，该算法会设置一个阈值，当元素个数小于该值时直接排序找出第k小元素。若不小于阈值，则将n个元素分为[n/5]组，每组5个元素，如果n不是5的倍数，则排除剩余的元素。每组进行排序并取出它们的中项即第3个元素。接着将这些中项序列中的中项元素记为mm，它是通过递归计算得到的。将A中的元素划分成三个数组：A1、A2和A3，其中分别包含小于、等于和大于mm的元素。最后求出第k小的元素出现在三个数组中的哪一个，并根据测试结果，算法或者返回滴k小的元素，或者在A1或A3上递归。

算法：SELECT

输入：n个元素的数组A[1...n]和整数k，1<=k<=n

输出：A中的第k小元素

select(A, low, high, k)

?

p ← high - low + 1if p < 44 then 将A排序 return A[k]令q=[p/5]（向下取整）。将A分成q组，每组5个元素。如果5不整除p，则排除剩余元素将q组中的每一组单独排序，找出中项。所有中项的集合为Mmm ← select(M, 1, q, [q/2]（向上取整）) {mm为中项集合的中项}将A[low...high]分成三组A1 = {a|a<mm}A2 = {a|a=mm}A3 = {a|a>mm}case    |A1|>=k: return select(A1, 1, |A1|, k)    |A1|+|A2|>=k: return mm    |A1|+|A2|<k: return select(A3, 1, |A3|, k-|A1|-|A3|)end case

?

?

下面是C++实现：

?

#include <iostream>#include <stack>#include <cmath>using std::stack;using std::cout;using std::endl;int Split(int * a, int low, int high) {int i = low;int x = a[low];for (int j = low+1; j <= high; j++) {if (a[j] <= x) {i ++;if (i != j) {int temp = a[i];a[i] = a[j];a[j] = temp;}}}int temp = a[low];a[low] = a[i];a[i] = temp;return i;}void QuickSort(int * a, int low, int high) {if (low >= high) {return;}stack<int> range;range.push(low);range.push(high);while(!range.empty()) {high = range.top();range.pop();low = range.top();range.pop();int w = Split(a, low, high);if (low < w-1) {range.push(low);range.push(w-1);}if (high > w+1) {range.push(w+1);range.push(high);}}}//寻找第k小的元素，但会破坏原数组的顺序int select(int * A, int low, int high, int k) {int result = 0;int p = high-low+1;if (p < 6/*44*/) {QuickSort(A, low, high);return A[k-1];}int q = p / 5;int * M = new int [q];for (int i = 0; i < q; i++) {QuickSort(A, i*5, i*5+4);M[i] = A[i*5+2];}int mm = select(M, 0, q-1, int(ceil(q/2.0)));int * A1 = new int [p];int * A2 = new int [p];int * A3 = new int [p];int count1 = 0, count2 = 0, count3 = 0;for (int i = low; i <= high; i++) {if (A[i] < mm) {A1[count1++] = A[i];} else if (A[i] == mm) {A2[count2++] = A[i];} else {A3[count3++] = A[i];}}if (count1 >= k) {result = select(A1, 0, count1-1, k);} else if (count1+count2 >= k) {result = mm;} else if (count1+count2 < k) {result = select(A3, 0, count3-1, k-count1-count2);}delete [] M;delete [] A1;delete [] A2;delete [] A3;return result;}int main(void) {int a[] = {8, 33, 17, 51, 57, 49, 35, 11, 25, 37, 14, 3, 2, 13, 52, 12, 6, 29, 32, 54, 5, 16, 22, 23, 7};int result = select(a, 0, 24, 13);cout << "序列：\n";for (int i = 0; i < 25; i++) {cout << a[i] << "  ";}cout << endl;cout << "的第k小元素为：" << result << endl;getchar();return 0;}

下面是Java版本：

?

package select;import java.util.ArrayList;import java.util.Arrays;import sort.QuickSort;public class SelectArray {private ArrayList<Integer> array = new ArrayList<Integer>();public SelectArray(int [] array) {this.array.clear();for (int i = 0; i < array.length; i++) {this.array.add(array[i]);}}private int select(int [] A, int low, int high, int k) {//QuickSort qs = null;int result = 0;      int p = high-low+1;      if (p < 6/*44*/) {          A = new QuickSort(A).getSortedIntArray();          return A[k-1];      }      int q = p / 5;      int [] M = new int [q];      for (int i = 0; i < q; i++) {    int [] t = Arrays.copyOfRange(A, i*5, i*5+4);    t = new QuickSort(t).getSortedIntArray();         M[i] = t[2];      }      int mm = select(M, 0, q-1, (int)Math.floor(q/2.0));        int [] A1 = new int [p];      int [] A2 = new int [p];      int [] A3 = new int [p];      int count1 = 0, count2 = 0, count3 = 0;      for (int i = low; i <= high; i++) {          if (A[i] < mm) {              A1[count1++] = A[i];          } else if (A[i] == mm) {              A2[count2++] = A[i];          } else {              A3[count3++] = A[i];          }      }      if (count1 >= k) {          result = select(A1, 0, count1-1, k);      } else if (count1+count2 >= k) {      result = mm;      } else if (count1+count2 < k) {      result = select(A3, 0, count3-1, k-count1-count2);      }return result;  }public int getSelectedElement(int k) {int [] A = new int [this.array.size()];for (int i = 0; i < A.length; i++) {A[i] = this.array.get(i); }return select(A, 0, A.length-1, k);}/** * @param args */public static void main(String[] args) {// TODO Auto-generated method stubint a[] = {8, 33, 17, 51, 57, 49, 35, 11, 25, 37, 14, 3, 2, 13, 52, 12, 6, 29, 32, 54, 5, 16, 22, 23, 7};SelectArray sa = new SelectArray(a);System.out.println("序列：");for (int i = 0; i < 25; i++) {  System.out.print(a[i] + "  ");      } System.out.println();System.out.println("的第k小元素为：" + sa.getSelectedElement(13));}}

Python版本如下：

?

#! /usr/bin/env python  # -*- coding:utf-8 -*-from math import ceilclass SelectList:    def __init__(self, l):        self.array = list()        for i in l:            self.array.append(i)    def select(self, a, low, high, k):        result = 0        p = high-low + 1                if p < 6:            a.sort()            return a[k-1]        q = p/5        M = [0] * q        for i in range(0, q):            t = a[i*5:i*5+5]            t.sort()            M[i] = t[2]        mm = self.select(M, 0, q-1, int(ceil(q/2.0)))                a1 = []         a2 = []        a3 = []        count1 = 0        count2 = 0        count3 = 0        for i in a:            if i < mm:                a1.append(i)                count1 += 1            elif i == mm:                a2.append(i)                count2 += 1            else:                a3.append(i)                count3 += 1                if count1 >= k:            result = self.select(a1, 0, count1-1, k)        elif count1+count2 >= k:            result = mm        elif count1+count2 < k:            result = self.select(a3, 0, count3-1, k-count1-count2)        return result    def getSelectedElement(self, k):        return self.select(self.array, 0, len(self.array)-1, k)if __name__ == '__main__':    a = [8, 33, 17, 51, 57, 49, 35, 11, 25, 37, 14, 3, 2, 13, 52, 12, 6, 29, 32, 54, 5, 16, 22, 23, 7]    sl = SelectList(a)    print "序列："    for i in a:        print i,    print    print "的第k小元素为：", sl.getSelectedElement(13)

?