① 恳请高手给小弟出一份java软件工程师的面试题
java软件工程师面试题集
EJB方面
1、EJB2.0有哪些内容?分别用在什么场合? EJB2.0和EJB1.1的区别?
答：规范内容包括Bean提供者，应用程序装配者，EJB容器，EJB配置工具，EJB服务提供者，系统管理员。这里面，EJB容器是EJB之所以能够运行的核心。EJB容器管理着EJB的创建，撤消，激活，去活，与数据库的连接等等重要的核心工作。JSP,Servlet,EJB,JNDI,JDBC,JMS.....
2、EJB与JAVA BEAN的区别？
答:Java Bean 是可复用的组件，对Java Bean并没有严格的规范，理论上讲，任何一个Java类都可以是一个Bean。但通常情况下，由于Java Bean是被容器所创建（如Tomcat)的，所以Java Bean应具有一个无参的构造器，另外，通常Java Bean还要实现Serializable接口用于实现Bean的持久性。Java Bean实际上相当于微软COM模型中的本地进程内COM组件，它是不能被跨进程访问的。Enterprise Java Bean 相当于DCOM，即分布式组件。它是基于Java的远程方法调用（RMI）技术的，所以EJB可以被远程访问（跨进程、跨计算机）。但EJB必须被布署在诸如Webspere、WebLogic这样的容器中，EJB客户从不直接访问真正的EJB组件，而是通过其容器访问。EJB容器是EJB组件的代理，EJB组件由容器所创建和管理。客户通过容器来访问真正的EJB组件。
3、EJB的基本架构
答:一个EJB包括三个部分:
Remote Interface 接口的代码
package Beans;
import javax.ejb.EJBObject;
import java.rmi.RemoteException;
public interface Add extends EJBObject
{
//some method declare
}
Home Interface 接口的代码
package Beans;
import java.rmi.RemoteException;
import jaax.ejb.CreateException;
import javax.ejb.EJBHome;
public interface AddHome extends EJBHome
{
//some method declare
}
EJB类的代码
package Beans;
import java.rmi.RemoteException;
import javax.ejb.SessionBean;
import javx.ejb.SessionContext;
public class AddBean Implements SessionBean
{
//some method declare
}
J2EE,MVC方面
1、MVC的各个部分都有那些技术来实现?如何实现?
答:MVC是Model－View－Controller的简写。"Model" 代表的是应用的业务逻辑（通过JavaBean，EJB组件实现）， "View" 是应用的表示面（由JSP页面产生），"Controller" 是提供应用的处理过程控制（一般是一个Servlet），通过这种设计模型把应用逻辑，处理过程和显示逻辑分成不同的组件实现。这些组件可以进行交互和重用。
2、应用服务器与WEB SERVER的区别？
希望大家补上，谢谢
3、J2EE是什么？
答:Je22是Sun公司提出的多层(multi-diered),分布式(distributed),基于组件(component-base)的企业级应用模型(enterpriese application model).在这样的一个应用系统中，可按照功能划分为不同的组件，这些组件又可在不同计算机上，并且处于相应的层次(tier)中。所属层次包括客户层(clietn tier)组件,web层和组件,Business层和组件,企业信息系统(EIS)层。
4、WEB SERVICE名词解释。JSWDL开发包的介绍。JAXP、JAXM的解释。SOAP、UDDI,WSDL解释。
答：Web Service描述语言WSDL
SOAP即简单对象访问协议(Simple Object Access Protocol)，它是用于交换XML编码信息的轻量级协议。
UDDI 的目的是为电子商务建立标准；UDDI是一套基于Web的、分布式的、为Web Service提供的、信息注册中心的实现标准规范，同时也包含一组使企业能将自身提供的Web Service注册，以使别的企业能够发现的访问协议的实现标准。
5、BS与CS的联系与区别。
希望大家补上，谢谢
6、STRUTS的应用(如STRUTS架构)
答：Struts是采用Java Servlet/JavaServer Pages技术，开发Web应用程序的开放源码的framework。 采用Struts能开发出基于MVC(Model-View-Controller)设计模式的应用构架。 Struts有如下的主要功能：
一.包含一个controller servlet，能将用户的请求发送到相应的Action对象。
二.JSP自由tag库，并且在controller servlet中提供关联支持，帮助开发员创建交互式表单应用。
三.提供了一系列实用对象：XML处理、通过Java reflection APIs自动处理JavaBeans属性、国际化的提示和消息。
设计模式方面
1、开发中都用到了那些设计模式?用在什么场合?
答：每个模式都描述了一个在我们的环境中不断出现的问题，然后描述了该问题的解决方案的核心。通过这种方式，你可以无数次地使用那些已有的解决方案，无需在重复相同的工作。主要用到了MVC的设计模式。用来开发JSP/Servlet或者J2EE的相关应用。简单工厂模式等。
2、UML方面
答：标准建模语言UML。用例图,静态图(包括类图、对象图和包图),行为图,交互图(顺序图,合作图),实现图,
JavaScript方面
1、如何校验数字型?
var re=/^d{1,8}$|.d{1,2}$/;
var str=document.form1.all(i).value;
var r=str.match(re);
if (r==null)
{
sign=-4;
break;
}
else{
document.form1.all(i).value=parseFloat(str);
}
CORBA方面
1、CORBA是什么?用途是什么?
答：CORBA 标准是公共对象请求代理结构(Common Object Request Broker Architecture)，由对象管理组织 (Object Management Group，缩写为 OMG)标准化。它的组成是接口定义语言(IDL), 语言绑定(binding:也译为联编)和允许应用程序间互操作的协议。 其目的为：
用不同的程序设计语言书写
在不同的进程中运行
为不同的操作系统开发
LINUX方面
1、LINUX下线程，GDI类的解释。
答：LINUX实现的就是基于核心轻量级进程的"一对一"线程模型，一个线程实体对应一个核心轻量级进程，而线程之间的管理在核外函数库中实现。
GDI类为图像设备编程接口类库。
1、面向对象的三个基本特征
2、方法重载和方法重写的概念和区别
3、接口和内部类、抽象类的特性
4、文件读写的基本类
**5、串行化的注意事项以及如何实现串行化
6、线程的基本概念、线程的基本状态以及状态之间的关系
7、线程的同步、如何实现线程的同步
8、几种常用的数据结构及内部实现原理。
9、Socket通信(TCP、UDP区别及Java实现方式)
**10、Java的事件委托机制和垃圾回收机制
11、JDBC调用数据库的基本步骤
**12、解析XML文件的几种方式和区别
13、Java四种基本权限的定义
14、Java的国际化
二、JSP
1、至少要能说出7个隐含对象以及他们的区别
** 2、forward 和redirect的区别
3、JSP的常用指令
三、servlet
1、什么情况下调用doGet()和doPost()？
2、servlet的init()方法和service()方法的区别
3、servlet的生命周期
4、如何现实servlet的单线程模式
5、servlet的配置
6、四种会话跟踪技术
四、EJB
**1、EJB容器提供的服务
主要提供声明周期管理、代码产生、持续性管理、安全、事务管理、锁和并发行管理等服务。
2、EJB的角色和三个对象
EJB角色主要包括Bean开发者 应用组装者 部署者 系统管理员 EJB容器提供者 EJB服务器提供者
三个对象是Remote（Local）接口、Home（LocalHome）接口，Bean类
2、EJB的几种类型
会话（Session）Bean ，实体（Entity）Bean 消息驱动的（Message Driven）Bean
会话Bean又可分为有状态（Stateful）和无状态（Stateless）两种
实体Bean可分为Bean管理的持续性（BMP）和容器管理的持续性（CMP）两种
3、bean 实例的生命周期
对于Stateless Session Bean、Entity Bean、Message Driven Bean一般存在缓冲池管理，而对于Entity Bean和Statefull Session Bean存在Cache管理，通常包含创建实例，设置上下文、创建EJB Object（create）、业务方法调用、remove等过程，对于存在缓冲池管理的Bean，在create之后实例并不从内存清除，而是采用缓冲池调度机制不断重用实例，而对于存在Cache管理的Bean则通过激活和去激活机制保持Bean的状态并限制内存中实例数量。
4、激活机制
以Statefull Session Bean 为例：其Cache大小决定了内存中可以同时存在的Bean实例的数量，根据MRU或NRU算法，实例在激活和去激活状态之间迁移，激活机制是当客户端调用某个EJB实例业务方法时，如果对应EJB Object发现自己没有绑定对应的Bean实例则从其去激活Bean存储中（通过序列化机制存储实例）回复（激活）此实例。状态变迁前会调用对应的ejbActive和ejbPassivate方法。
5、remote接口和home接口主要作用
remote接口定义了业务方法，用于EJB客户端调用业务方法
home接口是EJB工厂用于创建和移除查找EJB实例
6、客服端调用EJB对象的几个基本步骤
一、 设置JNDI服务工厂以及JNDI服务地址系统属性
二、 查找Home接口
三、 从Home接口调用Create方法创建Remote接口
四、 通过Remote接口调用其业务方法
五、数据库
1、存储过程的编写
2、基本的SQL语句
六、weblogic
1、 如何给weblogic指定大小的内存?
在启动Weblogic的脚本中（位于所在Domian对应服务器目录下的startServerName），增加set MEM_ARGS=-Xms32m -Xmx200m，可以调整最小内存为32M，最大200M
2、 如何设定的weblogic的热启动模式(开发模式)与产品发布模式?
可以在管理控制台中修改对应服务器的启动模式为开发或产品模式之一。或者修改服务的启动文件或者commenv文件，增加set PRODUCTION_MODE=true。
3、 如何启动时不需输入用户名与密码?
修改服务启动文件，增加 WLS_USER和WLS_PW项。也可以在boot.properties文件中增加加密过的用户名和密码.
4、 在weblogic管理制台中对一个应用域(或者说是一个网站,Domain)进行jms及ejb或连接池等相关信息进行配置后,实际保存在什么文件中?
保存在此Domain的config.xml文件中，它是服务器的核心配置文件。
5、 说说weblogic中一个Domain的缺省目录结构?比如要将一个简单的helloWorld.jsp放入何目录下,然的在浏览器上就可打入http://主机:端口号//helloword.jsp就可以看到运行结果了? 又比如这其中用到了一个自己写的javaBean该如何办?
Domain目录\服务器目录\applications，将应用目录放在此目录下将可以作为应用访问，如果是Web应用，应用目录需要满足Web应用目录要求，jsp文件可以直接放在应用目录中，Javabean需要放在应用目录的WEB-INF目录的classes目录中，设置服务器的缺省应用将可以实现在浏览器上无需输入应用名。
6、 如何查看在weblogic中已经发布的EJB?
可以使用管理控制台，在它的Deployment中可以查看所有已发布的EJB
7、 如何在weblogic中进行ssl配置与客户端的认证配置或说说j2ee(标准)进行ssl的配置
缺省安装中使用DemoIdentity.jks和DemoTrust.jks KeyStore实现SSL，需要配置服务器使用Enable SSL，配置其端口，在产品模式下需要从CA获取私有密钥和数字证书，创建identity和trust keystore，装载获得的密钥和数字证书。可以配置此SSL连接是单向还是双向的。
8、在weblogic中发布ejb需涉及到哪些配置文件
不同类型的EJB涉及的配置文件不同，都涉及到的配置文件包括ejb-jar.xml,weblogic-ejb-jar.xmlCMP实体Bean一般还需要weblogic-cmp-rdbms-jar.xml
9、EJB需直接实现它的业务接口或Home接口吗,请简述理由.
远程接口和Home接口不需要直接实现，他们的实现代码是由服务器产生的，程序运行中对应实现类会作为对应接口类型的实例被使用。
10、说说在weblogic中开发消息Bean时的persistent与non-persisten的差别
persistent方式的MDB可以保证消息传递的可靠性,也就是如果EJB容器出现问题而JMS服务器依然会将消息在此MDB可用的时候发送过来，而non－persistent方式的消息将被丢弃。
11、说说你所熟悉或听说过的j2ee中的几种常用模式?及对设计模式的一些看法
Session Facade Pattern：使用SessionBean访问EntityBean
Message Facade Pattern：实现异步调用
EJB Command Pattern：使用Command JavaBeans取代SessionBean，实现轻量级访问
Data Transfer Object Factory：通过DTO Factory简化EntityBean数据提供特性
Generic Attribute Access：通过AttibuteAccess接口简化EntityBean数据提供特性
Business Interface：通过远程（本地）接口和Bean类实现相同接口规范业务逻辑一致性
EJB架构的设计好坏将直接影响系统的性能、可扩展性、可维护性、组件可重用性及开发效率。项目越复杂，项目队伍越庞大则越能体现良好设计的重要性
from java-cn
② java面试/笔试题
1.JSP、Servlet、JavaBean技术的出现给我们构建强大的企业应用系统提供了可能。但用这些技术构建的系统非常的繁乱，所以在此之上，我们需要一个规则、一个把这些技术组织起来的规则，这就是框架，Struts便应运而生。
经过长达五年的发展，Struts已经逐渐成长为一个稳定、成熟的框架，并且占有了MVC框架中最大的市场份额。但是Struts某些技术特性上已经落后于新兴的MVC框架。面对Spring MVC、Webwork2 这些设计更精密，扩展性更强的框架，Struts受到了前所未有的挑战。但站在产品开发的角度而言，Struts仍然是最稳妥的选择。
Struts2.0为其它框架提供了更好的集成。
使得与Spring的集成非常的容易。
2.Struts的工作流程:
在web应用启动时就会加载初始化ActionServlet,ActionServlet从
struts-config.xml文件中读取配置信息,把它们存放到各种配置对象
当ActionServlet接收到一个客户请求时,将执行如下流程.
-(1)检索和用户请求匹配的ActionMapping实例,如果不存在,就返回请求路径无效信息;
-(2)如果ActionForm实例不存在,就创建一个ActionForm对象,把客户提交的表单数据保存到ActionForm对象中;
-(3)根据配置信息决定是否需要表单验证.如果需要验证,就调用ActionForm的validate()方法;
-(4)如果ActionForm的validate()方法返回null或返回一个不包含ActionMessage的ActuibErrors对象,就表示表单验证成功;
-(5)ActionServlet根据ActionMapping所包含的映射信息决定将请求转发给哪个Action,如果相应的Action实例不存在,就先创建这个实例,然后调用Action的execute()方法;
-(6)Action的execute()方法返回一个ActionForward对象,ActionServlet在把客户请求转发给ActionForward对象指向的JSP组件;
-(7)ActionForward对象指向JSP组件生成动态网页,返回给客户;
3.在struts配置文件中配置具体的错误提示，再在FormBean中的validate()方法具体调用。
4.(1) 对JDBC访问数据库的代码做了封装，大大简化了数据访问层繁琐的重复性代码。
(2) Hibernate是一个基于JDBC的主流持久化框架，是一个优秀的ORM实现。他很大程度的简化DAO层的编码工作
(3)hibernate使用Java反射机制，而不是字节码增强程序来实现透明性。
(4)hibernate的性能非常好，因为它是个轻量级框架。映射的灵活性很出色。它支持各种关系数据库，从一对一到多对多的各种复杂关系。
5.原理：
(1).读取并解析配置文件
(2).读取并解析映射信息，创建SessionFactory
(3).打开Sesssion
(4).创建事务Transation
(5).持久化操作
(6).提交事务
(7).关闭Session
(8).关闭SesstionFactory
6.
Hibernate的最大的好处就是简化数据库的操作，允许你的代码以对象模式来访问数据库内容，
比如通常我们找一个User的资料需要select出所需要的资料，而通过hibnate我们可以把这个User的资料作为一个对象来看待
，通过User.getName()或者User.getId()等操作来获得，这样就完全统一了上层JAVA或者C#等OO语言中对于数据库的非OO操作的不和谐了.
另外对于复杂的表和表之间的关联我们也不用去使用复杂的Select等SQL来操作,而使用对象可以方便获得,
比如多对多关系某用户属于的部门的名称,虽然底层数据库使用了3个表的主键关联操作,
但是我们可以通过User.getDep().getName()来简单的获得,这个就是持久化对象的好处了
7.
(1)、spring能简化企业级开发， spring可以用简单的java bean来代替实现复杂的EJB。（大部分情况下）
(2)、spring是一个轻量级的IOC和AOP框架，可以spring的IOC实现松耦合，而作为一个AOP框架他又能分离系统服务，实现内聚开发
(3)、spring是非侵入式，基于spring的系统可以不依赖于spring的类。
良好的spring运用可以使程序代码清晰，容易维护，容易测试。
8.
Spring是个很不错的框架。内部最核心的就是IOC了，
动态注入，让一个对象的创建不用new了，可以自动的生产，这其实就是利用java里的反射
反射其实就是在运行时动态的去创建、调用对象，Spring就是在运行时，跟xml Spring的配置
文件来动态的创建对象，和调用对象里的方法的 。
Spring还有一个核心就是AOP这个就是面向切面编程，可以为某一类对象 进行监督和控制（也就是
在调用这类对象的具体方法的前后去调用你指定的 模块）从而达到对一个模块扩充的功能。这些都是通过
配置类达到的。
Spring目的：就是让对象与对象（模块与模块）之间的关系没有通过代码来关联，都是通过配置类说明
管理的（Spring根据这些配置 内部通过反射去动态的组装对象）
要记住：Spring是一个容器，凡是在容器里的对象才会有Spring所提供的这些服务和功能。
Spring里用的最经典的一个设计模式就是：模板方法模式。（这里我都不介绍了，是一个很常用的设计模式）
Spring里的配置是很多的，很难都记住，但是Spring里的精华也无非就是以上的两点，把以上两点跟理解了
也就基本上掌握了Spring.
9.
(1).spring mvc请所有的请求都提交给DispatcherServlet,它会委托应用系统的其他模块负责负责对请求进行真正的处理工作。
(2).DispatcherServlet查询一个或多个HandlerMapping,找到处理请求的Controller.
(3).DispatcherServlet请请求提交到目标Controller
(4).Controller进行业务逻辑处理后，会返回一个ModelAndView
(5).Dispathcher查询一个或多个ViewResolver视图解析器,找到ModelAndView对象指定的视图对象
(6).视图对象负责渲染返回给客户端。
③ 应届生面试Java相关岗位可能会被问到哪些技术问题
常见的Java问题
1.什么是Java虚拟机？为什么Java被称作是“平台无关的编程语言”？
Java虚拟机是一个可以执行Java字节码的虚拟机进程。Java源文件被编译成能被Java虚拟机执行的字节码文件。
Java被设计成允许应用程序可以运行在任意的平台，而不需要程序员为每一个平台单独重写或者是重新编译。Java虚拟机让这个变为可能，因为它知道底层硬件平台的指令长度和其他特性。
2.JDK和JRE的区别是什么？
Java运行时环境(JRE)是将要执行Java程序的Java虚拟机。它同时也包含了执行applet需要的浏览器插件。Java开发工具包(JDK)是完整的Java软件开发包，包含了JRE，编译器和其他的工具(比如：JavaDoc，Java调试器)，可以让开发者开发、编译、执行Java应用程序。
3.”static”关键字是什么意思？Java中是否可以覆盖(override)一个private或者是static的方法？
“static”关键字表明一个成员变量或者是成员方法可以在没有所属的类的实例变量的情况下被访问。
Java中static方法不能被覆盖，因为方法覆盖是基于运行时动态绑定的，而static方法是编译时静态绑定的。static方法跟类的任何实例都不相关，所以概念上不适用。
4.是否可以在static环境中访问非static变量？
static变量在Java中是属于类的，它在所有的实例中的值是一样的。当类被Java虚拟机载入的时候，会对static变量进行初始化。如果你的代码尝试不用实例来访问非static的变量，编译器会报错，因为这些变量还没有被创建出来，还没有跟任何实例关联上。
5.Java支持的数据类型有哪些？什么是自动拆装箱？
Java语言支持的8中基本数据类型是：
byte
short
int
long
float
double
boolean
char
自动装箱是Java编译器在基本数据类型和对应的对象包装类型之间做的一个转化。比如：把int转化成Integer，double转化成double，等等。反之就是自动拆箱。
6.Java中的方法覆盖(Overriding)和方法重载(Overloading)是什么意思？
Java中的方法重载发生在同一个类里面两个或者是多个方法的方法名相同但是参数不同的情况。与此相对，方法覆盖是说子类重新定义了父类的方法。方法覆盖必须有相同的方法名，参数列表和返回类型。覆盖者可能不会限制它所覆盖的方法的访问。
7.Java中，什么是构造函数？什么是构造函数重载？什么是复制构造函数？
当新对象被创建的时候，构造函数会被调用。每一个类都有构造函数。在程序员没有给类提供构造函数的情况下，Java编译器会为这个类创建一个默认的构造函数。
Java中构造函数重载和方法重载很相似。可以为一个类创建多个构造函数。每一个构造函数必须有它自己唯一的参数列表。
Java不支持像C++中那样的复制构造函数，这个不同点是因为如果你不自己写构造函数的情况下，Java不会创建默认的复制构造函数。
8.Java支持多继承么？
不支持，Java不支持多继承。每个类都只能继承一个类，但是可以实现多个接口。
9.接口和抽象类的区别是什么？
Java提供和支持创建抽象类和接口。它们的实现有共同点，不同点在于：
接口中所有的方法隐含的都是抽象的。而抽象类则可以同时包含抽象和非抽象的方法。
类可以实现很多个接口，但是只能继承一个抽象类
类如果要实现一个接口，它必须要实现接口声明的所有方法。但是，类可以不实现抽象类声明的所有方法，当然，在这种情况下，类也必须得声明成是抽象的。
抽象类可以在不提供接口方法实现的情况下实现接口。
Java接口中声明的变量默认都是final的。抽象类可以包含非final的变量。
Java接口中的成员函数默认是public的。抽象类的成员函数可以是private，protected或者是public。
接口是绝对抽象的，不可以被实例化。抽象类也不可以被实例化，但是，如果它包含main方法的话是可以被调用的。
也可以参考JDK8中抽象类和接口的区别
10.什么是值传递和引用传递？
对象被值传递，意味着传递了对象的一个副本。因此，就算是改变了对象副本，也不会影响源对象的值。
对象被引用传递，意味着传递的并不是实际的对象，而是对象的引用。因此，外部对引用对象所做的改变会反映到所有的对象上。
Java线程
④ java编码中用设计模式与不用设计模式有什么区别为什么那些面试官老是喜欢问设计模式
使用了设计模式之后代码看起来更结构化，在很小的项目中橘裂看不出来，但是如果是一个大项目的话，凌乱的代码会让人头痛
为什么面试官老是喜欢问设计模式：
因为写代码久了基本功都会了之后就需要更进一步的技能：写出更结构化的代码
设计模式是面试时候的一个常问的问题，面试官也是人，自己也要想面试别人的问题啊，想了也头痛圆毕闭，既然这个常问就拿来问了
说实在话，java面试问设计模式已数银经是一个好多年的老传统了，但是现在再审视一下这本成书较早的书，其实里面很多的模式已经过时，有些并不适用于java，我感觉总是问设计模式也没啥意思
所以很大的原因也是面试官懒，不想创新的去想面试的问题，直接问这种传统问题省事
⑤ java面试题 很急 谢谢
2, 归并排序(merge sort)体现了分治的思想，即将一个待排序数组分为两部分，对这两个部分进行归并排序，排序后，再对两个已经排序好的数组进行合并。这种思想可以用递归方式很容易实现。归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。
实现代码如下：
#include <stdio.h>
#include "common.h"
void merge(int data[], int p, int q, int r)
{
int i, j, k, n1, n2;
n1 = q - p + 1;
n2 = r - q;
int L[n1];
int R[n2];
for(i = 0, k = p; i < n1; i++, k++)
L[i] = data[k];
for(i = 0, k = q + 1; i < n2; i++, k++)
R[i] = data[k];
for(k = p, i = 0, j = 0; i < n1 && j < n2; k++)
{
if(L[i] > R[j])
{
data[k] = L[i];
i++;
}
else
{
data[k] = R[j];
j++;
}
}
if(i < n1)
{
for(j = i; j < n1; j++, k++)
data[k] = L[j];
}
if(j < n2)
{
for(i = j; i < n2; i++, k++)
data[k] = R[i];
}
}
void merge_sort(int data[], int p, int r)
{
if(p < r)
{
int q = (p + r) / 2;
merge_sort(data, p, q);
merge_sort(data, q + 1, r);
merge(data, p, q, r);
}
}
void test_merge_sort()
{
int data[] = {44, 12, 145, -123, -1, 0, 121};
printf("-------------------------------merge sort----------------------------\n");
out_int_array(data, 7);
merge_sort(data, 0, 6);
out_int_array(data, 7);
}
int main()
{
test_merge_sort();
return 0;
}
4.对于有n个结点的线性表（e0，e1，…，en-1），将结点中某些数据项的值按递增或递减的次序，重新排列线性表结点的过程，称为排序。排序时参照的数据项称为排序码，通常选择结点的键值作为排序码。
若线性表中排序码相等的结点经某种排序方法进行排序后，仍能保持它们在排序之前的相对次序，称这种排序方法是稳定的；否则，称这种排序方法是不稳定的。
在排序过程中，线性表的全部结点都在内存，并在内存中调整它们在线性表中的存储顺序，称为内排序。在排序过程中，线性表只有部分结点被调入内存，并借助内存调整结点在外存中的存放顺序的排序方法成为外排序。
下面通过一个表格简单介绍几种常见的内排序方法，以及比较一下它们之间的性能特点。
排序方法
简介
平均时间
最坏情况
辅助存储
是否稳定
简单排序
选择排序
反复从还未排好序的那部分线性表中选出键值最小的结点，并按从线性表中选出的顺序排列结点，重新组成线性表。直至未排序的那部分为空，则重新形成的线性表是一个有序的线性表。
O( )
O( )
O(1)
不稳定
直接插入排序
假设线性表的前面I个结点序列e0，e1，…，en-1是已排序的。对结点在这有序结点ei序列中找插入位置，并将ei插入，而使i+1个结点序列e0，e1，…，ei也变成排序的。依次对i=1，2，…，n-1分别执行这样的插入步骤，最终实现线性表的排序。
O( )
O( )
O(1)
稳定
冒泡排序
对当前还未排好序的范围内的全部结点，自上而下对相邻的两个结点依次进行比较和调整，让键值大的结点往下沉，键值小的结点往上冒。即，每当两相邻比较后发现它们的排列顺序与排序要求相反时，就将它们互换。
O( )
O( )
O(1)
稳定
希尔排序
对直接插入排序一种改进，又称“缩小增量排序”。先将整个待排序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
kn ln n
O( )
O(logn)
不稳定
快速排序
对冒泡排序的一种本质的改进。通过一趟扫视后，使待排序序列的长度能大幅度的减少。在一趟扫视后，使某个结点移到中间的正确位置，并使在它左边序列的结点的键值都比它的小，而它右边序列的结点的键值都不比它的小。称这样一次扫视为“划分”。每次划分使一个长序列变成两个新的较小子序列，对这两个小的子序列分别作同样的划分，直至新的子序列的长度为1使才不再划分。当所有子序列长度都为1时，序列已是排好序的了。
O(nlogn)
O( )
O(logn)
不稳定
堆排序
一种树形选择排序，是对直接选择排序的有效改进。一个堆是这样一棵顺序存储的二叉树，它的所有父结点（e[i]）的键值均不小于它的左子结点（e[2*i+1]）和右子结点（e[2*i+2]）的键值。初始时，若把待排序序列的n个结点看作是一棵顺序存储的二叉树，调整它们的存储顺序，使之成为一个堆，这时堆的根结点键值是最大者。然后将根结点与堆的最后一个结点交换，并对少了一个结点后的n-1结点重新作调整，使之再次成为堆。这样，在根结点得到结点序列键值次最大值。依次类推，直到只有两个结点的堆，并对它们作交换，最后得到有序的n个结点序列。
O(nlogn)
O(nlogn)
O(1)
不稳定
归并排序
将两个或两个以上的有序子表合并成一个新的有序表。对于两个有序子表合并一个有序表的两路合并排序来说，初始时，把含n个结点的待排序序列看作有n个长度都为1的有序子表所组成，将它们依次两两合并得到长度为2的若干有序子表，再对它们作两两合并……直到得到长度为n的有序表，排序即告完成。
O(nlogn)
O(nlogn)
O(n)
稳定
后面根据各种排序算法，给出了C语言的实现，大家在复习的时候可以做下参考。
u 选择排序
void ss_sort(int e[], int n)
{ int i, j, k, t;
for(i=0; i< n-1; i++) {
for(k=i, j=i+1; j<n; j++)
if(e[k]>e[j]) k=j;
if(k!=i) {
t=e[i]; e[i]=e[k]; e[k]=t;
}
}
}
u 直接插入排序
void si_sort(int e[], int n)
{ int i, j, t;
for(i=0; i< n; i++) {
for(t=e[i], j=i-1; j>=0&&t<e[j]; j--)
e[j+1]=e[j];
e[j+1]=t;
}
}
u 冒泡排序
void sb_sort(int e[], int n)
{ int j, p, h, t;
for(h=n-1; h>0; h=p) {
for(p=j=0; j<h; j++)
if(e[j]>e[j+1]) {
t=e[j]; e[j]=e[j+1]; e[j+1]=t;
p=j;
}
}
}
u 希尔排序
void shell(int e[], int n)
{ int j, k, h, y;
for(h=n/2; h>0; h=h/2)
for(j=h; j<n; j++) {
y=e[j];
for(k=j-h; k>0&&y<e[k]; k-=h)
e[k+h]=e[k];
e[k+h]=y;
}
}
u 堆排序
void sift(e, n, s)
int e[];
int n;
int s;
{ int t, k, j;
t=e[s];
k=s; j=2*k+1;
while(j<n) {
if(j<n-1&&e[j]<e[j+1])
j++;
if(t<e[j]) {
e[k]=e[j];
k=j;
j=2*k+1;
}else break;
}
e[k]=t;
}
void heapsorp (int e[], int n)
{ int i, k, t;
for(i=n/2-1; i>=0; i--)
sift(e, n, i);
for(k=n-1; k>=1; k--) {
t=e[0]; e[0]=e[k]; e[k]=t;
sift(e, k, 0);
}
}
u 快速排序
void r_quick(int e[], int low, int high)
{ int i, j, t;
if(low<high) {
i=low; j=high; t=e[low];
while(i<j) {
while (i<j&&e[j]>t) j--;
if(i<j) e[I++]=e[j];
while (i<j&&e[i]<=t) i++;
if(I<j) e[j--]=e[i];
}
e[i]=t;
r_quick(e,low,i-1);
r_quick(w,i+1,high);
}
}
另外，外排序是对大型文件的排序，待排序的记录存储在外存中，在排序过程中，内存只存储文件的一部分记录，整个排序过程需进行多次的内外存间的交换。
*** 查找
查找就是在按某种数据结构形式存储的数据集合中，找出满足指定条件的结点。
按查找的条件分类，有按结点的关键码查找、关键码以外的其他数据项查找或其他数据项的组合查找等。按查找数据在内存或外存，分内存查找和外存查找。按查找目的，查找如果只是为了确定指定条件的结点存在与否，成为静态查找；查找是为确定结点的插入位置或为了删除找到的结点，称为动态查找。
这里简单介绍几种常见的查找方法。
u 顺序存储线性表的查找
这是最常见的查找方式。结点集合按线性表组织，采用顺序存储方式，结点只含关键码，并且是整数。如果线性表无序，则采用顺序查找，即从线性表的一端开始逐一查找。而如果线性表有序，则可以使用顺序查找、二分法查找或插值查找。
u 分块查找
分块查找的过程分两步，先用二分法在索引表中查索引项，确定要查的结点在哪一块。然后，再在相应块内顺序查找。
u 链接存储线性表的查找
对于链接存储线性表的查找只能从链表的首结点开始顺序查找。同样对于无序的链表和有序的链表查找方法不同。
u 散列表的查找
散列表又称杂凑表，是一种非常实用的查找技术。它的原理是在结点的存储位置和它的关键码间建立一个确定的关系，从而让查找码直接利用这个关系确定结点的位置。其技术的关键在于解决两个问题。
I. 找一个好的散列函数