1、第5 5章 排序與查找PART A可視化計(jì)算學(xué)習(xí)目標(biāo)如何在計(jì)算機(jī)中進(jìn)行排序?排序算法有那些分類? 如何實(shí)現(xiàn)常用的排序算法?查找與排序有何關(guān)系?查找算法有哪些分類? 如何實(shí)現(xiàn)常用的查找算法？2http:/何為排序?學(xué)習(xí)中的排序：在一些教課書中，會(huì)將涉及到的所有術(shù)語(yǔ)排成索引，作為附錄，方便讀者在需要時(shí)查找圖書館工作人員的重要工作，就是把歸還的書，插入適當(dāng)?shù)臅?、層次、位? 方便讀者查閱社會(huì)中排序：會(huì)議代表名單的排序（按姓氏筆畫）；聯(lián)大會(huì)議的發(fā)言順序（按國(guó)家名稱字母排序）3http:/計(jì)算機(jī)如何進(jìn)行排序？從”混沌”到有序：排序自身也是一種應(yīng)用,同時(shí)也為快速的查找提供必要的準(zhǔn)備在計(jì)算機(jī)科學(xué)中，排序(

2、sorting)是研究最多的問題之一基本排序算法有5類：插入排序，例如，直接插入排序，二分插入排序等；交換排序，例如，冒泡排序，快速排序等；選擇排序，例如，選擇排序，推排序等歸并排序，例如，歸并排序，多相歸并排序等分布排序，例如，桶排序，基數(shù)排序等4http:/排序術(shù)語(yǔ)和實(shí)現(xiàn)策略自然的自然的(natural)(natural)如果某種排序算法對(duì)有序的數(shù)據(jù)排序速度較快(工作量變小)，對(duì)無序的數(shù)據(jù)排序速度卻較慢(工作變量大)，這種算法被稱為自然排序算法如果數(shù)據(jù)已接近有序，就需要考慮選用自然的排序算法5http:/排序術(shù)語(yǔ)和實(shí)現(xiàn)策略穩(wěn)定的穩(wěn)定的(stable)(stable)如果能保持它認(rèn)為相等的數(shù)

3、據(jù)的前后順序，這種算法被稱為穩(wěn)定排序算法穩(wěn)定的排序算法可按主、次關(guān)鍵字對(duì)數(shù)據(jù)進(jìn)行排序，例如，按照姓氏和名字排序。在具體實(shí)現(xiàn)時(shí)，就是先按主關(guān)鍵字排序，再按次關(guān)鍵字排序6http:/排序術(shù)語(yǔ)和實(shí)現(xiàn)策略內(nèi)部排序和外部排序內(nèi)部排序和外部排序待排數(shù)據(jù)全部在內(nèi)存中的排序方法被稱為內(nèi)部排序，待排數(shù)據(jù)在磁盤、磁帶和其它外存中的排序方法被稱為外部排序本節(jié)涉及的排序算法，全部針對(duì)內(nèi)部排序進(jìn)行討論7http:/排序術(shù)語(yǔ)和實(shí)現(xiàn)策略關(guān)鍵字排序（關(guān)鍵字排序（Key sortKey sort）如果要對(duì)某班級(jí)學(xué)生的期末成績(jī)表進(jìn)行排序，表中給出了每個(gè)學(xué)生的學(xué)號(hào)、姓名、單科成績(jī)和總成績(jī)等項(xiàng)目按什么來排序？所選結(jié)果,就是關(guān)鍵字本章

4、所有案例中，只考慮關(guān)鍵字字段，而先將信息的其他內(nèi)容一概略去8http:/排序術(shù)語(yǔ)和實(shí)現(xiàn)策略數(shù)字化排序（數(shù)字化排序（digitized sortdigitized sort）在排序過程中，可以按數(shù)值大小排序，有時(shí)候需要按字符來排序，有時(shí)候需要按照時(shí)間的遲早來排序?qū)嶋H上，計(jì)算機(jī)內(nèi)的所有數(shù)據(jù)，無論屬于哪種類型數(shù)據(jù)，都可以轉(zhuǎn)換成數(shù)字（二進(jìn)制或十進(jìn)制）表達(dá)所以排序本身可以抽象為對(duì)數(shù)字進(jìn)行排序9http:/如何在如何在RAPTORRAPTOR中實(shí)現(xiàn)排序中實(shí)現(xiàn)排序排序算法測(cè)試的數(shù)據(jù)來源請(qǐng)回顧第2章提及的隨機(jī)數(shù)生成和存儲(chǔ)，以及使用文件輸入數(shù)據(jù)的方法不僅可以節(jié)省用戶與算法的交互時(shí)間而且可以適當(dāng)擴(kuò)大數(shù)據(jù)集合，驗(yàn)證

5、算法的效率10http:/直接插入排序直接插入排序與整理?yè)淇伺频倪^程非常類似第1張牌沒有必要整理以后每次從牌堆(無序區(qū))的最上面摸出1張牌并插入左手牌(有序區(qū))中正確的位置上為了確定正確的插入位置，一般從左向右將摸上來的牌與手中已有的牌逐一比較11http:/直接插入排序假設(shè)data.txt文件中存放著待排序的記錄R ，則R可以看成是一個(gè)長(zhǎng)度為n的待排數(shù)組首先從data.txt文件中保存的數(shù)組R讀入一個(gè)數(shù)據(jù)到a1，生成一個(gè)有序數(shù)組由于文件中的數(shù)組R呈無序狀態(tài)，從i=2起至i=n為止，依次將Ri插入當(dāng)前的有序數(shù)組a1.i-1中最后生成含n個(gè)記錄的有序數(shù)組12http:/插入排序main子圖13h

6、ttp:/插排look_for_position子圖14http:/插排move_to_new_position子圖15http:/桶排序桶排序的思想源于信件分揀 在現(xiàn)實(shí)應(yīng)用中，是把0，1)的數(shù)值劃分為n個(gè)大小相同的子區(qū)間，每一子區(qū)間可以看作是一個(gè)桶然后將n個(gè)記錄分配到各個(gè)桶內(nèi)由于同一桶內(nèi)的記錄其關(guān)鍵字不盡相同，所以必須采用關(guān)鍵字比較的排序方法(通常用插入排序)對(duì)每個(gè)桶進(jìn)行排序然后依次將各非空桶內(nèi)的記錄連接(收集)起來即可16http:/17http:/桶排序main子圖18http:/桶排序的實(shí)現(xiàn)說明簡(jiǎn)單的設(shè)計(jì)就是直接利用random()函數(shù)產(chǎn)生待排數(shù)據(jù)準(zhǔn)備一個(gè)10行的二維數(shù)組a,每一行就是

7、一個(gè)桶將隨機(jī)數(shù)小數(shù)后的第一位為09的數(shù)字依次放入這10個(gè)桶內(nèi)很顯然，這個(gè)算法離不開上一節(jié)介紹的插入排序使用csv格式的文件保存已排序數(shù)據(jù)，可以留給其他的應(yīng)用使用19http:/桶排insert_sort_prepare子圖 （I）20http:/桶排insert_sort_prepare子圖 （II）21http:/桶排序的輸出結(jié)果22http:/冒泡排序冒泡排序（Bubble Sort）的基本概念是：將被排序的記錄數(shù)組a1.n垂直排列，每個(gè)記錄ai看作是重量為ai所存數(shù)值的氣泡根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組a：凡掃描到違反本原則的輕氣泡，就使其向上飄浮“如此反復(fù)進(jìn)行，直到

8、最后任何兩個(gè)氣泡都是輕者在上，重者在下為止23http:/24http:/冒泡排序main子圖25http:/冒泡算法說明初始狀態(tài)： a1.n為無序區(qū)。第一次掃描：從無序區(qū)底部向上依次比較相鄰的兩個(gè)氣泡的重量，若發(fā)現(xiàn)輕者在下、重者在上，則交換二者的位置，第一次掃描完畢時(shí)，最輕的氣泡就飄浮到該區(qū)間的頂部，即關(guān)鍵字最小的記錄被放在最高位置a1上。第二次掃描：掃描a2.n。掃描完畢時(shí)，次輕的氣泡飄浮到a2的位置上。最后，經(jīng)過n-1 趟掃描可得到有序區(qū)a1.n26http:/冒泡排序bubble子圖27http:/冒泡算法如何改進(jìn)？假如待排序列已經(jīng)是基本有序的（只有兩個(gè)數(shù)字需要換位），如何能夠在n-1

9、趟之前，結(jié)束排序？提示：可以將已經(jīng)排好的數(shù)據(jù)，有意調(diào)換一對(duì)，然后使用改進(jìn)后的算法實(shí)驗(yàn)（從文件讀入待排數(shù)據(jù)）28http:/快速排序快速排序（Quick sort）是在冒泡排序基礎(chǔ)上做了適當(dāng)?shù)母倪M(jìn)快速排序是由C. A. R. Hoare在1962年提出的它采用了分治的策略，是一種劃分交換排序算法被譽(yù)為二十世紀(jì)“十大經(jīng)典算法”之一29http:/快速排序的基本思想通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)要小然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序整個(gè)排序過程可以遞歸進(jìn)行，從而使整個(gè)數(shù)據(jù)變?yōu)橛行蛐蛄?0http:/31http:/快速排序main子

10、圖32http:/快速排序QkSort子圖33http:/快速排序QkPass子圖34http:/RAPTOR中的快速排序通過實(shí)際運(yùn)行可知，這里實(shí)現(xiàn)的“快速排序”盡管可以改善排序算法的時(shí)間復(fù)雜性，但由于全局變量問題，實(shí)際上的空間復(fù)雜性很差可以考慮使用非遞歸的實(shí)現(xiàn)來完成“快速排序”35http:/歸并排序歸并排序也叫合并排序是分治法一個(gè)非常典型的應(yīng)用歸并排序法是將兩個(gè)或更多個(gè)有序表合并成一個(gè)新的有序表如果是將兩個(gè)有序表合并成一個(gè)有序表，被稱為2-路歸并36http:/37http:/歸并排序main子圖38http:/歸并排序input子圖（I）39http:/歸并排序input子圖（II）40

11、http:/歸并算法實(shí)現(xiàn)的說明待排的兩路數(shù)據(jù)存放在一個(gè)文件中，文件中的頭兩個(gè)數(shù)據(jù)，分別是兩路數(shù)據(jù)的個(gè)數(shù)（可以不等長(zhǎng)）；在得到線形表的長(zhǎng)度后，再用兩個(gè)數(shù)組a、b保存待排數(shù)據(jù)第一個(gè)排序循環(huán)過程是對(duì)兩個(gè)數(shù)組的元素逐個(gè)進(jìn)行比對(duì)，并輸出較小的數(shù)據(jù)元素；第二個(gè)循環(huán)過程是在比對(duì)輸出完成后，仍有一個(gè)線形表的數(shù)據(jù)尚未輸出完畢，所以再將有剩余元素的數(shù)組進(jìn)行輸出41http:/歸并排序歸并排序merge子圖（子圖（I）42http:/歸并排序merge子圖（II）43http:/排序算法的分析冒泡排序顯然最容易實(shí)現(xiàn)對(duì)已經(jīng)存在的無序線形表進(jìn)行排序，所以最為最常見；插入排序?qū)τ陔S機(jī)產(chǎn)生的無序數(shù)據(jù)，可以實(shí)現(xiàn)實(shí)時(shí)排序；歸并排序的前提是存在兩個(gè)以上已經(jīng)排序的線形表；桶排序則適用于可以進(jìn)行分類的數(shù)據(jù)排序；快速排序則是最能體現(xiàn)時(shí)間復(fù)雜性優(yōu)化的排序算法，但要關(guān)注其在不同的實(shí)現(xiàn)環(huán)境中，可能因空間復(fù)雜性所帶來的問題44http:/排