数据结构实验五-查找与排序的实现

实 验 报 告

课程名称 数据结构 实验名称 查找与排序的实现 系别 专业班级 指导教师11 一、实验目的

(1) (2) (3) (4)

掌握交换排序算法（冒泡排序）的基本思想； 掌握交换排序算法（冒泡排序）的实现方法； 掌握折半查找算法的基本思想； 掌握折半查找算法的实现方法；

学号 姓名 实验日期 实验成绩

二、实验内容

1. 对同一组数据分别进行冒泡排序，输出排序结果。要求： 1) 设计三种输入数据序列：正序、反序、无序

2) 修改程序：

a) 将序列采用手工输入的方式输入

b) 增加记录比较次数、移动次数的变量并输出其值，分析三种序列状态的算法时间复杂

性

2. 对给定的有序查找集合，通过折半查找与给定值k相等的元素。

3. 在冒泡算法中若设置一个变量lastExchangeIndex来标记每趟排序时经过交换的最后位置，

算法如何改进？

三、设计与编码

1.本实验用到的理论知识

2.算法设计

3.编码

package sort_search;

import java.util.Scanner; public class Sort_Search {

//冒泡排序算法

public void BubbleSort(int r[]){ int temp;

int count=0,move=0; boolean flag=true;

for(int i=1;i

for(int j=0;jr[j+1]){ temp=r[j]; r[j]=r[j+1]; r[j+1]=temp; move++; flag=true; } } }

System.out.println(\排序后的数组为：\ for(int i=0;i

System.out.println();

System.out.println(\比较次数为：\ System.out.println(\移动次数为：\ }

public static int BinarySearch(int r[],int key){ //折半查找算法

int low=0,high=r.length-1; while(low<=high){

int mid=(low+high)/2; if(r[mid]==key){ return mid; }

else if(r[mid]>key){

high=mid-1; }

else{

low=mid+1; } }

return -1; }

//测试

public static void main(String[] args) { Sort_Search ss=new Sort_Search(); int t[]=new int[13];

System.out.println(\依次输入13个整数为：\

Scanner sc=new Scanner(System.in); for(int i=0;i

System.out.println(\排序前的数组为： \ for(int i=0;i

System.out.println(); ss.BubbleSort(t); //查找

while(true){

System.out.println(\请输入要查找的数： \ int k=sc.nextInt(); if(BinarySearch(t,k)>0)

System.out.println(k+\在数组中的位置是第： \ BinarySearch(t,k)); else

System.out.println(k+\在数组中查找不到！\ } } }