一、 实验目的
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电脑
开发工具：jdk1.8、IDEA
四、实验过程设计（算法思路及描述，代码设计）
1、排序算法
（1）冒泡排序
1）从第一个数开始，比较相邻的两个数，如果第一个数比第二个数大，则两数交换。
2）对后面的元素进行同样的操作，从开始到最后一个，这样进行一次排序后，数据的最后一位会是最大的。
3）重复上述步骤，直到在一次排序中无交换之后，排序完成。
代码：
public class Maopao {public static void main(String[] args) {int[] array1 = {1,10,5,8,6,4}; bubbleSort(array1);for(int i=0;i<array1.length;i++){System.out.print(array1[i]+" ");}}public static void bubbleSort(int[] array){int tmp;boolean flag = false; //设置是否发生交换的标志for(int i = array.length-1;i >= 0;i--){for(int j=0;j<i;j++){ if(array[j]>array[j+1]){tmp = array[j];array[j] = array[j+1];array[j+1] = tmp;flag = true; //发生了交换}}if(!flag) break; //没有发生交换，排序完成，退出循环}}
}冒泡排序
最好的时间复杂度为O(n)，最坏时间复杂度为O(n2)，平均时间复杂度为O(n2)。
结果：
（2）插入排序
1）第一次循环时，从第2个数开始处理。我们将第1个数作为已经排好序的数据：当第2个数 > 第1个数时，将第2个数放在第1个数后面一个位置；否则，将第2个数放在第1个数前面。此时，前两个数形成了一个有序的数据。
2）第二次循环时，我们处理第3个数。此时，前两个数形成了一个有序的数据：首先比较第3个数和第2个数，当第3个数 > 第2个数时，将第3个数放在第2个数后面一个位置并结束此次循环；否则，再和第1个数比较。如果第3个数 > 第1个数，则将第3个数插入第1个数和第2个数中间；否则，第3个数 < 第1个数，则将第3个数放在第1个数前面。此时，前三个数形成了一个有序的数据。
3）后续的数据同理处理，直至结束。
代码：
public class Charu {public static void main(String[] args) {int[] array1 = {1,10,35,8,6,44}; insertionSort(array1);for(int i=0;i<array1.length;i++){System.out.print(array1[i]+" ");}}public static void insertionSort(int[] array){int tmp;for(int i=0;i<array.length;i++){tmp = array[i]; //将当前位置的数给tmpint j = i;for(;j>0&&array[j-1]>tmp;j--){array[j] = array[j-1];}//将当前位置的数插入到合适的位置array[j] = tmp;}}
}插入排序
最好的时间复杂度为O(n)，最坏时间复杂度为O(n2)，平均时间复杂度为O(n2)。
结果：
（3）选择排序
首先在未排序的数列中找到最小元素，然后将其存放到数列的起始位置。接着，再从剩余未排序的元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
代码：
public class Xuanze {public static void main(String[] args) {int[] array1 = {1,10,35,8,6,44}; selectSort(array1);for(int i=0;i<array1.length;i++){System.out.print(array1[i]+" ");}}public static void selectSort(int[] array){for(int i = 0;i<array.length;i++){int min = array[i];int minindex = i;for(int j = i;j<array.length;j++){if(array[j]<min){ //选择当前最小的数min = array[j];minindex = j;}}if(i != minindex){ //若i不是当前元素最小的，则和找到的那个元素交换array[minindex] = array[i];array[i] = min;}}}
}选择排序
最好的时间复杂度为O(n2)，最坏时间复杂度为O(n2)，平均时间复杂度为O(n^2)。
结果：
（4）希尔排序
1）比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，算法先将要排序的一组数按某个增量d分成若干组。
2）对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。
3）当增量减到1时，整个要排序的数被分成一组，排序完成。
4）一般的初次取序列的一半为增量，以后每次减半，直到增量为1。
代码：
public class Xier{public static void main(String[] args) {int[] array1 = {22,10,55,87,66,44}; ShellSort(array1);for (int i = 0; i < array1.length; i++) {System.out.print(array1[i]+" ");}}public static int[] ShellSort(int[] array) {int len = array.length;int temp, gap = len / 2;while (gap > 0) {for (int i = gap; i < len; i++) {temp = array[i];int preIndex = i - gap;while (preIndex >= 0 && array[preIndex] > temp) {array[preIndex + gap] = array[preIndex];preIndex -= gap;}array[preIndex + gap] = temp;}gap /= 2;}return array;}
}希尔排序
最好的时间复杂度为O(nlog2 n)，最坏时间复杂度为O(nlog2 n)，平均时间复杂度为O(nlog2n)
结果：
（5）快速排序
1）从数列中挑出一个元素，称为"基准"，重新排序数列。
2）所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。从而一趟排序过程，就可以锁定基准元素的最终位置。
3）对左右两个分块重复以上步骤直到所有元素都是有序的。
代码：
public class Kuaisu {public static void main(String[] args) {int[] array1 = {22,10,55,87,66,44}; quickSort(array1);for(int i=0;i<array1.length;i++){System.out.print(array1[i]+" ");}}public static void quickSort(int[] arr) {qsort(arr, 0, arr.length - 1);}private static void qsort(int[] arr, int low, int high) {if (low >= high) return;int pivot = partition(arr, low, high); //将数组分为两部分qsort(arr, low, pivot - 1); //递归排序左子数组qsort(arr, pivot + 1, high); //递归排序右子数组}private static int partition(int[] arr, int low, int high) {int pivot = arr[low]; //基准while (low < high) {while (low < high && arr[high] >= pivot) --high;arr[low] = arr[high]; //交换比基准大的记录到左端while (low < high && arr[low] <= pivot) ++low;arr[high] = arr[low]; //交换比基准小的记录到右端}//扫描完成，基准到位arr[low] = pivot;//返回的是基准的位置return low;}
}（6）基数排序
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
代码：
import java.util.ArrayList;public class Paixu {public static void main(String[] args) {int[] array1 = {25,8,55,87,66,44}; RadixSort(array1);for (int i = 0; i < array1.length; i++) {System.out.print(array1[i]+" ");}}public static int[] RadixSort(int[] array) {if (array == null || array.length < 2)return array;// 1.先算出最大数的位数；int max = array[0];for (int i = 1; i < array.length; i++) {max = Math.max(max, array[i]);}int maxDigit = 0;while (max != 0) {max /= 10;maxDigit++;}int mod = 10, div = 1;ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();for (int i = 0; i < 10; i++)bucketList.add(new ArrayList<Integer>());for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {for (int j = 0; j < array.length; j++) {int num = (array[j] % mod) / div;bucketList.get(num).add(array[j]);}int index = 0;for (int j = 0; j < bucketList.size(); j++) {for (int k = 0; k < bucketList.get(j).size(); k++)array[index++] = bucketList.get(j).get(k);bucketList.get(j).clear();}}return array;}
}基数排序
最好的时间复杂度为O(nk)，最坏时间复杂度为O(nk)，平均时间复杂度为O(n*k)
结果：
2、三壶谜题
1）本题使用广度优先遍历来进行计算。刚开始我们可以将三个瓶子的状态都标示为一个数。例如800
2）然后开始拓展这个数的所有可能的状态，第一步这个数可以变为（括号里的数是上一步的数字）：3 5 0（8 0 0） 、 5 0 3（8 0 0）。
3）然后继续拓展第二步所有可能的状态，并且不得和之前的状态出现重复，即进行剪枝：0 5 3（3 5 0）、3 2 3（3 5 0）、5 3 0（5 0 3）
4）继续进行同样操作，一直到第六步，出现1 4 3（1 5 2），这时候就应该停止了。因为出现了第一个数字4，满足了条件。所以最终的路径就是：143 <-- 152 <-- 602 <-- 620 <-- 323 <-- 350 <-- 800
代码:
import java.util.*;
public class Sanhu {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("请输入三个值表示容器的初始状态,三个瓶子的容积目前是8，5，3：");int x1 = sc.nextInt();int x2 = sc.nextInt();int x3 = sc.nextInt();String string = x1+""+x2+""+x3;System.out.println(string);ContainerPot containerPot = new ContainerPot(8, 0, 0);List<String> list = new ArrayList<String>(); //保存状态list.add(string); //将第一个状态存入到状态数组中containerPot.init();//初始化这些瓶子可以装多少水String result = "";//保存最终带有4的结果int n = 0;//状态计数do {//遍历倒水for (int i = 0; i < 3 && containerPot.flag; i++) {for (int j = 0; j < 3 && containerPot.flag; j++) {if (i != j) { //不能让壶相同if (containerPot.canPour(i, j)) { //是否可以倒水String str = containerPot.getString();//保存初始状态//倒入水containerPot.pour(i, j);String strResult = containerPot.getString();if (!list.contains(strResult)) {list.add(strResult);containerPot.addList(str, strResult);}//如果出现容量为4的壶就停止if (containerPot.pot[0] == 4 || containerPot.pot[1] == 4 || containerPot.pot[2] == 4) {result = result + containerPot.pot[0] + containerPot.pot[1] + containerPot.pot[2];containerPot.flag = false;//已经找到break;}//初始化倒水到上一步containerPot.intPot(str);}}}}n++;containerPot.intPot(list.get(n));} while (containerPot.flag);System.out.println(list);System.out.println(containerPot.listMap);String key = result;System.out.print(key + "<--");do {for (Map.Entry<String, List<String>> entry : containerPot.listMap.entrySet()) {for (int i = 0; i < entry.getValue().size(); i++) {if (entry.getValue().get(i).equals(key)) {System.out.print(entry.getKey() + "<--");key = entry.getKey();break;}}}} while (containerPot.listMap.containsKey(key) && !key.equals(string));System.out.println();}
}import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;public class ContainerPot {int[] pot = new int[3];// List<String> list;//存放已经出现的结果Map<String, List<String>> listMap = new HashMap<>();int[] maxP = new int[3];boolean flag = true;public ContainerPot(int a, int b, int c) {pot[0] = a;pot[1] = b;pot[2] = c;}public void init() {maxP[0] = 8;maxP[1] = 5;maxP[2] = 3;}//将key值作为它的上一步public void addList(String key, String str) {if (listMap.isEmpty() || !listMap.containsKey(key)) {List<String> temp = new ArrayList<String>();temp.add(str);listMap.put(key, temp);} else {
// System.out.println(listMap.containsKey(key));
// System.out.println(listMap.get(key));listMap.get(key).add(str);}}//判读是否已经有这个key值在里面存放了public boolean isAdd(String str) {return listMap.containsKey(str);}//判读是否可以从from壶倒水到to壶public boolean canPour(int from, int to) {//如果没用水就不能倒了if (pot[from] == 0) {return false;}//如果里面已经有水了 就不能倒了if (pot[to] == maxP[to]) {return false;} else {return true;}}//倒水的过程public void pour(int from, int to) {//做一个判读看看是否能剩水if (pot[from] + pot[to] > maxP[to]) {pot[from] = pot[from] - (maxP[to] - pot[to]);pot[to] = maxP[to];} else {pot[to] = pot[to] + pot[from];pot[from] = 0;}}public String getString() {String str = "";for (int i = 0; i < pot.length; i++) {str = str + pot[i];}return str;}public void intPot(String str) {for (int i = 0; i < str.length(); i++) {pot[i] = Integer.parseInt(String.valueOf(str.charAt(i)));}}public void printDD() {for (List<String> value : listMap.values()) {System.out.println(value.toString());}}
}三壶谜题
时间复杂度为O（n^2）
结果：
3、交替放置的碟子
将所有碟子存放在一个数组里，设白碟子为1，黑碟子为0，使其经过若干次冒泡排序的交换，将所有的黑碟子都放在右边，白碟子都放在左边。
代码：
import java.util.Scanner;
public class Jiaoti{public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("请输入碟子的数量2n，其中黑白碟子各n个：");int num=sc.nextInt();//从控制台接受碟子数量int sum[]=new int[num];for(int i=0;i<=(sum.length-1)/2;i++) {sum[2*i]=0;sum[2*i+1]=1;}System.out.println("碟子的初始排序为：");for(int i=0;i<sum.length;i++) {System.out.print(sum[i]+" ");if(sum[i]==1) {System.out.print("白"+" ");}else {System.out.print("黑"+" ");}}System.out.println();//换行/** 进行排序 冒泡排序*/int k = 0;for(int i=0;i<sum.length-1;i++) {for(int j=0;j<sum.length-1-i;j++) {if(sum[j+1]>sum[j]) {int t=sum[j];sum[j]=sum[j+1];sum[j+1]=t;k++;}}}System.out.println("交换的次数为："+ k);System.out.println("排序后的顺序为：");for(int i=0;i<sum.length;i++) {System.out.print(sum[i]+" ");if(sum[i]==1) {System.out.print("白"+" ");}else {System.out.print("黑"+" ");}}}
}交替放置的碟子
时间复杂度为O（n）
结果：
4、带锁的门
1）这道题需要统计从1到n每个数的因子个数（包括1和自身），每个数的因子个数决定了它代表的门被改变锁状态的次数，若i有奇数个因子，则第i号门最终是开着的，若i有偶数个因子，则第i号门最终仍然是关着的。
2）大多数情况下，每个数的因子是成对出现的，例如数15的因子有1和15，以及3和5，数12的因子有1和12，2和6，3和4，所以有偶数个因子。只有当这个数是完全平方数时，例如1,4,9,16,25,36等等，它的因子除成对出现的以外，还有它的整数平方根作为单独的因子，这些完全平方数的因子数为奇数。所以最终打开的门都会是完全平方数的门。
代码：
import java.util.ArrayList;
import java.util.Scanner;public class Daisuo {public static void main(String[] args){System.out.println("请输入带锁的门的个数：");int n = new Scanner(System.in).nextInt(); int sum = 0;ArrayList<Integer> open = new ArrayList<>();for(int i=1;i*i<=n;i++){open.add(i*i);sum++;}ArrayList<Integer> close=new ArrayList<>();for(int i=1;i<=n;i++){if(!open.contains(i)) //用于判断是否包含某个元素close.add(i);}System.out.println("打开的门的编号为：");for(Integer integer:open){System.out.print(integer +" ");}System.out.println("");System.out.println("关着的门的编号为：");for(Integer integer:close){System.out.print(integer +" ");}System.out.println("");System.out.println("打开的门的个数为："+ sum);}
}带锁的门
时间复杂度为O（n）
结果：
