資源描述：
《排序算法講義》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、Jsoi2004-2005第一輪函授B班第4講講義第一節(jié)排序及其基本概念一、基本概念1．什么是排序排序是數(shù)據(jù)處理中經(jīng)常使用的一種重要運(yùn)算。設(shè)文件由n個(gè)記錄{R1，R2，……，Rn}組成，n個(gè)記錄對應(yīng)的關(guān)鍵字集合為{K1，K2，……，Kn}。所謂排序就是將這n個(gè)記錄按關(guān)鍵字大小遞增或遞減重新排列。2．穩(wěn)定性當(dāng)待排序記錄的關(guān)鍵字均不相同時(shí)，排序結(jié)果是惟一的，否則排序結(jié)果不唯一。如果文件中關(guān)鍵字相同的記錄經(jīng)過某種排序方法進(jìn)行排序之后，仍能保持它們在排序之前的相對次序，則稱這種排序方法是穩(wěn)定的；否則，稱這種
2、排序方法是不穩(wěn)定的。3．排序的方式由于文件大小不同使排序過程中涉及的存儲器不同，可將排序分成內(nèi)部排序和外部排序兩類。整個(gè)排序過程都在內(nèi)存進(jìn)行的排序，稱為內(nèi)部排序；反之，若排序過程中要進(jìn)行數(shù)據(jù)的內(nèi)、外存交換，則稱之為外部排序。內(nèi)排序適用于記錄個(gè)數(shù)不是很多的小文件，而外排序則適用于記錄個(gè)數(shù)太多，不能一次性放人內(nèi)存的大文件。內(nèi)排序是排序的基礎(chǔ)，本講主要介紹各種內(nèi)部排序的方法。按策略劃分內(nèi)部排序方法可以分為五類：插入排序、選擇排序、交換排序、歸并排序和分配排序。二、排序算法分析1．排序算法的基本操作幾乎所有
3、的排序都有兩個(gè)基本的操作：（1）關(guān)鍵字大小的比較。（2）改變記錄的位置。具體處理方式依賴于記錄的存儲形式，對于順序型記錄，一般移動記錄本身，而鏈?zhǔn)酱鎯Φ挠涗泟t通過改變指向記錄的指針實(shí)現(xiàn)重定位。為了簡化描述，在下面的講解中，我們只考慮記錄的關(guān)鍵字，則其存儲結(jié)構(gòu)也簡化為數(shù)組或鏈表。并約定排序結(jié)果為遞增。2．排序算法性能評價(jià)排序的算法很多，不同的算法有不同的優(yōu)缺點(diǎn)，沒有哪種算法在任何情況下都是最好的。評價(jià)一種排序算法好壞的標(biāo)準(zhǔn)主要有兩條：（1）執(zhí)行時(shí)間和所需的輔助空間，即時(shí)間復(fù)雜度和空間復(fù)雜度；（2）算法
4、本身的復(fù)雜程度，比如算法是否易讀、是否易于實(shí)現(xiàn)。第二節(jié)插入排序插入排序的基本思想是：每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的記錄集中，使記錄依然有序，直到所有待排序記錄全部插入完成。一、直接插入排序1．直接插入排序的思想假設(shè)待排序數(shù)據(jù)存放在數(shù)組A[1..n]中，則A[1]可看作是一個(gè)有序序列，讓i從2開始，依次將A[i]插入到有序序列A[1..i-1]中，A[n]插入完畢則整個(gè)過程結(jié)束，A[1..n]成為有序序列。2．排序過程示例（用【】表示有序序列）13Jsoi2004-200
5、5第一輪函授B班第4講講義待排序數(shù)據(jù)：【25】548542119727315（n=10）i=2：【2554】8542119727315i=3：【82554】542119727315i=4：【8255454】2119727315i=5：【821255454】19727315i=6：【1821255454】9727315i=7：【182125545497】27315i=8：【1282125545497】7315i=9：【128212554547397】15i=10：【12815212554547397】
6、排序結(jié)束3．算法實(shí)現(xiàn)可在數(shù)組中增加元素A[0]作為關(guān)鍵值存儲器和循環(huán)控制開關(guān)。第i趟排序，即A[i]的插入過程為：①保存A[i]→A[0]②③如果A[j]<=A[0]（即待排序的A[i]），則A[0]→A[j+1]，完成插入；否則，將A[j]后移一個(gè)位置：A[j]→A[j+1]；；繼續(xù)執(zhí)行③對于上面的數(shù)據(jù)實(shí)例，i從2依次變化到10的過程中，j值分別為{1，0，3，1，0，6，1，7，3}4．程序代碼procedureinsertsort(n:integer);vari,j:integer;begin
7、fori:=2tondobegina[0]:=a[i];j:=i-1;whilea[j]>a[0]do{決定運(yùn)算次數(shù)和移動次數(shù)}begina[j+1]:=a[j];j:=j-1;end;a[j+1]:=a[0];end;end;5．算法分析（1）穩(wěn)定性：穩(wěn)定（2）時(shí)間復(fù)雜度：①原始數(shù)據(jù)正序，總比較次數(shù)：n-113Jsoi2004-2005第一輪函授B班第4講講義②原始數(shù)據(jù)逆序，總比較次數(shù)：③原始數(shù)據(jù)無序，第i趟平均比較次數(shù)=，總次數(shù)為：④可見，原始數(shù)據(jù)越趨向正序，比較次數(shù)和移動次數(shù)越少。（3）空間復(fù)
8、雜度：僅需一個(gè)單元A[O]二、希爾排序1．基本思想：任取一個(gè)小于n的整數(shù)S1作為增量，把所有元素分成S1個(gè)組。所有間距為S1的元素放在同一個(gè)組中。第一組：{A[1]，A[S1+1]，A[2*S1+1]，……}第二組：{A[2]，A[S1+2]，A[2*S1+2]，……}第三組：{A[3]，A[S1+3]，A[2*S1+3]，……}……第s1組：{A[S1]，A[2*S1]，A[3*S1]，……}先在各組內(nèi)進(jìn)行直接插人排序；然后，取第二個(gè)增量S2（
