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