随机化算法实验（Sherwood型线性时间选择）
本次实验的主要目的是掌握 Sherwood 型线性时间选择算法的设计思想、程序设计和实现。 Sherwood 型线性时间选择算法是一种随机化算法，通过随机选择基准元素来实现选择数组中的中值。
实验目的：
1. 掌握 Sherwood 型线性时间选择算法的设计思想和实现方法。
2. 了解随机化算法在解决选择问题中的应用。
3. 实现 Sherwood 型线性时间选择算法的程序设计和实现。
实验内容：
1. 问题描述：给定任意几组数据，利用舍伍德型选择算法，找出数组中的中值并输出（若数组为奇数个则输出中值，若数组为偶数个则输出第 n/2 小元素）。
2. 算法设计思想：Sherwood 型线性时间选择算法的设计思想是通过随机选择基准元素来实现选择数组中的中值。
3. 程序设计：实现 Sherwood 型线性时间选择算法的程序设计，包括随机选择基准元素、元素交换和判断基准值是否就是所需选择的数。
实验步骤：
1. 判断是否需要进行随机划分，即判断数组的规模是否大于 1。
2. 产生随机数 j，选择划分基准，将 a[j] 与 a[l] 交换。
3. 以划分基准为轴做元素交换，使得一侧数组小于基准值，另一侧数组值大于基准值。
4. 判断基准值是否就是所需选择的数，若是，则输出；若不是对子数组重复步骤 (2)(3)(4)。
随机化算法的实现：
1. 随机划分基准处理：随机选择基准元素，并将其与数组的第一个元素交换。
2. 随机洗牌预处理：将数组元素洗牌，重新排序，以便选择基准元素。
实验结果：
通过实验，我们可以看出 Sherwood 型线性时间选择算法的实现可以达到选择数组中的中值的目的，并且可以在不同的输入规模下保持良好的性能。
实验分析：
1. Sherwood 型线性时间选择算法的设计思想是通过随机选择基准元素来实现选择数组中的中值。
2. 随机化算法可以改善其他确定性算法的性能。
3. 通过实验，我们可以看到随机化算法的实现可以达到良好的性能。
代码实现：
```cpp
template <class Type>
Type select(Type a[], int l, int r, int k) {
if (l >= r) {
return a[l];
}
// 随机选择基准元素
int j = l + rand() % (r - l + 1);
Swap(a[j], a[l]);
// 判断基准值是否就是所需选择的数
if (j - l + 1 == k) {
return a[j];
} else if (j - l + 1 > k) {
return select(a, l, j - 1, k);
} else {
return select(a, j + 1, r, k - (j - l + 1));
}
}
template <class Type>
void Shuffle(Type a[], int n) {
for (int i = 0; i < n; i++) {
int j = rand() % (n - i) + i;
Swap(a[i], a[j]);
}
}
```
通过实验，我们可以掌握 Sherwood 型线性时间选择算法的设计思想和实现方法，并了解随机化算法在解决选择问题中的应用。
