实验一、归并排序及各种排序算法性能比较一、实验实习目的及要求了解归并排序等各种排序算法，并能独立在计算机上实现，同时并能够计算它们的时间复杂度，并用计算机来验证。

二、实验实习设备（环境）及要求（软硬件条件）计算机eclipse软件，执行环境JavaSE-1.8.三、实验实习项目、内容与步骤(注意是主要关键步骤，适当文字+代码+截图说明)项目：对10 4 6 3 8 2 5 7进行从小到大排序，采用几种排序方法，并统计这几种方法的运行时间，与归并排序比较。

内容及步骤：(1)归并排序：将序列每次分成两组，再进行合并，直到递归完成；1、递归调用mergeSort对数组排序2、merge将两个有序数组合并为一个有序数组3、主函数调用mergeSort对数组排序4、统计时间(2) 选择排序：每次选择一个当前最小的并和当前的相对的第一个元素交换，直到最后只有一个元素时结束；也可选择当前最大的并与当前的相对的最后一个元素交换，直到最后只有一个元素时结束。

1、数组长度为n，需要选择n-1次；每次选择完成后，将数组中的最大值与最后一个元素互换，调用java.util包中Arrays类。

2、主函数调用ChooseSort对数组排序。

3、统计运行时间。

(3)插入排序：从第二个元素开始，每次插入一个到当前有序序列中，使得有序，当所有的元素插入完毕时，就排好序了；1、从第二个元素开始，与之前序列比较，插入到合适的位置。

2、主函数调用sort对数组排序。

3、统计运行时间(4) 快速排序：每次选择一个中间元素，并进行交换，使得中间元素的左边比它小，右边比它大，然后对左右两边进行递归；1、选取一个基准位，从右边向左边看，找比基准位小的元素，再从左边向右边看，找比基准位大的元素，若两者均存在则交换；若两者相遇，则相遇元素与基准位元素交换，然后递归排序左右半数组。

2、主函数调用quickSort对函数排序3、统计运行时间(5) 堆排序：采用插入的模式产生堆，然后把根交换到最后，在形成一个堆，再把根与当前最后一个交换，如此，直到最后只剩下一个元素；1、升序方式采用大顶堆，由父节点与左右子节点对应元素比较，将较大元素的位置改为对应子节点，若不为最大，需要交换最大的，递归处理其余堆。

2、从最后一个非叶子节点开始，即最后一个叶子节点的父节点，调用maxHeap，完成后，第一个元素与最后一个元素互换，此时最后一个元素固定，递归调用maxHeap，直至最后一个元素停止。

3、主函数调用heapSort 对数组进行排序4、统计程序运行时间四、实验实习结果及分析实验结果： (1)归并排序(2)选择排序(3)插入排序(4)快速排序(5)堆排序分析：上述五种排序方法中，选择排序与堆排序的运行时间相当，而归并排序与插入排序和快速排序相当，前两种方法的运行时间比后三种方法短。

但一则例子不能完全表明哪种方法的优劣，需要对特定的目标采取合适的方法。

归并排序：最差时间复杂度和最优时间复杂度都为。

虽然比较稳定，在时间上也非常有效，但却很消耗空间，一般在内部排序不会采用这种方法，而采用快速排序，外部排序会考虑使用这种方法。

(log )O n n选择排序：最差时间复杂度和最优时间复杂度都为。

该方法是不稳定的。

插入排序：最优时间复杂度为，对应待排序列已有序；最差时间复杂度为。

因为在有序部分元素和待插入元素相等的时候，可以将待插入的元素放在前面，所以插入排序是稳定的。

快速排序：最优时间复杂度为，每次取到的元素都刚好使待排序列中分；最差时间复杂度为，每次取到的元素都是数组中的最大值或最小值，即已排好的序列。

因为在快速排序的时候，即使待排序元素可基数相等也需要移动待排序元素的位置使得有序，所以快速排序是不稳定的。

堆排序：堆排序的时间复杂度主要在初始化堆过程和每次选取最大数后重新建堆的过程。

初始化建堆过程：，更改堆元素后重建堆：，于是堆排序的时间复杂度为。

该方法是不稳定的。

实验二、背包问题一、实验实习目的及要求了解0-1背包问题的原理和解决问题的各种算法，掌握编程实现动态规划法，贪心算法，回溯法及分支界限法四种方法解决0-1背包问题的方法。

分析比较各算法的优劣。

二、实验实习设备（环境）及要求（软硬件条件）计算机eclipse 软件，执行环境JavaSE-1.8. 三、实验实习项目、内容与步骤项目：分别运用动态规划法，贪心算法，回溯法及分支界限法解决0-1背包问题并比较各算法的优劣。

内容及步骤： (1)动态规划法1、定义二维数组F[i][j]表示前i 个物品在限重为j 的最大价值，以及各物品的重量与价值。

2()O n ()O n ()O n2、对价值二维数组初始化，背包是否加入下一个物品进行判断。

3、表示所有价值数组元素构成矩阵并判断选取哪些物品使价值最大。

4、键入各物品的重量与价值，主函数调用求解问题。

(2)贪心算法1、键入背包的容量和待装物品的重量与价值。

2、定义贪婪准则对带装物品进行降序排序3、判断待装物品进行装包判断以及计算最大价值。

(3)回溯法1、键入背包的容量和待装物品的重量与价值。

2、对搜索方向进行判定，以及确定在下界停止，递归操作，寻找最优路径。

3、计算剩余物品的最高价值上界。

4、主函数调用求解最优解。

(4)分支界限法1、定义背包的容量和待装物品的重量与价值。

2、队列式分支限界，即若当前分支的“装载的价值上界”，比现有的最大装载的价值小，则该分支就无需继续搜索。

3、操作节点定义放入物品或不放入物品其当前重量与价值4、获得背包中价值上限以及最大价值5、主函数对键入数据计算四、实验实习结果及分析实验结果：(1)动态规划法：(2)贪心算法：(3)回溯法：(4)分支界限法：分析：对于同一数据下的0/1背包问题，从结果上，动态规划法与分支限界法的效果较优，回溯法次之，贪心算法效果最差。

动态规划算法通常基于一个递推公式及一个或多个初始状态。

当前子问题的解将由上一次子问题的解推出。

使用动态规划来解题只需要多项式时间复杂度，因此它比回溯法、暴力法等要快许多。

回溯法是一个既带有系统性又带有跳跃性的搜索算法。

它在包含问题的所有解的解空间树中按照深度优先的策略，从根节点出发搜索解空间树。

算法搜索至解空间树的任一节点时，总是先判断该节点是否肯定不包含问题的解。

如果肯定不包含，则跳过对以该节点为根的子树的系统搜索，逐层向其原先节点回溯。

否则，进入该子树，继续按深度优先的策略进行搜索。

需执行三步，分别为针对所给问题，定义问题的解空间、确定易于搜索的解空间结构、以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

贪心算法是指在对问题进行求解时，总是做出当前看来是最好的选择。

也就是说，不从整体最优上加以考虑，所得出的结果仅仅是某种意义上的局部最优解。

因此贪心算法不会对所有问题都能得到整体最优解，但对于很多问题能产生整体最优解或整体最优解的近似解。

贪心算法适用的情况很少。

一般，对一个问题分析是否适用于贪心算法，可以先选择几个实际数据进行分析，就可做出判断。

然而，贪心算法的策略构造一般是简单的，因此只要证明策略是正确的，即局部最优策略能导致产生全局最优解。

那么，2、定义最短路径长度、判断某点是否求出和存储输出路径并初始化；3、选取出发点到目标点的多条路径中的最短线路并打印；4、调用dijkstra算法计算最短路径。

四、实验实习结果及分析实验测试：某一个七个顶点八条边的有向图，以下键入相关数据(取0为源点)：实验结果：实验分析：该测试实验确实得到了正确结果。

但还没有测试其他，存在缺陷。

Dijkstra算法本质上是贪心算法，下一条路径都是由当前更短的路径派生出来的更长的路径。

不存在回溯的过程。

如果权值存在负数，那么被派生出来的可能是更短的路径，这就需要过程可以回溯，之前的路径需要被更短的路径替换掉，而Dijkstra算法是不能回溯的。

它每一步都是以当前最优选择为前提的。

实验四、采用普里姆(prim)算法构造网络的最小生成树一、实验实习目的及要求深入理解最小生成树的概念，熟练掌握普里姆（prim）算法的工作过程，在计算机上实现。

二、实验实习设备（环境）及要求（软硬件条件）计算机eclipse软件，执行环境JavaSE-1.8.三、实验实习项目、内容与步骤(注意是主要关键步骤，适当文字+代码+截图说明)实习项目：编制普里姆算法的程序，同时寻找两个结点大于6的网络，运行程序，记录程序的运行结果，根据结果画出最小生成树，并与手工生成的最小生成树进行比较。

实验内容及步骤：对以下图的最小生成树1、建立一个数组由于记录顶点是否被遍历，选取初始点为顶点02、若遍历顶点数等于给定顶点数，则退出循环；若还存在顶点未被遍历，则遍历相邻顶点中权重最小的边对应的顶点。

最后打印对图顶点的访问顺序3、对给出图写出邻接矩阵，主函数中调用getMinTree类，求解最小生成树四、实验实习结果及分析算法的结果：手工计算的结果：分析：计算机的结果与手工计算的结果一致。

prim算法也是贪婪算法的一个典型例子，有点类似于dijkstra算法。

实验五、采用克鲁斯卡尔(kruskal)算法构造网络的最小生成树一、实验实习目的及要求深入理解最小生成树的概念，熟练掌握克鲁斯卡尔（kruskal）算法的工作过程，用计算机语言实现。

二、实验实习设备（环境）及要求（软硬件条件）计算机eclipse软件，执行环境JavaSE-1.8.三、实验实习项目、内容与步骤(注意是主要关键步骤，适当文字+代码+截图说明)实习项目: 编制克鲁斯卡尔算法的程序，同时寻找两个结点大于6的网络，运行程序，记录程序的运行结果，根据结果画出最小生成树，并与手工生成的最小生成树进行比较。

实验内容及步骤：对以下图的最小生成树1、键入图的顶点，边数及权值信息2、将键入边按权值进行排序3、建立储存顶点与边的数组，将权值最小的边及对应点存入数组中，选择下一条边时，对应的顶点不能出现再出现4、判断顶点不在数组中5、计算权值之和四、实验实习结果及分析对上图键入相关信息：知晓边数和顶点数后，下面的第一位为权值，后两位为关联点。

实验结果：手工计算结果：分析：上述结果不唯一，但最小生成树的权值之和保持不变。

Kruskal算法从边的角度求网的最小生成树，时间复杂度为，更适合于求边稀疏的网的最小生成树。

Prim算法从顶点的角度为出发点，时间复杂度为，更适合与解决边的绸密度更高的连通网。

对于任意一个连通网的最小生成树来说，在要求总的权值最小的情况下，最直接的想法就是将连通网中的所有边按照权值大小进行升序排序，从小到大依次选择。

实验六、回溯算法-符号三角形一、实验实习目的及要求深入理解符号三角形问题的算法，熟练掌握算法的工作过程，编写基于回溯算法的符号三角形的程序，输入计算机进行调试，准备顶点大于9的符号三角形，记录程序的运行结果。