算法实验报告.doc

《算法实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.实验一快速排序与折半搜索1.实验描述：具体描述见课本10.4节快速排序和11.3节折半搜索问题。2.实验目的：通过快速排序问题，巩固并详细分析分治方法思想和解题步骤。3.实验设计思路：快速排序：折半查找：以处于区间中间位置记录的关键字和给定值比较，若相等，则查找成功，如不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值或区间大小小于零范文..时为止。其中缩小范围有两种实现方式，一是使用循环的方式，二是使用递归的方式。本次实验选择的是使用循环的方式实现查找。4.实验环境及工具：操作系统：

2、win7操作系统开发工具：eclipse3.4、jdk1.6开发工具：java5.实验数据结构及算法：快速排序：QuickSort类{快速排序:publicstaticvoidquickSort(ElementelementArray[],intstartIndex,intendIndex)对子数组进行分割：publicstaticintpartition(ElementelementArray[],intstarIndex,intendIndex)输出排序结果：publicstaticvoido

3、utputResult(ElementelementArray[])}折半查找：SearchElement{打印输出结果：publicstaticvoidPrintResult(intposition,intx)查询：publicstaticintSearch(int[]array,intx)//存在则返回当前位置，否则返回-1打印数组中的元素:publicstaticvoidPrintArray(int[]array)}6.实验结果截图：范文..7.实验总结：通过本实验，我了解掌握了快速排序、折

4、半搜索的原理和具体实现过程，其实只要理解了快速排序、折半搜索算法原理，就可较好的编程实现快速排序算法。范文..实验二计数基数排序1.实验描述：具体描述见课本10.8节计数排序及10.9节基数排序的实验。2.实验目的：通过计数排序及基数排序问题，更进一步了解排序思想和程序设计思想与技巧。3.实验设计思路：基数排序的总体思路就是将待排序数据拆分成多个关键字进行排序，也就是说，基数排序的实质是多关键字排序。多关键字排序的思路是将待排数据里德排序关键字拆分成多个排序关键字；第1个排序关键字，第2个排序关键

5、字，第3个排序关键字......然后，根据子关键字对待排序数据进行排序。多关键字排序时有两种解决方案：最高位优先法（MSD）(MostSignificantDigitfirst)最低位优先法（LSD）(LeastSignificantDigitfirst)4.实验环境及工具：操作系统：win7操作系统开发工具：eclipse3.4、jdk1.6开发工具：java5.实验数据结构及算法：classMultiKeyRadixSortTest{publicstaticvoidradixSort(int[

6、]data,intradix,intd)publicstaticvoidprint(int[]data)}实验源码：importjava.util.Arrays;publicclassMu1tiKeyRadixSortTest{publicstaticvoidmain(String[]args){int[]data=newint[]{1188,192,221,12,23};print(data);radixSort(dataj10;4);System.out.print1n("排序后数组:“);p

7、rint(data);范文..publicstaticvoidradixSort(int[]data,intradixjintd){//缓存数组int[]tmp=newint[data.1ength];//buckets用于记录待排序元素的信息//buckets数组定义了max-min个桶int[]buckets=newint[radix];for(inti=e,rate=1;i

8、的元素完全复制到tmp数组中System.arraycopy(dataj@,tmp,@,data.1ength);//计算每个待排序数据的子关键字for(intj=8;j=e;m--){(int