舍伍德算法

舍伍德算法主要解決算法中，避免輸入所産生的時間複雜度遠遠超過平均時間的情況。例如快速排序或者線性時間選擇中，對劃分标準用機率來選取可以在很大程度上避免最壞的情況。下面是線性時間選擇算法：

// 舍伍德.cpp : 定義控制台應用程式的入口點。

//

#include "stdafx.h"

#include "targetver.h"

#include <stdio.h>

#include <tchar.h>

#include "stdafx.h"

#include"iostream"

#include<math.h>

#include<time.h>

#include<iomanip>

using namespace std;

const unsigned long maxshort=65535L;

const unsigned long multiplier=1194211693L;

const unsigned long adder=12345L;

const int INF=9999;

class RandomNumber{

private:

 //目前種子

 unsigned long randSeed;

public:

 //構造函數

 RandomNumber(unsigned long s=0);

 unsigned short Random(unsigned long n);

 double fRandom();

};

RandomNumber::RandomNumber(unsigned long s)

{

 if(s==0)

  randSeed=time(0);

 else

  randSeed=s;

}

double RandomNumber::fRandom()

{

 return Random(maxshort)/double(maxshort);

}

unsigned short RandomNumber::Random(unsigned long n)

{

 randSeed=multiplier*randSeed+adder;

 return (unsigned short)((randSeed>>16)%n);

}

//template <typename Type>

void Swap(int &a,int &b)

{

 int temp;

 temp=a;

 a=b;

 b=temp;

}

//template <typename Type>

int select(int a[],int lt,int rt,int k)

{

 //計算a[lt:rt]中第k小元素

 static RandomNumber rnd;

 while(true)

 {

  if(lt>rt)

   return a[lt];

  int i=lt,j=lt+rnd.Random(rt-lt+1);//随機選擇劃分基準

  Swap(a[i],a[j]);

  j=rt+1;

  int pivot=a[lt];

  while(true)

  {

   while(a[++i]<pivot);//循環找資料

   while(a[--j]>pivot);

   if(i>=j)

    break;

   Swap(a[i],a[j]);

  }

    if(j-lt+1==k)

  return pivot;

 a[lt]=a[j];

    a[j]=pivot;

 //對子數組重複劃分過程

 if(j-lt+1<k)

 {

  k=k-j+lt-1;

  lt=j+1;

 }

 else

  rt=j-1;

 }

}

//template <typename Type>

int Select(int a[],int n,int k)

{

 if(k<1||k>n)

  cerr<<"Wrong!"<<endl;

 return select(a,0,n-1,k);

}

int _tmain(int argc, _TCHAR* argv[])

{

 int arr[7]={3,2,5,7,10,INF};

 cout<<Select(arr,6,5)<<endl;

 int x;

 cin>>x;

 return 0;

}