选择排序算法实验报告.docx

算法设计与分析基础实验报告应用数学学院姓名：学号：班级：二零一六年六月实验 选择排序算法一、实验性质 设计二、实验学时 14学时三、实验目的1、掌握选择排序的方法和原理。2、掌握java语言实现该算法的一般流程。四、实验内容1、数组的输入。2、输入、输出的异常处理。3、选择排序的算法流程。4、运行结果的输出。五、实验报告、算法原理首先扫描整个列表，在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。然后从第二个元素开始扫描列表，找到最后n-1个元素中的最小元素，在和第二个元素交换位置，把第二小的元素放在它的最终位置上。一般来说，在对该列表做第i次扫描的时候（i的值从0到n-2），该算法在最后n - i个元素中寻找最小元素，然后拿它和Ai交换，在n-1遍以后就被排序好了。、书中源代码 算法 SelectionSort(A0.n-1) /该算法用选择排序对给定的数组排序 /输入：一个可排序数组A0.n-1 /输出：升序排列的数组A0.n-1 for i 0 to n-2 do min i for j i+1 to n-1 do if Aj Amin min j swap Ai and Amin、Java算法代码：import java.util.*;public class Xuanze public static void main(String args) int n = 5; int a = new intn; int i = 0, j = 0; int sm = 0, min = 0; System.out.println(请输入一组数字：); Scanner sc = new Scanner(System.in); try while (i n) ai=sc.nextInt(); i+; for (i = 0; i = n - 2; i+) min = i; for (j = i+1;j=n-1; j+) if (aj amin) min=j; sm = amin; amin = ai; ai = sm; System.out.println(选择排序输出结果为：); for (i = 0; i n; i+) System.out.println(ai); catch (Exception e) System.out.println(e); 、运行结果显示： 图（1） 图（2）、实验结论：选择排序是一个（n2）的算法，键的交换次数仅为（n）。或者是n-1次。择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。实验三 折半查找算法一、实验性质 设计二、实验学时 14学时三、实验目的1、掌握折半查找算法的方法和原理。2、掌握java语言实现该算法的一般流程。四、实验内容1、给定一个数组。2、输入、输出的异常处理。3、折半查找的算法流程。4、运行结果的输出。五、实验报告、算法原理 折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0ax，要查找的数是K,通过比较查找键K和数组中间元素Am来完成查找工作。如果他们相等，算法结束，否则，如果KAm,则对数组的后半部分执行该操作。、书中源代码 算法 BinarySearch(A0.n-1,K) /实现非递归的折半查找 /输入：一个可排序数组A0.n-1和一个查找键K /输出：一个数组的下标，该元素等于K；如果没有该元素，则返回-1 l 0; r n - 1 while l r do m (l+r)/2 if K = Am return m else if K Am r m-1 else l m+1return -1、Java算法代码：import java.util.*;public class Zheban public static void main(String args) int k = 0, i = 0, m = 0; int a = 15,25,36,98,108,250,360,782; int s = a.length-1; System.out.println(请输入一个需要查找的数字：); Scanner sc = new Scanner(System.in); try k = sc.nextInt(); while (i=s) m=(int)(i+s)/2); if (k = am) System.out.print(该数字在数组中的下标为：+m); System.exit(-1); else if (k am) s = m - 1; else i=m+1; System.out.println(-1); catch(Exception