迄今為止看的最全面的就是王曉東的《計算機算法設(shè)計與分析》里講的了。在網(wǎng)上查的一些資料也基本全和這本書上講的一樣，至于是這本書先寫的，還是其他位置先寫的，我就不做評論了。
* Author: Tanky woo
* Blog: www.WuTianQi.com
* Date: 2010.12.8
* 舍伍德(Sherwood)算法運用(1) -- 線性時間選擇算法
* 代碼來至王曉東《計算機算法設(shè)計與分析》
*/
#include "RandomNumber.h"
#include <iostream>
#include <iomanip>
#include <time.h>
using namespace std;
const int INF = 9999;
// 交換a, b的值
template <typename Type>
void Swap(Type &a, Type &b)
{
Type temp;
temp = a;
a = b;
b = temp;
}
template <typename Type>
Type select(Type 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); // 隨機選擇的劃分基準(zhǔn)
Swap(a[i], a[j]);
j = rt+1;
Type pivot = a[lt];
//以劃分基準(zhǔn)為軸作元素交換
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;
// 對子數(shù)組重復(fù)劃分過程
if(j - lt + 1 < k)
{
k = k - j + lt - 1;
lt = j + 1;
}
else
rt = j - 1;
}
}
template <typename Type>
Type Select(Type a[], int n, int k)
{
// 計算a[0: n-1]中第k小元素
// 假設(shè)a[n]是一個鍵值無窮大的元素
if(k < 1 || k > n)
cerr << "Wrong!" << endl;
return select(a, 0, n-1, k);
}
int main()
{
int arr[7] = {3, 2, 5, 7, 10, INF};
cout << Select(arr, 6, 4) << endl;
}
當(dāng)然，舍伍德算法也不是萬能的。有時也會遇到這樣的情況，即所給的確定性算法無法直接改造成舍伍德型算法。此時可借助于隨機預(yù)處理技術(shù)，不改變原有的確定性算法，僅對其輸入進行隨機洗牌，同樣可收到舍伍德算法的效果。
/*
* Author: Tanky woo
* Blog: www.WuTianQi.com
* Date: 2010.12.8
* 和舍伍德算法效果類似的一個程序 -- 隨機洗牌
* 代碼來至王曉東《計算機算法設(shè)計與分析》
*/
#include "RandomNumber.h"
#include <iostream>
#include <iomanip>
#include <time.h>
using namespace std;
// 交換a, b的值
template <typename Type>
void Swap(Type &a, Type &b)
{
Type temp;
temp = a;
a = b;
b = temp;
}
template <typename Type>
void Shuffle (Type a[], int len)
{
// 隨機洗牌算法
static RandomNumber rnd;
for (int i = 0; i < len; ++i)
{
int j = rnd.Random(len-i) + i;
Swap (a[i], a[j]) ;
}
}
template <typename Type>
void Print (Type a[], int len)
{
for(int i=0; i<len; ++i)
cout << a[i] << " ";
cout << endl;
}
int main()
{
int arr[10];
// 原先次序
for(int i=0; i<10; ++i)
arr[i] = i+1;
Print(arr, 10);
// 第一次洗牌
Shuffle(arr, 10);
Print(arr, 10);
// 第二次洗牌
Shuffle(arr, 10);
Print(arr, 10);
return 0;
}