重载运算符 [] 实现寻找数组的第K大的元素

方法是利用快排的想法，效率O(N)
  1 /*
  2  * use the method of quicksort. The time efficiency is 
  3  * O(N).
  4  * 
  5  * */
  6 #include <iostream>
  7 #include <cstdlib>
  8 #include <cstdio>
  9 #include <iomanip>
 10 
 11 using namespace std;
 12 
 13 class Array
 14 {
 15 public:
 16     friend istream & operator >> (istream & input, Array & a);
 17     friend ostream & operator << (ostream & outpu, Array & a);
 18     int operator [] (int p);
 19     void exchange(int &s, int &t);
 20     int partition(int *p, int l, int r);
 21     int k_element(int *p, int l, int r, int k);
 22     int getlen(){return len;}
 23 private:
 24     int *a;
 25     int len;
 26 };
 27 
 28 int Array::operator [] (int p)
 29 {
 30     return k_element(a, 0, len-1, p);
 31 }
 32 
 33 int Array::k_element(int *p, int l, int r, int k)
 34 {
 35     if (l < r)
 36     {
 37         int q = partition(p, l, r);
 38         if (q + 1 == k)
 39             return p[q];
 40         else if (q + 1 > k)
 41             return k_element(p, l, q-1, k);
 42         else 
 43             return k_element(p, q+1, r, k); //这个地方尤其要注意，应该还是k，而不是k-q-1！
 44     }
 45     else return p[l];
 46 }
 47 
 48 ostream & operator << (ostream & output, Array & array)
 49 {
 50     for (int i = 0; i < array.len; ++i)
 51         output << setw(3) << array.a[i]; 
 52     output << endl;
 53     return output;
 54 }
 55 
 56 istream & operator >> (istream & input, Array & array)
 57 {
 58     cout << "intput the length of Array: ";
 59     input >> array.len;
 60     array.a = new int[array.len+1];
 61     for (int i = 0; i < array.len; ++i)
 62         input >> array.a[i];
 63     return input;
 64 }
 65 
 66 void Array::exchange(int &s, int &t)
 67 {
 68     int temp;
 69     temp = s; s = t; t = temp; 
 70 }
 71 
 72 int Array::partition(int *p, int l, int r)
 73 {
 74     int i = (l+r)/2, j;
 75     exchange(p[i], p[r]);
 76     int store = l;
 77     for (j = l; j < r; ++j)
 78     {
 79         if (p[j] >= p[r])
 80         {
 81             exchange(p[j], p[store]);
 82             store++;
 83         }
 84     }
 85     exchange(p[r], p[store]);
 86     return store;
 87 }
 88 
 89 int main(void)
 90 {
 91     Array array;
 92 
 93     freopen("in", "r", stdin);
 94 
 95     cin >> array;
 96     cout << array;
 97     for (int i = 0; i < array.getlen(); ++i)
 98         cout << i+1 << "-th: " << array[i+1] << endl;
 99     cout << endl;
100 
101     return 0;
102 }
写的过程中还是出现了一些错误，以后要认真，尤其是细节，不能想当然，要仔细一点。