① 懇請高手給小弟出一份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. 找一個好的散列函數