选择问题

问题描述：输入N的元素以及一个整数k，要求是找出第k大的元素。

一，普通排序：
算法1A：

将所有元素读入数组并且从大到小排序，然后直接返回第K个元素。如果使用简单的排序算法，运行时间就是O(N^2)。很不好。

 1//从大到小排序
 2int choose_1A(VI& in, int k)
 3{
 4    int count = in.size();
 5    for (int i = 0; i < count; ++i)
 6    {
 7        for (int j = i; j < count; ++j)
 8            if(in[i] < in[j])
 9            {
10                swap(in[i], in[j]);
11            }
12    }
13    return in[k-1];
14}

算法1B：
先将k个元素读入一个数组并且将其从大到小排序，这样的话这k个元素的最小者就在第k个位置上。然后我们依次的处理其余的元素。处理一个元素的时候，先将此元素跟数组中的第k个元素进行比较，如果此元素大就将第k个元素删除，而将这个新的元素放在其余k-1个元素间的正确的位置上。算法结束时，第k个元素上就是正确的答案。此方法的运行时间就是O(k*k+(N-k)*k)=O(N*k)。但是如果当K=[N/2]的时候（找中位数时），这种算法也是O(N^2)的。

 1//先排k个
 2int choose_1B(VI& in, int k)
 3{
 4    int count = in.size();
 5    FORR(i, 0, k)
 6    {
 7        FORR(j, i, k)
 8        {
 9            if (in[i] < in[j])
10            {
11                swap(in[i], in[j]);
12            }
13        }
14    }
15    list<int> lst_k(in.begin(), in.begin()+k);
16
17    FORR(i, k, count)
18    {
19        if (in[i] > lst_k.back())
20        {
21            for (list<int>::iterator it = lst_k.begin(); it != lst_k.end(); ++it)
22            {
23                if (in[i] > *it)
24                {
25                    lst_k.insert(it, in[i]);
26                    break;
27                }
28            }
29            lst_k.pop_back();
30        }
31    }
32    return lst_k.back();
33}
34

二，使用优先队列（二叉堆）
算法2A：
简单起见现在我们把问题改一下：找出第k个最小的元素。算法是，先将N个元素读入一个数组，然后对此数组应用buildHeap算法。最后执行k次deleteMin操作。这时候从该堆中取出的就是正确答案。这个算法显然是正确的，如果使用buildHeap，构造堆的最坏情形就是O(N)的时间，而每次deleteMin的时间是O(logN)的时间。由于是k次deleteMin，则总时间是O(N+klogN)。当k=[N/2]的时候，运行时间就是O(NlogN)（找中位数时间）。其实注意的是，如果令k=N，那么实际上就是对输入文件以时间O(NlogN)进行了排序。这就是堆排序。

//优先队列O(N + k*logN)
int choose_2A(VI& in, int k)
{
    priority_queue<int> maxPQ(in.begin(), in.end());

    FORR(i, 0, k-1)
    {
        maxPQ.pop();
    }
    return maxPQ.top();
}

算法2B:
使用算法1B的思路，在任意一个时刻，都将维持k个最大元素的集合S。在前k个元素读入以后，再读入一个新的元素时候，该元素将会和第k个最大最大元素进行比较，设其为Sk(是S中最小的)。如果新的元素大于Sk，那么就用新元素代替S中的Sk。这个时候S中就会有一个新的最小元素，可能是新添加的也可能不是。输入完成时，找到S中的最小元素，返回就是问题的答案。
上面看来基本和算法1B差不多，不过这里我们用一个堆来实现S了(上面我是用的链表)。通过buildHeap将前k个元素以总时间O(k)放到堆中。处理其余每个元素时间只要O(1)+O(logk)。总时间是O(Nlogk)。当k=[N/2]时候即找中位数时间也是O(NlogN)。

 1//1B算法加上二叉堆
 2int choose_2B(const VI& in, int k)
 3{
 4    int count = in.size();
 5    //下面定义的是最小堆(即最小的在最顶部)
 6    priority_queue<int, vector<int>, greater<int>> minPQ(in.begin(), in.begin()+k);
 7    FORR(i, k, count)
 8    {
 9        if (in[i] > minPQ.top())
10        {
11            minPQ.pop();
12            minPQ.push(in[i]);
13        }
14    }
15    return minPQ.top();
16}
17

三，使用快速排序思想
算法3A：快速选择
这种算法称为快速选择，令|Si|是Si中的元素的个数，那么快速选择的步骤是：
(1)如果|S|=1，那么k=1并且将S中的元素作为答案返回。如果我们选用小数组的截止方法，则当|S|<=CUTOFF的时候将S排序并且返回第k个最小元。
(2)在S中选取一个枢纽元。
(3)将集合S-{v}分割成S1和S2，就像快速排序中所做的那样。
(4)如果k<=|S1|，那么第k个最小元必定在S1中。在这种情况下，返回quickselect(S1,k)。如果k=1+|S1|那么枢纽元就是第k个最小元，将它作为答案返回。否则第k个最小元就在S2中，它是S2中的第（k-|S1|-1）      个最小元。进行一次递归调用返回quickselect(S2,k-|S1|-1)。

跟快速排序相比，快速选择只是进行了一次递归调用不是两次。快速选择的最快情形也是O(N^2)，不过平均时间是O(N)。

 1const int& median3(VI& a, int left, int right)
 2{
 3    int center = (left+right)/2;
 4    if (a[center] < a[left])
 5        swap(a[left], a[center]);
 6    if (a[right] < a[left])
 7        swap(a[left], a[right]);
 8    if (a[right] < a[center])
 9        swap(a[center], a[right]);
10
11    swap(a[center], a[right-1]);
12    return a[right-1];
13}
14
15//快速选择，注意这里我们找到的是第k小的元素
16void quickSelect(VI& in, int left, int right, int k)
17{
18    if (left < right)
19    {
20        int pivot = median3(in, left, right); 
21        int i = left, j = right-1;
22        
23        while(true)
24        {
25            while(in[++i] < pivot) {}
26            while(pivot < in[--j]) {}
27            
28            if (i < j)
29                swap(in[i], in[j]);
30            else
31                break;
32        }
33
34        if(i < right-1)
35            swap(in[i], in[right-1]);
36
37        if (k <= i)
38            quickSelect(in, left, i-1, k);
39        else if(k > i+1)
40            quickSelect(in, i+1, right, k);
41    }
42    else
43        return;
44}
45
46int choose_3A(VI& in, int k)
47{
48    int count = in.size();
49    quickSelect(in, 0, count-1, k);
50    return in[k-1];
51}
52

算法3B:

是一个最坏为O(n)的算法，要准备考研了，没时间研究了，以后再说吧~~

全部源代码：

  1#include <iostream>
  2#include <sstream>
  3#include <algorithm>
  4#include <string>
  5#include <map>
  6#include <set>
  7#include <list>
  8#include <stack>
  9#include <queue>
 10#include <cctype>
 11#include <vector>
 12#include <bitset>
 13#include <cmath>
 14//#include <hash_map>
 15
 16#define FORR(i, a, b) for(int i = a; i < b; ++i)
 17#define BE(x) x.begin(),x.end()
 18#define MP(a, b) make_pair(a, b)
 19
 20using namespace std;
 21//using namespace stdex;
 22
 23typedef vector<string> VS;
 24typedef vector<int> VI;
 25
 26//从大到小排序O(N^2)
 27int choose_1A(VI& in, int k)
 28{
 29    int count = in.size();
 30    for (int i = 0; i < count; ++i)
 31    {
 32        for (int j = i; j < count; ++j)
 33            if(in[i] < in[j])
 34            {
 35                swap(in[i], in[j]);
 36            }
 37    }
 38    return in[k-1];
 39}
 40
 41//先排k个,O(K*N)
 42int choose_1B(VI& in, int k)
 43{
 44    int count = in.size();
 45    FORR(i, 0, k)
 46    {
 47        FORR(j, i, k)
 48        {
 49            if (in[i] < in[j])
 50            {
 51                swap(in[i], in[j]);
 52            }
 53        }
 54    }
 55    list<int> lst_k(in.begin(), in.begin()+k);
 56
 57    FORR(i, k, count)
 58    {
 59        if (in[i] > lst_k.back())
 60        {
 61            for (list<int>::iterator it = lst_k.begin(); it != lst_k.end(); ++it)
 62            {
 63                if (in[i] > *it)
 64                {
 65                    lst_k.insert(it, in[i]);
 66                    break;
 67                }
 68            }
 69            lst_k.pop_back();
 70        }
 71    }
 72    return lst_k.back();
 73}
 74
 75//优先队列O(N + k*logN)
 76int choose_2A(const VI& in, int k)
 77{
 78    priority_queue<int> maxPQ(in.begin(), in.end());
 79
 80    int count = maxPQ.size();
 81
 82    FORR(i, 0, k-1)
 83    {
 84        maxPQ.pop();
 85    }
 86    return maxPQ.top();
 87}
 88
 89//1B算法加上二叉堆
 90int choose_2B(const VI& in, int k)
 91{
 92    int count = in.size();
 93    //下面定义的是最小堆(即最小的在最顶部)
 94    priority_queue<int, vector<int>, greater<int>> minPQ(in.begin(), in.begin()+k);
 95    FORR(i, k, count)
 96    {
 97        if (in[i] > minPQ.top())
 98        {
 99            minPQ.pop();
100            minPQ.push(in[i]);
101        }
102    }
103    return minPQ.top();
104}
105
106const int& median3(VI& a, int left, int right)
107{
108    int center = (left+right)/2;
109    if (a[center] < a[left])
110        swap(a[left], a[center]);
111    if (a[right] < a[left])
112        swap(a[left], a[right]);
113    if (a[right] < a[center])
114        swap(a[center], a[right]);
115
116    swap(a[center], a[right-1]);
117    return a[right-1];
118}
119
120//快速选择，注意这里我们找到的是第k小的元素
121void quickSelect(VI& in, int left, int right, int k)
122{
123    if (left < right)
124    {
125        int pivot = median3(in, left, right); 
126        int i = left, j = right-1;
127        
128        while(true)
129        {
130            while(in[++i] < pivot) {}
131            while(pivot < in[--j]) {}
132            
133            if (i < j)
134                swap(in[i], in[j]);
135            else
136                break;
137        }
138
139        if(i < right-1)
140            swap(in[i], in[right-1]);
141
142        if (k <= i)
143            quickSelect(in, left, i-1, k);
144        else if(k > i+1)
145            quickSelect(in, i+1, right, k);
146    }
147    else
148        return;
149}
150
151int choose_3A(VI& in, int k)
152{
153    int count = in.size();
154    quickSelect(in, 0, count-1, k);
155    return in[k-1];
156}
157
158
159
160int main()
161{
162    int a[] = {45, 34, 12, 9 ,5, 23, 34, 32, 5, 10, 56, 29, 14, 2};
163    VI input(a, a+14);
164
165    int k = 8;
166
167    //cout << choose_1A(input, k) << endl;
168    //print(input);
169    //cout << endl;
170    //cout << choose_1B(input, k) << endl;
171    //cout << choose_2A(input, k) << endl;
172    //cout << choose_2B(input, k) << endl;
173
174    //cout << choose_3A(input, k) << endl;
175
176    return 0;
177}