Java程序设计实验指导与习题解答 工业和信息化普通高等教育“十二五”规划教材 作者 李荣 段新娥 chap2.pptVIP

【例2-21】插入升序排序。 [初始关键字] [49] 38 65 97 76 13 27 49 ??? J=2(38) [38 49] 65 97 76 13 27 49 ??? J=3(65) [38 49 65] 97 76 13 27 49 ??? J=4(97) [38 49 65 97] 76 13 27 49 ??? J=5(76) [38 49 65 76 97] 13 27 49 ??? J=6(13) [13 38 49 65 76 97] 27 49 ??? J=7(27) [13 27 38 49 65 76 97] 49 ??? J=8(49) [13 27 38 49 49 65 76 97] 在下面的插入排序算法中，为了写程序方便我们引入一个哨兵元素L[0]，它小于L[1..n]中任一记录。所以，我们设元素的类型ElementType中有一个常量-∞，它比可能出现的任何记录都小。如果常量-∞不好事先确定，就必须在决定L[i]是否向前移动之前检查当前位置是否为1，若当前位置已经为1时，就应结束第i遍的处理。另一个办法是在第i遍处理开始时，就将L[i]放入L[0]中，这样也可以保证在适当的时候结束第i遍处理。下面的算法中将对当前位置进行判断。 代码如下： public class InsertionSortW { void doInsertSort1(int[] src) { int len=src.length; for(int i=1;ilen;i++) { int temp=src[i]; int j=i; while(src[j-1]temp) { src[j]=src[j-1]; j--; if(j=0) break; } src[j]=temp; } } public static void main(String[] args) { int array[]={49,38,65,97,76,13,27,49}; System.out.print(原数组元素为：); for(int i=0;iarray.length;i++) System.out.print(array[i]+　); System.out.println(); BubbleSort b=new BubbleSort(); b.bubble(array); //调用函数 System.out.print(插入升序排后数组元素为：); for(int i=0;iarray.length;i++) System.out.print(array[i]+ ); } } 2.6.1 排序 4．利用系统类实现排序 对于排序，Arrays类揽胜方法重载提供了多种静态的排序方法，下面是其中的几种： （1）public static void sort(int[] a) 对参数指定的整型数组进行排序。 （2）public static void sortt(float[] a) 对参数指定的浮点型数组进行排序。 （3）public static void sort(char[] a) 对参数指定的字符数组进行排序。 （4）public static void sort(int[] a,int fromInedx,int toIndex) 对参数指定的下标范围内对数组元素进行排序（其他元素不动）。fromInedx,toIndex分别指要排序的起始和终止下标。 （5）public static void sort(object[] a) 对可比较大小的对象进行排序。（例如字符串） 2.6.2 查找 查找是利用率给定的某个值，在一个数据集或数据序列中确定一个其关键字等于给定值记录或数据元素。若表中存在这样一个记录，则称查找是成功的；若表中不存在关键字等于给定值的记录，则称查找不成功。常用查找算法有顺序查找、二分查找等。 1．顺序查找 顺序查找又称线性查找。 2.6.2 查找 基本思想： 从查找表的一端开始，向另一端逐个按给定值K与关键字进行比较，若找到，查找成功;并给出记录在表中的位置；若整个表检测完，仍未找到与K值相同的关键字，则查找失败;其优点是：对表中数据的存储没有要求，数据序列可以是有序，也可以是无序；对于链表，只能进行顺序查找；顺序查找的缺点是：当n值很大时，平均查找长度较大，效率低。 2 二分查找 （一