<学习笔记> 线性查找算法

2017-10-05

这个算法解决问题一般是选取一个序列的第k小哥元素，那么我们很容易想到，当我们将n个数排序好以后，那么排在第k个位置的即为我们要找的元素。
通过算法学家们的研究，可以很巧妙的做到即使是最坏情况下，依然可以再线性时间内完成。
这种方法的步骤是：
1.将这n个每5个一组，不够5个的剩下的元素再组成一组。
2.取出每一组的中位数，采取任意排序方法，进行排序。
3.递归调用函数查找上一步中的所有中位数的中位数，设为x。
4.用x来分割数组，设小于x的个数为k，大于x的个数n-k。
5.若i与x相等，那么返回x；若i小于k，那么在小于x的元素中继续递归查找，否则反之。
6.当n等于1时，我们终止算法，返回元素即为所求。
依据我们的步骤，很轻易就写出代码了。

template<class T>
void myswap(T &a, T &b) {    //交换元素；
  T temp;
  temp = a;
  a = b;
  b = temp;
}
template<class T>
T partition(T list[], int a, int b, int x) {    //划分方法；
  int i = a;  
  int j = b + 1;
  while (true) {
    while (list[++i]<x&&i<b);
    while (list[--j]>x);
    if (i >= j)break;
    myswap(list[i], list[j]);
  }
  list[a] = list[j];
  list[j] = x;
  return j;
}
template<class T>
void bablesort(T list[], int size) {
  for (int p = 0; p<size; p++) {      //冒泡排序；
    for (int q = p + 1; q<size; q++) {
      if (list[q]<list[p]) {
        myswap(list[q], list[p]);
      }
    }
  }
}
template<class T>
T select(T list[], int a, int b, int k) {   //核心方法；
  if (b ==a) {     //当只有一个元素时，返回此时的值即为所寻值；
    return list[a];
  }
  int groupnum = (b - a + 1) / 5;    //每5个元素一组，分的组数；不包括不足5个的那一组；
  int restnumb = (b - a + 1) % 5;    //5元组划分完毕后剩下的元素；
  for (int i = 0; i <groupnum; i++) {
    bablesort(list+a+i*5,5);         //对每个5元组进行排序；
  }
  if (restnumb != 0) {
    bablesort(list+a+groupnum*5,restnumb);  //对剩下的元素进行排序；
  }
  T *mids;                           //new一个数组来储存我们在每组中找到的中位数；
  if (restnumb == 0) {
    mids = new T[groupnum];          
  }
  else {
    mids = new T[groupnum+1];        //有剩余元素的情况要多一组；
  }
  for (int i = 0; i < groupnum; i++) {
    mids[i] = list[a+i*5+2];         //将中位数放入数组中；
  }
  if (restnumb != 0) {
    mids[groupnum] = list[a+groupnum*5+(restnumb-1)/2];  
  }
  T x;
  if(restnumb==0){                     //利用递归找中位数的中位数；
    x = select(mids, 0, groupnum-1, (groupnum-1)/2+1);
  }
  else {
    x = select(mids, 0, groupnum, (groupnum) / 2 + 1);
  }
  delete[]mids;                       //释放我们的临时空间mids；
  int i = partition(list, a, b,x);    //以x为划分基准；
  int j = i + 1 - a;
  if (k <= j) {
    return select(list, a, i, k);     //左子串递归搜寻第k小；
  }
  else {
    return select(list, i + 1, b, k - j);
  }                                   //右子串递归搜寻第k-j小，即为整个串的第k小；
}