插入排序算法实验报告

算法设计与分析基础实验报告应用数学学院二零一六年六月实验一插入排序算法一、实验性质设计二、实验学时14学时三、实验目的1、掌握插入排序的方法和原理。2、掌握java语言实现该算法的一般流程。四、实验内容1、数组的输入。2、输入、输出的异常处理。3、插入排序的算法流程。4、运行结果的输出。五、实验报告Ⅰ、算法原理从左到右扫描有序的子数组，直到遇到一个大于（或小于）等于A[n-1]的元素，然后就把A[n-1]插在该元素的前面（或后面）。插入排序基于递归思想。Ⅱ、书中源代码算法InsertionSort（A[0..n-1]）//用插入排序对给定数组A[0..n-1]排序//输入：n个可排序元素构成的一个数组A[0..n-1]//输出：非降序排列的数组A[0..n-1]fori←1ton-1dov←A[i]j←i-1whilej≥0andA[j]vdoA[j+1]←A[j]j←j-1A[j+1]←vⅢ、Java算法代码：importjava.util.*;publicclassCharu{publicstaticvoidmain(String[]args){intn=5;inta[]=newint[n];ints=a.length;inti=0,j=0,v=0;System.out.println(请输入若干个数字：);Scannersc=newScanner(System.in);try{while(is){a[i]=sc.nextInt();i++;}for(i=1;is;i++){v=a[i];j=i-1;while(j=0&&a[j]v){a[j+1]=a[j];j--;}a[j+1]=v;}System.out.println(插入排序结果显示：);for(i=0;is;i++){System.out.println(a[i]);}}catch(Exceptiones){System.out.println(es);}}}Ⅳ、运行结果显示：图（1）图（2）Ⅴ、实验结论：插入排序的基本操作是键值比较A[j]v。键值比较次数显然依赖于特定的输入，在最坏的情况下，插入排序与选择排序的键值比较次数是完全一致的。在最好的情况下，在外部循环的每次迭代中，比较次数只执行一次。插入排序的平均性能比最差性能快两倍，以及遇到基本有序的数组时表现出优异的性能，使得插入排序领先与选择排序和冒泡排序。