快速排序演算法非遞歸法c語言

⑴ 北航計算機類研究生專業考試科目

你需要到人家的網站看招生簡章、招生專業目錄、參考書目錄三個文件，都在招生信息里，或者在招生就業里！網站在網路輸入學校名就有了. 或者直接某大學2008研究生招生專業目錄，參考08年的，09年的每年7月後出！對應相應編號找 ，總之你只要會電腦，就在他的網站找到招生專業目錄及參考書！一定要去他的網站
http://yzb.buaa.e.cn/
院系名稱:計算機學院
專業名稱:計算機科學與技術
專業擬招收人數：220人
研究方向名稱:計算機系統結構 計算機應用技術 計算機軟體與理論
專業備注:基本學習年限為2.5年

考試科目單元 考試科目代碼 考試科目名稱
第一門考試科目 101 政治
第二門考試科目 201 英語
第三門考試科目 301 數學一
第四門考試科目 961 計算機專業綜合
其中數學英語政治全國都一樣，是統考！到考研書店問問就知道了！
專業課參考書：961 計算機專業綜合
《數據結構教程》（第二版，第三次印刷〕
北航出版社
唐發根著

《計算機組成原理》
高等教育出版社
唐朔飛編著

《操作系統實用教程》
清華大學出版社
任愛華主編

《離散數學》（數理邏輯部分〕
高等教育出版社
尹寶林等編

大綱：961計算機專業綜合考試大綱（2008版）

一、考試組成
961計算機專業綜合共包括四門課程的內容：計算機組成原理、數據結構、操作系統、數理邏輯，分別佔40分、40分、40分、30分。

二、計算機組成原理部分的考試大綱
(一) 參考書
《計算機組成原理》，高等教育出版社，唐朔飛編著
(二) 復習內容
1．存儲系統
（1）主存儲器：存儲單元電路及其工作原理、存儲晶元結構及其工作原理、DRAM的刷新原理和刷新方式、存儲器的擴展方法。
（2）高速緩沖存儲器：Cache的基本結構和工作原理、Cache的地址映射方式、Cache的替換策略。
（3）輔助存儲器：磁碟存儲器的結構、訪問特徵和性能參數計算。
2．指令系統
（1）指令格式：機器指令的一般格式以及指令字中各欄位的作用和特點。
（2）定址方式：常見定址方式的有效地址計算方法、定址范圍、作用和特點。
（3）指令系統的設計：指令格式設計的相關因素及基本方法、擴展操作碼技術。
3．CPU
（1）CPU的功能和結構: CPU的基本功能、內部結構、數據通路、控制信號。
（2）控制單元的功能：指令周期、多級時序系統、控制方式、指令執行過程的微操作流程分析。
（3）控制單元的設計：微程序控制器的結構和工作原理、微指令的格式和編碼方式、微程序設計。
4．輸入輸出技術
（1）匯流排：匯流排的分類、匯流排的判優（仲裁）控制方式、匯流排的通信控制方式。
（2）I/O控制方式：中斷響應與中斷處理、DMA方式的工作原理。

三、操作系統部分的考試大綱
（一）指定參考書
《操作系統實用教程（第二版）》，任愛華，清華大學出版社。
（二）復習內容
1．進程
進程、進程同步和通信、進程調度和死鎖等基本概念和相關演算法。要求清楚理解進程，線程等基本概念，熟練掌握各種基本演算法。
2．存儲管理
存儲器管理，包括重定位和虛擬存儲器等基本概念，分區、分頁、分段以及段頁式存 儲管理。要求清楚理解基本概念，熟練掌握各種分配演算法。
3．設備管理
I/O設備管理、調度、分配機制, RAID 等。要求掌握I/O管理的基本概念。
4．文件系統
文件系統，包括文件的組織方式、目錄結構、存取控制等。要求清楚理解文件系統的基本概念。

四、數據結構部分的考試大綱
（一）、指定參考書
《數據結構教程（第二版）》 唐發根編著 北京航空航天大學出版社，（建議選用第3次印刷的書）
（二）、復習內容
1．線性表
（1）線性關系，線性表的定義，線性表的基本操作；
（2）線性表的順序存儲結構與鏈式存儲結構(單鏈表、循環鏈表和雙向鏈表)的構造原理；
（3）在以上兩種存儲結構的基礎上對線性表實施的基本操作對應的演算法設計。
2．堆棧與隊列
（1）堆棧與隊列的基本概念，基本操作；
（2）堆棧與隊列的順序存儲結構與鏈式存儲結構的構造原理；
（3）在以上兩種儲結構的基礎上對堆棧與隊列實施插入與刪除等基本操作的演算法設計。
3．二叉樹
（1）二叉樹的基本概念與基本名詞術語；
（2）完全二叉樹與滿二叉樹，二叉樹的基本性質；
（3）二叉樹的順序存儲結構與二叉鏈表存儲結構的基本構造原理，二叉樹的前序遍歷、中序遍歷、後序遍歷以及對應演算法的設計(非遞歸演算法)；
（4）二叉排序樹的基本概念，二叉排序樹的建立(插入)和查找。
4．圖
（1）圖的定義，基本名詞術語；
（2）圖的鄰接矩陣存儲方法、鄰接表存儲方法的基本構造原理；
（3）圖的深度優先遍歷與廣度優先遍歷；
（4）最小生成樹與最短路徑的基本概念和構造過程。
5．文件及查找
（1）順序查找法與折半查找法，折半查找法對應的「判定樹」的構造；
（2）B-樹的基本概念，B-樹的插入與查找；
（3）散列(Hash)表的構造、散列函數、散列沖突以及處理散列沖突的方法。
6．內排序
（1）插入排序法(含折半插入排序法)、選擇排序法、泡排序法、快速排序法、(大頂)堆積排序法；
（2）各種內排序方法排序的基本原理和特點。

五、數理邏輯部分的考試大綱
（一）參考書
《離散數學》（第一篇 數理邏輯），高等教育出版社，尹寶林等編著
（二）復習內容
1. 命題邏輯
命題邏輯的基本概念及方法：聯結詞、賦值、等值演算、對偶定理、聯結詞的完全集、範式、邏輯推論。
2. 謂詞邏輯
謂詞邏輯的基本概念及方法：謂詞和量詞、項和公式、解釋和賦值、永真式、等值演算、邏輯推論。
3. 公理系統
公理系統：命題邏輯及謂詞邏輯的公理系統、可靠性和完全性。
4. 歸結法原理
歸結法原理：前束範式、斯科倫範式、命題邏輯及謂詞邏輯的歸結法。

還一個：
院系名稱:軟體學院
專業名稱:軟體工程
專業擬招收人數：80人
研究方向名稱:集成電路設計 日文應用軟體開發 嵌入式軟體
專業備注:基本學習年限2.5年,培養費共4萬元人民幣,本專業只招收"自籌經費"和"委託培養"兩種類別

第一門考試科目 101 政治
第二門考試科目 201 英語
或 203 日語
第三門考試科目 301 數學一
第四門考試科目 991 數據結構與C語言程序設計
專業課參考書：991 數據結構與C語言程序設計
《數據結構教程第二版》
北京航空航天大學出版社
唐發根著

《C程序設計》
清華大學出版社
譚浩強著

大綱：991數據結構與C語言程序設計考試大綱(2008版)

一、考試組成
數據結構與C語言程序設計包括「數據結構」與「C語言程序設計」兩門課程的內容，各佔75分，總分150分。

二、數據結構部分的考試大綱
（一）指定參考書
《數據結構教程（第二版）》 唐發根編著， 北京航空航天大學出版社
（建議選擇2006年6月第3次印刷的書）
（二）復習內容及基本要求
1、概述
（1）數據的邏輯結構與存儲結構的基本概念；
（2）演算法的定義、基本性質以及演算法分析的基本概念，包括採用大形式表示時間或空間復雜度。
2、線性表
（1）線性關系、線性表的定義，線性表的基本操作；
（2）線性表的順序存儲結構與鏈式存儲結構(包括單鏈表、循環鏈表和雙向鏈表)的構造原理；
(3)在以上兩種存儲結構的基礎上對線性表實施的基本操作，包括順序表的插入和刪除、鏈表的建立、插入和刪除、檢索等操作對應的演算法設計(含遞歸演算法的設計)。
3、堆棧與隊列
(1)堆棧與隊列(含循環隊列)的基本概念、基本操作；
(2)堆棧與隊列的順序存儲結構與鏈式存儲結構的構造原理；
(3)在不同存儲結構的基礎上對堆棧與隊列實施插入與刪除等基本操作。
4、樹與二叉樹
(1)樹與二叉樹的基本概念，基本特徵、名詞術語；
(2)完全二叉樹、滿二叉樹的概念、二叉樹的基本性質；
(3)二叉樹的順序存儲結構與二叉鏈表存儲結構的構造原理、二叉樹的前序遍歷、中序遍歷、後序遍歷和按層次遍歷演算法(重點為非遞歸演算法)以及利用遍歷解決有關二叉樹的其它操作；
(4)線索二叉樹的基本概念以及構造原理；
(5)二叉排序樹的基本概念、建立(插入)和查找，在二叉排序樹中查找結點的平均查找長度ASL。
5、圖
(1)圖的基本概念、名詞術語；
(2)鄰接矩陣存儲方法和鄰接表存儲方法的基本構造原理與特點；
(3)圖的深度優先搜索和廣度優先搜索的過程，圖的遍歷的基本作用；
(4)最小生成樹及最短路徑的特點、求解過程，拓撲排序及其目的。
6、文件及查找
(1)順序查找法、折半查找法以及查找過程對應的「判定樹」的構造；
(2)索引文件的基本概念；
(3)B-樹與B+樹的構造以及構造上異同，B-樹的插入和查找；
(4)散列文件的特點，散列函數和散列沖突的概念，處理散列沖突的方法以及散列文件的查找。
7、內排序
插入排序、選擇排序、泡排序、快速排序、堆積排序(大頂堆積)和二路歸並排序法等排序方法的排序原理、規律和特點。

三、C語言程序設計部分的考試大綱
（一）指定參考書
《C程序設計》 譚浩強編著，清華大學出版社
（二）復習內容及基本要求
1、C語言基本知識
（1）C語言的特點以及C語言程序的組成；
（2）數據類型，包括整型、實型、字元型等常量與變數和變數的賦值；用typedef定義類型；
（3）各種類型數據之間的混合運算；
（4）各類運算符的運算規則和優先順序；條件運算符；
（5）算術表達式、關系表達式和邏輯表達式，逗號運算符和逗號表達式，表達式sizeof的含義。
2、語句
（1）賦值語句(含條件賦值語句)、條件語句(含if、if-else、switch)、循環語句(含while、do-while、for語句，包括循環嵌套和break語句)；
（2）輸入/輸出語句，包括整型、實型、字元型(含字元串)等類型數據的格式輸入函數scanf和格式輸出函數printf。
3、數組
（1）一維數組與二維數組的定義，數組元素的引用，數組的初始化；
（2）字元數組的定義，字元數組的初始化，字元數組的引用，字元數組的輸入與輸出，字元串和字元串處理函數。
4、函數
（1）函數的定義，函數參數(形參和實參)與函數的返回值；
（2）函數的調用，包括函數的嵌套調用和遞歸函數的遞歸調用；
（3）命令行參數的概念（帶參數的主函數）。
5、宏定義
（1）帶參數的宏定義；
（2）包含文件的處理。
6、指針
（1）指針的概念，變數的指針與指向變數的指針變數，包括定義、引用以及指針變數作為函數參數；
（2）數組的指針，包括指向數組的指針變數的定義與賦值、通過指針引用數組元素、數組名作為函數參數；
（3）字元串的指針與指向字元串的指針變數。
7、結構體
（1）結構體的基本概念和特點，結構體的初始化與引用；
（2）結構體數組。
8、文件
（1）文本文件的基本概念，文本文件的類型指針FILE以及文本文件的使用方式；
（2）文本文件的打開(fopen函數)、文本文件的關閉(fclose函數)；
（3）文本文件的狀態，包括feof函數和ferror函數；
（4）文本文件的讀寫，包括fputc函數和fgetc函數、fgets函數和fputs函數等；
（5）文本文件的輸入函數fscanf和輸出函數fprintf。

復式：北京航空航天大學計算機學院
2008年碩士研究生復試規定與安排

北航計算機學院碩士研究生招生復試工作基本安排如下：
一、 統考生源復試安排（僅適合統考生源）
1. 復試分數線：計算機科學與技術（081200）和地圖制圖學與地理信息工程（081603）兩個專業的復試分數線均為：總分350分，政治和外語單科50分，數學和專業單科80分。另外，計算機學院2008年繼續在統考生源中招收部分軟體工程碩士（雙證），有關軟體工程碩士的分數線和復試辦法參見《北京航空航天大學計算機學院2008年軟體工程碩士復試規定與安排》。
2. 復試辦法：復試採取差額復試的辦法，復試分為C語言上機考試和綜合面試兩部分，每部分各150分，復試總成績300分，沒有筆試。每部分成績及格（90分以上（含）），方具有錄取資格。
 C語言上機考試只測試考生的C語言編程能力，直接在計算機上進行，系統環境為Microsoft Visual Studio 6.0，建議使用標准C編程。
 綜合面試內容包括英語口語、聽力、數理基礎和專業綜合素質等方面的內容。專業綜合素質方面將涉及計算機基礎與專業知識，考生在相關領域內曾經進行的開發、研究工作，考生本科的專業背景、曾獲得的各種榮譽，參加的各種科技、社會活動等。復試注重實際能力和可培養潛力。
3. 資格審查：所有參加復試的考生須按本規定附件1的要求准備好復試資格審查材料，復試報到時提交以便學院進行資格審查。
4. 復試報到：3月23日上午8:30，參加復試的考生到新主樓G849報到，遞交復試資格審查材料，進行考生復試資格審核（復試資格審核辦法見附件1），同時領取導師情況簡介和導師志願表。
5. C上機考試：3月23日下午2:00，參加復試的考生到計算機學院教學實驗中心參加C語言上機測試，測試時間2小時。
6. 地圖制圖學與地理信息工程專業綜合面試：3月24日上午8:30報考地圖制圖學與地理信息工程專業的學生統一參加導師組面試。面試結束後公布復試結果。
7. 計算機科學與技術專業綜合面試流程
 參加計算機科學與技術專業復試的考生根據導師介紹、導師招生人數等情況填報兩個導師志願，3月24日中午12:00前將志願表返回G849（過時無故不交，視為自動放棄復試）。3月24日下午6:00公布第一批面試分組名單。
 第一批面試（3月25日上午8:30）的考生是第一志願填報教授導師的考生，第一志願填報副教授導師的考生不參加第一批面試。每個導師的面試人數一般不超過招生人數的150％，排名在150％以後的考生，如第一志願服從調劑，學院將根據具體情況將考生調劑到報名人數不足150％的教授所在的面試小組參加面試。3月25日下午5:30左右公布第一批擬錄取名單和3月26日上午（第二批）面試分組名單。
 第二批面試3月26日上午8:30進行，第一志願填報副教授的考生按其第一志願和第一志願填報教授導師但沒被錄取的考生的第二志願一起排隊參加面試。每個導師的面試人數一般不超過招生人數的150％。排名在150％以後的考生，學院將根據具體情況進行調劑，以確保每人至少有一次面試機會。
 兩輪面試仍然沒有錄取滿的導師，學院將從剩餘考生中根據考生統考成績和考生是否服從分配等因素調劑錄取。
 3月26日下午5:30左右公布全部擬錄取名單。最終錄取與否，以收到研究生院發出的正式錄取通知書為准。
 3月26日下午5:30左右，所有被擬錄取的考生到學院辦公室領取政審表，錄取類別為自籌的考生領取並簽署自籌協議，錄取類別為委託培養的考生領取定向委託培養協議。
8. 同等學歷加試：按同等學力身份參加復試的考生（國家承認學歷的成人應屆本科畢業生或獲得國家承認的大專畢業證書後連續工作兩年或兩年以上的）需要單獨加試《C語言程序設計》和《編譯原理》課程（《C語言程序設計》用上機考試成績代替），《編譯原理》成績不低於60分，方有資格錄取。
二、 推免、單考和強軍計劃類別生源復試安排
 推免生不再進行復試。
 單考和強軍計劃考生的復試採取等額復試的辦法，且不參加C語言上機考試。
 3月23日下午2:30，單考和強軍計劃類別參加復試的考生到院會議室（如心樓407）報到，同時領取綜合面試記錄表、政審表。
 3月24日單考和強軍計劃類別考生與志願導師聯系，取得導師認可後，參加導師所在組的綜合面試。

北京航空航天大學計算機學院
2008年3月18日

計算機學院碩士研究生招生咨詢電話：
010－82317630

附件1：
北京航空航天大學計算機學院
2008碩士研究生招生復試資格審核及材料提交辦法
參加復試的考生在報到時應提交如下材料以進行資格審核後，方可參加復試：
1. 考生參加研究生入學考試的准考證原件和一份復印件；
2. 本人有效身份證件（身份證、現役軍官證、文職幹部證）原件和一份復印件，應屆本科畢業生還需同時提交本人學生證原件和一份復印件，原件審核後當場退回考生；
3. 非應屆本科畢業生需提交：（1）學歷證書原件和一份復印件；（2）由檔案所在單位人事部門提供的在校歷年學習成績表復印件一份（原件上應有畢業學校公章），並由檔案所在單位人事部門加蓋公章。
4. 應屆本科畢業生需提交所在學校教務部門提供的加蓋公章的在校歷年學習成績表一份。
5. 英語六級或四級證書復印件。
國家承認學歷的成人應屆本科生可按同等學力資格參與復試，但必須同時符合如下條件方有資格錄取：
 加試專業成績合格（加試科目：《C語言程序設計》和《編譯原理》）；
 2008年8月底以前獲得本科畢業證書；
 在計算機相關領域核心期刊以第一作者發表一篇以上（含）論文；
 2008年8月底以前通過國家英語四級。
獲得國家承認的大專畢業證書後到2008年9月1日連續工作兩年以上（含）可按同等學力參加復試，但必須同時符合如下條件方有資格錄取：
 加試專業成績合格（加試科目：《C語言程序設計》和《編譯原理》）；
 在全日制普通高校輔修完所報專業本科的全部主幹課程且成績合格（提交加蓋學校教務處公章的成績表）；
 在計算機相關領域核心期刊以第一作者發表一篇以上（含）論文；
 2008年8月底以前通過國家英語四級。
以下材料不屬於復試資格審核必須的，但希望考生提供：
 考生自述；
 考生獲得的校級以上的獎勵證書復印件（如果有）
凡提交信息與本人實際情況不符，一經發現，立即取消復試或擬錄取資格。無論錄取與否，考生復試報到時所提交資料恕不退回。
所有提交的材料均以A4紙大小按如下順序統一左側裝訂（成績單超過A4的，裝訂後折疊成A4大小）：
1） 封面（見附件2）
2） 准考證復印件；
3） 有效身份證復印件，應屆畢業生將身份證與學生證復印在同一A4紙上；
4） 考生自述；
5） 往屆生的學歷證復印件和成績證明，應屆生成績證明；
6） 英語六級或四級證書復印件（有六級證書的不要再提供四級證書）
7） 同等學力考生應提交的其他證明材料；
8） 各類校級以上獲獎證書復印件。

北京航空航天大學計算機學院
2008年3月18日

附件2：

北京航空航天大學計算機學院
2008碩士研究生招生復試審核材料

准考證號：
考生姓名：
畢業學校：
所學專業：
初試成績（總分）：

本人鄭重聲明：
在此提交的所有材料均與實際情況一致，如有不實之處，本人願承擔由此引起的相關責任。
簽名：
時間： 年 月 日

⑵ C語言實現文件排序

常見排序演算法（冒泡，選擇，快速）的C語言實現
要實現這幾種演算法的關鍵是要熟悉演算法的思想。簡單的說，冒泡排序，就如名字說的，每經過一輪排序，將最大的數沉到最底部。選擇排序的思想是將整個數列，分為有序區和無序區。每輪排序，將無序區里的最小數移入到有序區。快速排序的思想是以一個數為中心，通常這個數是該數列第一個數，將整個數列分為兩個部分，一個部分是大於這個數的區域，一個部分是小於這個數的區域。然後再對這兩個部分的數列分別排序。如果將數列分為兩個部分是通過，一方面從後向前的搜索，另一方面從前向後的搜索來實現的。具體的參考後面的來自網路的文檔。
從這幾個簡單的排序演算法上看，有幾個特點：
冒泡排序是最簡單的，也是最穩定的演算法。
選擇排序不太穩定，但是效率上較冒泡還是有較大的提升。其實在分析的過程中就能發現，選擇排序和冒泡排序相比，中間少了很多的交換過程，和比較的次數，這個應該是時間較少的原因。選擇排序能夠滿足一般的使用。當比較的數超過以萬為單位時，選擇排序也還是要一點時間的。
快速排序據說是最快的。這個可以從思想上看的出來。，當記錄較多的時候，快速排序的比較循環次數比上面2個都要少。但是在具體的實現過程中，並不見得如此。這是因為遞歸效率的低下導致的。當然，估計在實際使用過的過程，快速排序估計都會使用非遞歸操作棧的方式來實現。那樣應該會效率高傷不少。估計我會在後期出一個快速排序的非遞歸實現來真正比較它們3個性能。在下面的程序中，可以通過調高N的數字就能看的出來冒泡排序和選擇排序性能的差異。在N較小，大概幾百的時候，是看不出來的。N較大的的時候，比如N=1000或者N=10000的時候，快速排序的遞歸實現就會卡死在那裡了，出不了結果。
以下是具體的代碼：
/*
** 常見排序演算法比較
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
#define N 10
#define Demo 1

void BubbleSort(int arr[], int n);
void SelectSort(int arr[], int n);
void QuickSort(int arr[], int n);
void PrintArray(int arr[], int n);
void GenerateArray(int arr[], int n);

int main(int argc, char *argv[])
{
int arr[N];

GenerateArray(arr, N);
#if Demo
printf("Before the bubble sort------------------------\n");
PrintArray(arr, N);
#endif
printf("Start Bubble sort----------------------\n");
clock_t start_time1=clock(); //開始計時
BubbleSort(arr, N);
clock_t end_time1=clock(); // 結束計時
printf("Running time is: %lf ms\n", (double)(end_time1-start_time1)/CLOCKS_PER_SEC*1000); //輸出運行時間
#if Demo
printf("After the bubble sort------------------------\n");
PrintArray(arr, N);
#endif
printf("-----------------------------------------------------------\n");

sleep(1000); // 單位是毫秒即千分之一秒
GenerateArray(arr, N);
#if Demo
printf("Before the selection sort------------------------\n");
PrintArray(arr, N);
#endif
printf("Start selection sort----------------------\n");
clock_t start_time2=clock(); //開始計時
SelectSort(arr, N);
clock_t end_time2=clock(); // 結束計時
printf("Running time is: %lf ms\n", (double)(end_time2-start_time2)/CLOCKS_PER_SEC*1000); //輸出運行時間
#if Demo
printf("After the selection sort------------------------\n");
PrintArray(arr, N);
#endif

printf("-----------------------------------------------------------\n");
sleep(1000); // 單位是毫秒即千分之一秒
GenerateArray(arr, N);
#if Demo
printf("Before the quick sort------------------------\n");
PrintArray(arr, N);
#endif
printf("Start quick sort----------------------\n");
clock_t start_time3=clock(); //開始計時
QuickSort(arr, N);
clock_t end_time3=clock(); // 結束計時
printf("Running time is: %lf ms\n", (double)(end_time3-start_time3)/CLOCKS_PER_SEC*1000); //輸出運行時間
#if Demo
printf("After the quick sort------------------------\n");
PrintArray(arr, N);
#endif

system("PAUSE");
return 0;
}

// 產生隨機列表
void GenerateArray(int arr[], int n)
{
int i;
srand((unsigned)time(0));

for(i = 0; i <N; i++)
{
arr[i] = rand(); // 生成隨機數 范圍在0-32767之間
}
}

// 列印列表
void PrintArray(int arr[], int n)
{
int i = 0;
for(i = 0; i < n; i++)
printf("%6d", arr[i]);
printf("\n");
}

// 經典冒泡排序
void BubbleSort(int arr[], int n)
{
int i = 0, j =0;
for(i = 0; i < n; i++)
for(j = 0; j < n - 1 - i; j++)
{
if(arr[j] > arr[j + 1])
{
arr[j] = arr[j] ^ arr[j+1];
arr[j+1] = arr[j] ^ arr[j+1];
arr[j] = arr[j] ^ arr[j+1];
}
}
}

// 快速排序的遞歸實現
void QuickSort(int arr[], int n)
{
if(n <= 1)
return;

int i =0 , j = n - 1;
int key = arr[0];
int index = 0;

while(i < j)
{
// 從後向前搜索
while(j > i && arr[j] > key)
j--;
if(j == i)
break;
else
{
//交換 a[j] a[i]
arr[j] = arr[j] ^arr[i];
arr[i] = arr[j] ^arr[i];
arr[j] = arr[j] ^arr[i];
index = j;
}

// 從前向後搜索
while(i < j && arr[i] <key)
i++;
if(i == j)
break;
else
{
// 交換 a[i] a[j]
arr[j] = arr[j] ^arr[i];
arr[i] = arr[j] ^arr[i];
arr[j] = arr[j] ^arr[i];
index = i;
}
}
QuickSort(arr, index);
QuickSort(arr + index + 1, n - 1 - index);
}

// 選擇排序
void SelectSort(int arr[], int n)
{
int i, j;
int min;

for(i = 0; i < n - 1; i++)
{
int index = 0;
min = arr[i];
for(j = i + 1; j < n; j++) //找出 i+1 - n 無序區的最小者與arr[i]交換
{
if(arr[j] < min)
{
min = arr[j];
index = j;
}
}
if(index != 0) //表明無序區有比arr[i]小的元素
{
arr[i] = arr[i]^arr[index];
arr[index] = arr[i]^arr[index];
arr[i] = arr[i]^arr[index];
}
}
}

程序里有幾點注意的地方：
一，在程序里，交換2個數，我使用了異或來處理。這個可以根據個人喜好。為了避免產生臨時變數，可以使用如下幾種方式來交換2個數：
a=a^b;
b=a^b;
a=a^b;

或者
a=a+b;
b=a-b;
a=a-b;
使用第二種也挺好的。第一種異或的方式，只適用於，2個數都為int型的，a,b可以正可以負，這個沒有關系，但是必須是int類型。
二， sleep()函數是包含在windows.h裡面的，要加入 #include <window.h>
三， 關於隨機數生成的2個函數 srand()種子發生器函數，還有rand()隨機數生成器函數，自己可以參考相關文檔。
四， Demo宏來控制是演示還是比較性能用的。當把N調整的很小，比如10的時候，可以設置Demo為1，那樣就能列印數組了，可以看到比較前後的情況。當把N調整到很大比如10000的時候，就把Demo設置為0，那樣就不列印數組，直接比較性能。

具體的演算法文檔參考下面的：
冒泡排序
基本概念
冒泡排序（BubbleSort）的基本概念是：依次比較相鄰的兩個數，將小數放在前面，大數放在後面。即在第一趟：首先比較第1個和第2個數，將小數放前，大數放後。然後比較第2個數和第3個數，將小數放前，大數放後，如此繼續，直至比較最後兩個數，將小數放前，大數放後。至此第一趟結束，將最大的數放到了最後。在第二趟：仍從第一對數開始比較（因為可能由於第2個數和第3個數的交換，使得第1個數不再小於第2個數），將小數放前，大數放後，一直比較到倒數第二個數（倒數第一的位置上已經是最大的），第二趟結束，在倒數第二的位置上得到一個新的最大數（其實在整個數列中是第二大的數）。如此下去，重復以上過程，直至最終完成排序。
由於在排序過程中總是小數往前放，大數往後放，相當於氣泡往上升，所以稱作冒泡排序。
用二重循環實現，外循環變數設為i，內循環變數設為j。外循環重復9次，內循環依次重復9，8，...，1次。每次進行比較的兩個元素都是與內循環j有關的，它們可以分別用a[j]和a[j+1]標識，i的值依次為1,2,...,9，對於每一個i, j的值依次為1,2,...10-i。
產生
在許多程序設計中，我們需要將一個數列進行排序，以方便統計，而冒泡排序一直由於其簡潔的思想方法而倍受青睞。
排序過程
設想被排序的數組R［1..N］垂直豎立，將每個數據元素看作有重量的氣泡，根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數組R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"，如此反復進行，直至最後任何兩個氣泡都是輕者在上，重者在下為止。
演算法示例
A[0] 、 A[1]、 A[2]、 A[3]、 A[4]、 A[5]、 A[6]：
49 38 65 97 76 13 27
第一趟冒泡排序過程
38 49 65 97 76 13 27
38 49 65 97 76 13 27
38 49 65 97 76 13 27
38 49 65 76 97 13 27
38 49 65 76 13 97 27
38 49 65 76 13 27 97 – 這是第一趟冒泡排序完的結果
第二趟也是重復上面的過程，只不過不需要比較最後那個數97，因為它已經是最大的
38 49 65 13 27 76 97 – 這是結果
第三趟繼續重復，但是不需要比較倒數2個數了
38 49 13 27 65 76 97
….
選擇排序
基本思想
n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：
①初始狀態：無序區為R[1..n]，有序區為空。
②第1趟排序
在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
……
③第i趟排序
第i趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R(1≤i≤n-1)。該趟排序從當前無序區中選出關鍵字最小的記錄 R[k]，將它與無序區的第1個記錄R交換，使R[1..i]和R分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
這樣，n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。
常見的選擇排序細分為簡單選擇排序、樹形選擇排序（錦標賽排序）、堆排序。上述演算法僅是簡單選擇排序的步驟。
排序過程
A[0] 、 A[1]、 A[2]、 A[3]、 A[4]、 A[5]、 A[6]：
49 38 65 97 76 13 27
第一趟排序後 13 ［38 65 97 76 49 27]
第二趟排序後 13 27 ［65 97 76 49 38]
第三趟排序後 13 27 38 [97 76 49 65]
第四趟排序後 13 27 38 49 [76 97 65]
第五趟排序後 13 27 38 49 65 [97 76]
第六趟排序後 13 27 38 49 65 76 [97]
最後排序結果 13 27 38 49 49 65 76 97
快速排序演算法
演算法過程
設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。一趟快速排序的演算法是：
1）設置兩個變數I、J，排序開始的時候：I=0，J=N-1；
2）以第一個數組元素作為關鍵數據，賦值給key，即 key=A[0]；
3）從J開始向前搜索，即由後開始向前搜索（J=J-1），找到第一個小於key的值A[J]，並與A[I]交換；
4）從I開始向後搜索，即由前開始向後搜索（I=I+1），找到第一個大於key的A[I]，與A[J]交換；
5）重復第3、4、5步，直到 I=J； (3,4步是在程序中沒找到時候j=j-1，i=i+1，直至找到為止。找到並交換的時候i， j指針位置不變。另外當i=j這過程一定正好是i+或j+完成的最後另循環結束)
例如：待排序的數組A的值分別是：（初始關鍵數據：X=49） 注意關鍵X永遠不變，永遠是和X進行比較，無論在什麼位子，最後的目的就是把X放在中間，小的放前面大的放後面。
A[0] 、 A[1]、 A[2]、 A[3]、 A[4]、 A[5]、 A[6]：
49 38 65 97 76 13 27
進行第一次交換後： 27 38 65 97 76 13 49
( 按照演算法的第三步從後面開始找)
進行第二次交換後： 27 38 49 97 76 13 65
( 按照演算法的第四步從前面開始找>X的值，65>49,兩者交換，此時：I=3 )
進行第三次交換後： 27 38 13 97 76 49 65
( 按照演算法的第五步將又一次執行演算法的第三步從後開始找
進行第四次交換後： 27 38 13 49 76 97 65
( 按照演算法的第四步從前面開始找大於X的值，97>49,兩者交換，此時：I=4,J=6 )
此時再執行第三步的時候就發現I=J，從而結束一趟快速排序，那麼經過一趟快速排序之後的結果是：27 38 13 49 76 97 65，即所以大於49的數全部在49的後面，所以小於49的數全部在49的前面。
快速排序就是遞歸調用此過程——在以49為中點分割這個數據序列，分別對前面一部分和後面一部分進行類似的快速排序，從而完成全部數據序列的快速排序，最後把此數據序列變成一個有序的序列，根據這種思想對於上述數組A的快速排序的全過程如圖6所示：
初始狀態 {49 38 65 97 76 13 27}
進行一次快速排序之後劃分為 {27 38 13} 49 {76 97 65}
分別對前後兩部分進行快速排序 {27 38 13} 經第三步和第四步交換後變成 {13 27 38} 完成排序。
{76 97 65} 經第三步和第四步交換後變成 {65 76 97} 完成排序。

⑶ 數據結構中快速排序演算法的不足以及改進

一般快速排序演算法都是以最左元素作為劃分的基準值，這樣當數據元素本身已經完全有序（不管正序或者逆序）時，每一趟劃分只能將一個元素分割出來，其效率很低：時間復雜度O(n^2)，空間復雜度為O(n)
所以改進方法就是找尋合適的基準值，保證不至於在關鍵字有序或者接近有序時發生這個情況，一般可以使用三者取中（就是待劃分序列的頭元素、尾元素、中間元素三者的中間值）、或者隨機選擇等方法，這樣即使關鍵字完全有序，也可以保證時間復雜度O(nlogn)，空間復雜度O(logn)