折半插入排序报告

实习报告——“折半插入排序”演示程序

（一）、程序的功能和特点

主要实现的功能：1.折半插入排序；

2.显示线性表；

（二）、程序的算法设计

“折半插入法”算法：

1.【逻辑结构与存储结构设计】

逻辑结构：线性表

存储结构:内存中连续的存储结构

2.【基本操作设计】

从文本文件读入数据，输出显示数据；

折半插入排序后在进行输出

3.

【算法设计】

基本思想：设在顺序表中有一个对象序列V[0],V[1],...,V[n-1]. 其中V[0],V[1],...V[i-1]是已经排好序的对象。在 插入V[i]时，利用折半搜索法寻找V[i]的插入位置。

假设排好的顺序是从小到大

若待排序元素的关键字>中间元素的关键字

Left=Middle+1 Right

反之：Right=Middle-1;

这样一直重复对比寻找，知道Right>left时结束

找到插入位置Left后，依次移动后边的每个元素，空开插入位置，进行插入；

4.【高级语言代码】

//成员方法：折半插入法排序

public void BineryInsSort(){

Record temp;//临时存放记录

int Left,Right,Middle;//指向待排序列两端的下标 /*

* 第一个数据已经排好，从第二个数据起

* 逐个插入到已经排好的序列*/

for(int i=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;//在左半区间找

else Left=Middle+1;//在右半区间找

}//结束时Left>Right

//找到插入位置Left,后移空开插入位置

for(int k=i-1;k>=Left;k--)

Vector[k+1]=Vector[k];

Vector[Left]=temp;//插入空位

}//循环结束，所有数据读入

}

//显示线性表

public void display(){

double s=0.0;

for(int i=0;i<CurrentSize;i++){

//其余数据列

System.out.print(Vector[i].other.stu_num+" ");

System.out.print(Vector[i]http://doc.guandang.net+" "); 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.【主要成员变量说明】

private static int DefaultSize=100;

private Record Vector[];//线性表

private int MaxSize,CurrentSize;//最大长度与当前长度

2.【主要成员方法说明】

//交换两记录

public void swap(int i,int j){

}

//成员方法：折半插入法排序

public void BineryInsSort(){

}

//成员方法：折半插入法排序

public void BineryInsSort(){

}

//显示线性表

public void display(){

}

4.【高级语言代码】

package study_3;

import java.io.*;

//"待排表"类（多行数据构成的线性表）

public class DataList {

private static int DefaultSize=100;

private Record Vector[];//线性表

private int MaxSize,CurrentSize;//最大长度与当前长度

//构造函数：从文件建表

public DataList (String filename){

MaxSize=DefaultSize;

CurrentSize=0;

Vector=new Record[MaxSize];//对象数组

for(int i=0;i<MaxSize;i++)

Vector[i]=new Record();//数组元素初始化 try{

//创建文件输入流

File f=new File(filename);

FileInputStream fin=new FileInputStream(f); //创建数据输入流，二者关联

DataInputStream din=new DataInputStream(fin); byte c=0;

byte temp[]=new byte[100];

int len=0;

String s;

len=0;

while((c=din.readByte())!=13){

//遇到回车符

temp[len]=c;//记录数是文本，非二进制数 len++;//读取长度加1

}

s=new String(temp,0,len);

int rs=Integer.parseInt(s);//字符串转整数 din.skipBytes(1);//跳过换行符（ASII码11） while(CurrentSize<rs){

//输入流结束时

len=0;

while((c=din.readByte())!='\t'){ //读取字符

temp[len]=c;//接收内容

len++;//读取长度加1

}

s=new String(temp,0,len);

//学号装入数组

Vector[CurrentSize].other.stu_num=new String(temp,0,len);

len=0;

while((c=din.readByte())!='\t'){ // 读取字符 temp[len] = c;// 接收内容

len++ ;// 读取长度加1

}

s=new String(temp,0,len);

//姓名装入数组

Vector[CurrentSize]http://doc.guandang.net= s; len=0;

while((c=din.readByte())!='\t'){ // 读取字符 temp[len] = c;// 接收内容

len++ ;// 读取长度加1

}

s=new String(temp,0,len);

//性别装入数组

Vector[CurrentSize].other.sex= s; //读出年龄

len=0;

while((c=din.readByte())!='\t'){ // 读取字符 temp[len] = c;// 接收内容

len++ ;// 读取长度加1

}

s=new String(temp,0,len); //字符串转整数

Vector[CurrentSize].other.age=Integer.parseInt(s); //读出考试分数

len=0;

while((c=din.readByte())!=13){ // 读取字符 temp[len] = c;// 接收内容

len++ ;// 读取长度加1

}

s=new String(temp,0,len);

din.skipBytes(1); //跳过换行字符

Vector[CurrentSize].key=Double.parseDouble(s); CurrentSize++; //字符串转实数

}//输入流结束

din.close();//关闭数据流同时关闭文件流 }catch(IOException e){

System.out.println("文件异常");

}

}

//交换两记录

public void swap(int i,int j){

Record temp=Vector[i];

Vector[i]=Vector[j];

Vector[j]=temp;

}

//成员方法：折半插入法排序

public void BineryInsSort(){

Record temp;//临时存放记录

int Left,Right,Middle;//指向待排序列两端的下标 /*

* 第一个数据已经排好，从第二个数据起

* 逐个插入到已经排好的序列*/

for(int i=1;i<CurrentSize;i++){

Left=0;

Right=i-1;

temp=Vector[i];//备份要插入的数据

//寻找插入位置Middle

while(Lef …… 此处隐藏：2836字，全部文档内容请下载后查看。喜欢就下载吧 ……