資源描述：
《《算法與數(shù)據(jù)結(jié)構(gòu)》第8章 排序及基本算法ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、算法與數(shù)據(jù)結(jié)構(gòu)第8章排序及基本算法排序及基本算法為了便于檢索，人們通常希望能在計(jì)算機(jī)中保存的數(shù)據(jù)是按關(guān)鍵字值大小排列的有序表。這是因?yàn)閷?duì)于有序表可以采用檢索效率較高的二分法檢索算法，其平均檢索長度為log2(n+1)-1;而對(duì)于無序表只能進(jìn)行順序檢索，其平均檢索長度為(n+1)/2。又如為了方便檢索，需要構(gòu)造二叉檢索樹、B樹和B+樹等樹表，構(gòu)造這些樹表的過程本身就是一個(gè)排序的過程。在現(xiàn)今的計(jì)算機(jī)系統(tǒng)中，有相當(dāng)大的一部分CPU時(shí)間開銷是用于對(duì)數(shù)據(jù)的排序整理上的。因此，學(xué)習(xí)和研究各種排序算法，分析并設(shè)計(jì)出高效適用的排序算法，是擺在計(jì)算機(jī)科學(xué)工作者面前的重要
2、課題之一。第8章排序及基本算法8.1排序的基本概念8.2插入排序8.3交換排序8.4選擇排序8.5歸并排序8.6基數(shù)排序8.7各種內(nèi)部排序方法的比較和選擇8.8外部排序簡(jiǎn)介8.1排序的基本概念排序是數(shù)據(jù)處理中的重要運(yùn)算，其功能是將一組數(shù)據(jù)元素（或記錄）的任意序列，經(jīng)重新排列整理成為按關(guān)鍵字值大小有序的序列。排序的實(shí)際應(yīng)用領(lǐng)域也是非常廣泛的。例如在實(shí)際問題的數(shù)據(jù)處理中常會(huì)遇到這樣的情況，需要把若干名字如人名、地名、國名、書名、校名、物名等按字母順序列表；需要把若干數(shù)值如各種考試分?jǐn)?shù)、田賽的長度、徑賽的時(shí)間等按成績(jī)次序排名；需要把若干不同屬性的記錄按照某種
3、方法排列次序……。所有這些都是排序問題，都需要把一組數(shù)據(jù)元素或記錄按照某種特定的次序排列起來。排序的基本概念（續(xù)）排序的確切定義可以描述為：設(shè)（R1，R2…Rn）是某文件的n個(gè)記錄，其相應(yīng)的關(guān)鍵字為（K1，K2…Kn）。排序（sort）是這樣一種操作，它確定文件中n個(gè)記錄的一種排列（Rj1，Rj2…Rjn），使得其相應(yīng)關(guān)鍵字滿足遞增（即不減）關(guān)系Kj1≤Kj2≤…≤Kjn或遞減（即不增）關(guān)系Kj1≥Kj2≥…≥Kjn。若關(guān)鍵字滿足遞增（即不減）關(guān)系時(shí)，稱作按關(guān)鍵字升序排序(ascendingsort)；若關(guān)鍵字滿足遞減（即不增）關(guān)系時(shí)，稱作按關(guān)鍵字降序
4、排序(descendingsort)。排序的基本概念（續(xù)）在前面定義中，關(guān)鍵字Ki(i=1，2…n)稱作排序碼（sortcode）。排序碼可以是記錄的主關(guān)鍵字，也可以是次關(guān)鍵字，或者是多個(gè)關(guān)鍵字的組合（即組合關(guān)鍵字）。當(dāng)排序碼是主關(guān)鍵字時(shí)，由于主關(guān)鍵字可以惟一標(biāo)識(shí)一個(gè)記錄，所以排序結(jié)果是惟一的。當(dāng)排序碼是次關(guān)鍵字時(shí)，同一關(guān)鍵字值可能標(biāo)識(shí)了兩個(gè)或兩個(gè)以上的記錄，所以排序結(jié)果不惟一。排序的基本概念（續(xù)）若相同關(guān)鍵字值的記錄在排序前后的相對(duì)位置不會(huì)發(fā)生改變，即若Ri與Rj的關(guān)鍵字相同（Ki=Kj）且在排序前Ri在Rj之前，排序后的Ri仍在Rj之前，則稱所用的
5、排序算法是穩(wěn)定的(stable)；否則，若排序前后相同關(guān)鍵字值的記錄其相對(duì)位置可能發(fā)生改變，即排序之后的序列中有可能出現(xiàn)Rj在Ri之前的情況，則稱所用的排序算法是不穩(wěn)定的。當(dāng)排序碼是組合關(guān)鍵字時(shí)，通常稱作多關(guān)鍵字排序，其排序結(jié)果的惟一性取決于組合關(guān)鍵字是否能惟一標(biāo)識(shí)一個(gè)記錄。排序的分類根據(jù)排序過程中待排序文件存放的位置不同，可以把排序分為內(nèi)部和外部排序兩大類。內(nèi)部排序是指待排序文件放在內(nèi)存中進(jìn)行排序的排序；內(nèi)部排序適用于記錄個(gè)數(shù)不很多的較小待排序文件的排序；外部排序是指在待排序文件很大時(shí)，內(nèi)存中不能一次容納全部記錄，還要借助于外存存放待排序文件，在排序
6、過程中需要對(duì)外存進(jìn)行訪問的排序；外部排序則適用于記錄個(gè)數(shù)太多不能一次全部放入內(nèi)存的較大待排序文件的排序。排序的分類（續(xù)）按排序中所用策略的不同：內(nèi)部排序通?？梢苑譃椴迦肱判?、選擇排序、交換排序、歸并排序和分配排序這五類，每一類中不同的排序算法都是基于同一策略的不同方法。外部排序多是采用多路歸并方法進(jìn)行排序。內(nèi)部排序文件的組織形式每種內(nèi)部排序方法均可在不同的存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)。通常待排序文件的組織形式有三種方式：以一維數(shù)組作為組織形式，排序過程是對(duì)記錄本身進(jìn)行物理重排，通過比較和判定把記錄移動(dòng)到合適的位置；以鏈表（動(dòng)態(tài)鏈表或靜態(tài)鏈表）作為組織形式，排序過程中
7、無需移動(dòng)記錄，僅需修改指針即可，通常把這類排序稱為表排序；為待排序文件組織一個(gè)輔助表，如組織一張含關(guān)鍵字和指向記錄指針的索引表，在排序過程中只需對(duì)輔助表的表目進(jìn)行物理重排，不需移動(dòng)記錄本身，在排序結(jié)束后按輔助表調(diào)整記錄位置。排序的基本概念（續(xù)）排序的方法很多，每一種方法都有自己的優(yōu)缺點(diǎn)，適用于在不同的環(huán)境下使用，很難說哪一種方法是最好的方法。由于所需的輔助空間的量一般都不大，所以排序的時(shí)間代價(jià)是衡量排序算法的最重要的因素。內(nèi)部排序的時(shí)間代價(jià)主要用關(guān)鍵字的比較次數(shù)和記錄的移動(dòng)次數(shù)來衡量；而外部排序的時(shí)間代價(jià)主要用訪問外存儲(chǔ)器的次數(shù)來衡量。排序的基本概念（
8、續(xù)）在本章主要討論內(nèi)部排序算法，以記錄數(shù)組作為待排序文件的組織形式，并假定關(guān)鍵字均為整數(shù)，按遞
