/*
  Name:
  Copyright:
  Author:goal00001111
  Date: 02-06-06 13:21
  Description:
      有一整数序列，求其序列第k大的数。已知序列每个数不大于1000，
长度不超过1000，有可能有重复数字。
    如：10 50 2 31 7 6 16第二大的数为6。（k以1为起点）
函数接口为：
    int KthNumOfList(int List[],int len,int k);
    int List[]为整型序列
    int len为序列长度
    int k  为要求第几大
    返回值为第k大的数
*/
/*
算法介绍：
(1) 设置一个最小长度least，当len <= least时，直接对数组按递增排序，第k个元素即为所求元素；否则，转步骤(2).
(2) 把元素划分为lenp = len/5 组, 每组5个元素,不足5个元素的那组先不予考虑.
(3) 取每组的中值元素,构成一个长度为lenp的数组p[].
(4) 对数组p[]递归地执行本算法,得到其中值元素m.
(5) 把原数组List[]划分成p,q,r三组,使得小于m的元素存放在p[],等于m的元素存放在q[],大于m的元素存放在r[].
(6) 如果lenp > k, 对p[]递归地执行本算法,并把最后返回的值存储到m;否则,转步骤(7).
(7) 如果lenp + lenq < k,对r[]递归地执行本算法,并把最后返回的值存储到m.
(8) 很明显,此时的m就是所要选择的元素, 销毁p,q,r, 并返回m.
*/
#include <iostream>

using namespace std;

int KthNumOfList(int List[],int len,int k);
static int Compare(const void *p1, const void *p2);
void Mid(int a[], int i, int p[]);
void Swap(int & a, int & b);

int main()
{
      int a[8] = {10,20,30,40,5,6,7,8};
      int n = KthNumOfList(a, 8, 2);
    cout << n << "\n";;

    getchar();
    return 0;
}

int KthNumOfList(int List[], int len, int k)
{
      const int least = 64; //设置一个最小长度least
      if (len <= least)
      {
            qsort(List, len, sizeof(int), Compare); //对数组按递增排序
            return List[k-1];
      }
      
      int *p = new int[3*len/4];
      int lenp = len/5; //把元素划分为lenp = len/5 组, 每组5个元素,不足5个元素的那组先不予考虑.
      for (int i=0; i<lenp; i++)
      {
            Mid(List, i, p); //取每组的中值元素,构成一个长度为lenp的数组p[].
      }
      
      int m = KthNumOfList(p, lenp, lenp/2 + lenp%2);//对数组p[]递归地执行本算法,得到其中值元素m.
      
      int *q = new int[3*len/4];
      int *r = new int[3*len/4];
      int lenq = 0;
      int lenr = 0;
      lenp = 0;
      //把原数组List[]划分成p,q,r三组,使得小于m的元素存放在p[],等于m的元素存放在q[],大于m的元素存放在r[].
      for (int i=0; i<len; i++)
      {
            if (List[i] < m)
                  p[lenp++] = List[i];
            else if (List[i] == m)
                  q[lenq++] = List[i];
            else
                  r[lenr++] = List[i];
      }
      
      if (lenp > k)
      {
            m = KthNumOfList(p, lenp, k);
      }
      else if(lenp + lenq < k)
      {
            m = KthNumOfList(r, lenr, k-lenp-lenq);
      }
      //很明显,此时的m就是所要选择的元素, 销毁p,q,r, 并返回m.
      delete []p;
      delete []q;
      delete []r;

      return m;
}

static int Compare(const void *p1, const void *p2)
{
    return (*(int *)p1) - (*(int *)p2);
}
 /*
函数介绍：从数组a[]中,每5个元素为一组,取第i组的中值元素作为数组p[]的第i个元素.
输入： 数组a[].
       组号 i .
输出：存放中值元素的数组p[].
*/
void Mid(int a[], int i, int p[])
{
      int k = 5 * i;
      
      if (a[k] > a[k+2])
            Swap(a[k], a[k+2]);
      if (a[k+1] > a[k+3])
            Swap(a[k+1], a[k+3]);
      if (a[k] > a[k+1])
            Swap(a[k], a[k+1]);
      if (a[k+2] > a[k+3])
            Swap(a[k+2], a[k+3]);
      if (a[k+1] > a[k+2])
            Swap(a[k+1], a[k+2]);
            
      if (a[k+4] > a[k+2])
            p[i] = a[k+2];
      else if (a[k+4] > a[k+1])
            p[i] = a[k+4];
      else
            p[i] = a[k+1];
}

void Swap(int & a, int & b)
{
      int temp = a;
      a = b;
      b = temp;
}