一、 实验目的
1．加深学生对算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；
2．提高学生利用课堂所学知识解决实际问题的能力；
3．提高学生综合应用所学知识解决实际问题的能力。
二、实验任务
1、排序算法
目前已知有几十种排序算法，请查找资料，并尽可能多地实现多种排序算法（至少实现 8
种）并分析算法的时间复杂度。比较各种算法的优劣。
2、三壶谜题：
有一个充满水的 8 品脱的水壶和两个空水壶（容积分别是 5 品脱和 3 品脱）。通过将水
壶完全倒满水和将水壶的水完全倒空这两种方式，在其中的一个水壶中得到 4 品脱的水。
3、交替放置的碟子
我们有数量为 2n 的一排碟子，n 黑 n 白交替放置：黑，白，黑，白…
现在要把黑碟子都放在右边，白碟子都放在左边，但只允许通过互换相邻碟子的位置来实现
。为该谜题写个算法，并确定该算法需要执行的换位次数。
4、带锁的门：
在走廊上有 n 个带锁的门，从 1 到 n 依次编号。最初所有的门都是关着的。我们从门前
经过 n 次，每次都从 1 号门开始。在第 i 次经过时（i = 1,2，..., n)我们改变 i 的整数倍号锁的
状态；如果门是关的，就打开它；如果门是打开的，就关上它。在最后一次经过后，哪些门
是打开的，哪些门是关上的？有多少打开的门？
三、实验设备及编程开发工具
实验设备：Win10 电脑
开发工具：Dev-C++
四、实验过程设计（算法思路及描述，代码设计）
1. 选择排序
- 描述： 一种简单直观的排序算法。它的工作原理是：每次找出第 i 小的元素（也就
是 A_{i..n} 中最小的元素）然后将这个元素与数组第 i 个位置上的元素交换。
- 代码实现:
void selection_sort(int* a, int n) {
for (int i = 0; i < n-1; ++i) {
int index = i;
for (int j = i + 1; j < n; ++j)
if (a[index] > a[j])
index = j;
std::swap(a[i], a[index]);
}
}
2. 冒泡排序
- 描述： 一种简单的排序算法。它的工作原理是每次检查相邻两个元素，如果前面的元
素与后面的元素满足给定的排序条件就将相邻两个元素交换。当没有相邻的元素需要交换时，
排序就完成了。经过 i 次扫描后，数列的末尾 i 项必然是最大的 i 项因此冒泡排序最多需要
扫描 n-1 遍数组就能完成排序
- 代码实现:
void bubble_sort(int* a, int n) {
bool flag = true; // 用于判断当前轮是否有序
int k = 1;
while (flag) {
flag = false;
for (int i = 0; i < n-1; ++i) {
if (a[i] > a[i + 1]) {
flag = true;
std::swap(a[i], a[i+1]);
}
}
}
}
3. 插入排序
- 描述： 一种简单直观的排序算法。它的工作原理是将待排列元素划分为「已排序」
和「未排序」两部分每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确
位置与打扑克类似
- 代码实现:
void insertion_sort(int* a, int n) {
for (int i = 1; i < n; ++i) {
int key = a[i];
int index = i - 1;
while (index >= 0 && a[index] > key) {
a[index + 1] = a[index];
index--;
}
a[index + 1] = key;
}
}
4. 折半插入排序
- 描述：通过二分算法优化性能，在排序元素数量较多时优化的效果比较明显。通过二分
查找插入位置
- 代码实现：
void insertion_binary_sort(int* a, int n) {
if (n < 2) return;
for (int i = 1; i < n; ++i) {
int key = a[i];
int index = std::upper_bound(a, a + i, key) - a;
// 使用 std::copy_backward 移动元素
std::copy_backward(a + index, a + i, a + i + 1);
a[index] = key;
}
}
5. 计数排序
- 描述：使用一个额外的数组 C，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的
个数然后根据数组 C 来将 A 中的元素排到正确的位置。1.计算每个数出现了几次； 2.求出
每个数出现次数的 前缀和； 3.利用出现次数的前缀和，从右至左计算每个数的排名。
- 代码实现：
void counting_sort(int* a, int n) {
int w = 0;
for (int i = 0; i < n; ++i) w = max(w, a[i]);
int cnt[w];
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < n; ++i) ++cnt[a[i]];
int j = 0;
for (int i = 0; i < w; i++)
while (cnt[i]--) a[j++] = i;
}
6. 快速排序
- 描述：工作原理是通过 分治 的方式来将一个数组排序。1.将数列划分为两部分（要求
保证相对大小关系）； 2.递归到两个子序列中分别进行快速排序； 3.不用合并，因为此时数
列已经完全有序。
- 代码实现：
void quick_sort(int* a, int l, int r) {
int i = l, j = r, tmp = a[l];
if(i > j) return;
while(i != j) {
while(a[j] >= tmp && j > i) j--;
while(a[i] <= tmp && j > i) i++;
if(j > i) std::swap(a[i], a[j]);
}
a[l] = a[i];
a[i] = tmp;
quick_sort(a, l, i-1);
quick_sort(a, i+1, r);
}
7. 归并排序
- 描述：归并排序最核心的部分是合并（merge）过程：将两个有序的数组 a[i] 和 b[j] 合
并为一个有序数组 c[k]。从左往右枚举 a[i] 和 b[j]，找出最小的值并放入数组 c[k]；重复
上述过程直到 a[i] 和 b[j] 有一个为空时，将另一个数组剩下的元素放入 c[k]。为保证排
序的稳定性，前段首元素小于或等于后段首元素时（a[i] <= b[j]）就要作为最小值放入
c[k]。
- 代码实现：
void merge(int *a, int * tmp, int l, int mid, int r) {
int i = l, j = mid+1, k = l;
while(i!=mid+1 && j!=r+1) {
if(a[i] > a[j]) tmp[k++] = a[j++];
else tmp[k++] = a[i++];
}
while(i != mid+1) tmp[k++] = a[i++];
while(j != r+1) tmp[k++] = a[j++];
for(i=l; i<=r; i++) a[i] = tmp[i];
}
void merge_sort(int* a, int* tmp, int l, int r) {
int mid;
if(l < r){
mid = l + (r-l) / 2;
merge_sort(a, tmp, l, mid);
merge_sort(a, tmp, mid+1, r);
merge(a, tmp, l, mid, r);
}
}
8. 堆排序
- 描述：首先建立大顶堆，然后将堆顶的元素取出，作为最大值，与数组尾部的元素交换，
并维持残余堆的性质；之后将堆顶的元素取出，作为次大值，与数组倒数第二位元素交换，
并维持残余堆的性质；以此类推，在第 n-1 次操作后，整个数组就完成了排序。
- 代码实现：
void sift_down(int *a, int start, int end) {
int parent = start;
int child = parent * 2 + 1;
while (child <= end) {
if (child + 1 <= end && a[child] < a[child + 1]) child++;
if (a[parent] >= a[child]) return;
else {
std::swap(a[parent], a[child]);
parent = child;
child = parent * 2 + 1;
}
}
}
void heap_sort(int a[], int n) {
for (int i = (n - 1 - 1) / 2; i >= 0; i--) sift_down(a, i, n - 1);
for (int i = n - 1; i > 0; i--) {
swap(a[0], a[i]);
sift_down(a, 0, i - 1);
}
}
（二）、三壶谜题
1、算法分析：
可以把每次三个水壶中水量设成一组状态，比如初始状态为 008，对应第一个水壶 0 品
脱水，第二个水壶 0 品脱水，第三个水壶 8 品脱水。对题目的状态空间图进行广度优先遍历。
当表示状态的数字中出现 4 时，即求出答案。
（1）打印倒水的过程，需要声明一个前置状态保存当前状态由哪个状态转换而来，然后就
可以回溯到初始状态，打印出倒水过程。
（2）声明一个 map 表，保存已有的状态，对已有的状态就不再向下继续遍历。
（3）因为是广度优先遍历，所以第一次得到的答案所需的倒水次数最少，即为最优解。
2、代码实现：
#include <iostream>
#include <vector>
#include <map>
#define MaxFirst 3
