折半插入排序报告Word文件下载.docx
《折半插入排序报告Word文件下载.docx》由会员分享，可在线阅读，更多相关《折半插入排序报告Word文件下载.docx（12页珍藏版）》请在冰点文库上搜索。
基本思想：
设在顺序表中有一个对象序列V[0],V[1],...,V[n-1].
其中V[0],V[1],...V[i-1]是已经排好序的对象。
在
插入V[i]时，利用折半搜索法寻找V[i]的插入位置。
假设排好的顺序是从小到大
LeftMiddleRight
若待排序元素的关键字>
中间元素的关键字
Left=Middle+1Right
反之：
Right=Middle-1;
这样一直重复对比寻找，知道Right>
left时结束
找到插入位置Left后，依次移动后边的每个元素，空开插入位置，进行插入；
4.【高级语言代码】
//成员方法：
折半插入法排序
publicvoidBineryInsSort（）{
Recordtemp;
//临时存放记录
intLeft,Right,Middle;
//指向待排序列两端的下标
/*
*第一个数据已经排好，从第二个数据起
*逐个插入到已经排好的序列*/
for（inti=1;
i<
CurrentSize;
i++）{
Left=0;
Right=i-1;
temp=Vector[i];
//备份要插入的数据
//寻找插入位置Middle
while（Left<
=Right）{
//折半，插入中点
Middle=（Left+Right）/2;
if（temp.key>
Vector[Middle].key）
Right=Middle-1;
//在左半区间找
elseLeft=Middle+1;
//在右半区间找
}//结束时Left>
Right
//找到插入位置Left,后移空开插入位置
for（intk=i-1;
k>
=Left;
k--）
Vector[k+1]=Vector[k];
Vector[Left]=temp;
//插入空位
}//循环结束，所有数据读入
}
//显示线性表
publicvoiddisplay（）{
doubles=0.0;
for（inti=0;
//其余数据列
System.out.print（Vector[i].other.stu_num+"
"
）;
System.out.print（Vector[i].other.name+"
System.out.print（Vector[i].other.sex+"
System.out.print（Vector[i].other.age+"
//排序关键字
System.out.println（Vector[i].key+"
s+=Vector[i].key;
}
System.out.println（"
平均分="
+s/CurrentSize）;
（三）、程序中类的设计
“DataList”类：
1.【主要成员变量说明】
privatestaticintDefaultSize=100;
privateRecordVector[];
//线性表
privateintMaxSize,CurrentSize;
//最大长度与当前长度
2.【主要成员方法说明】
//交换两记录
publicvoidswap（inti,intj）{
}
//成员方法：
publicvoidBineryInsSort（）{
}
//显示线性表
publicvoiddisplay（）{
packagestudy_3;
importjava.io.*;
//"
待排表"
类（多行数据构成的线性表）
publicclassDataList{
//构造函数：
从文件建表
publicDataList（Stringfilename）{
MaxSize=DefaultSize;
CurrentSize=0;
Vector=newRecord[MaxSize];
//对象数组
MaxSize;
i++）
Vector[i]=newRecord（）;
//数组元素初始化
try{
//创建文件输入流
Filef=newFile（filename）;
FileInputStreamfin=newFileInputStream（f）;
//创建数据输入流，二者关联
DataInputStreamdin=newDataInputStream（fin）;
bytec=0;
bytetemp[]=newbyte[100];
intlen=0;
Strings;
len=0;
while（（c=din.readByte（））!
=13）{
//遇到回车符
temp[len]=c;
//记录数是文本，非二进制数
len++;
//读取长度加1
}
s=newString（temp,0,len）;
intrs=Integer.parseInt（s）;
//字符串转整数
din.skipBytes
（1）;
//跳过换行符（ASII码11）
while（CurrentSize<
rs）{
//输入流结束时
len=0;
while（（c=din.readByte（））!
='
\t'
）{
//读取字符
temp[len]=c;
//接收内容
len++;
}
s=newString（temp,0,len）;
//学号装入数组
Vector[CurrentSize].other.stu_num=newString（temp,0,len）;
）{//读取字符
temp[len]=c;
//接收内容
len++;
//读取长度加1
//姓名装入数组
Vector[CurrentSize].other.name=s;
//性别装入数组
Vector[CurrentSize].other.sex=s;
//读出年龄
//字符串转整数
Vector[CurrentSize].other.age=Integer.parseInt（s）;
//读出考试分数
=13）{//读取字符
din.skipBytes
（1）;
//跳过换行字符
Vector[CurrentSize].key=Double.parseDouble（s）;
CurrentSize++;
//字符串转实数
}//输入流结束
din.close（）;
//关闭数据流同时关闭文件流
}catch（IOExceptione）{
System.out.println（"
文件异常"
Recordtemp=Vector[i];
Vector[i]=Vector[j];
Vector[j]=temp;
System.out.print（Vector[i].other.stu_num+"
System.out.print（Vector[i].other.name+"
System.out.print（Vector[i].other.sex+"
System.out.print（Vector[i].other.age+"
publicstaticvoidmain（String[]args）{
//读入数据，把成绩作为排序关键字
DataListD=newDataList（"
student.txt"
D.display（）;
//显示线性表
D.BineryInsSort（）;
//折半插入法排序
}
（4）、程序的输入输出和运行结果截屏
升级会员 