《數(shù)據(jù)結(jié)構(gòu)》課件第八章

第八章內(nèi)部排序內(nèi)容提要基本概念插入排序快速排序選擇排序歸并排序基數(shù)排序排序的概述（一）排序的功能：將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。排序的穩(wěn)定性：如果在待排序的記錄序列中有多個(gè)數(shù)據(jù)元素的關(guān)鍵字值相同，經(jīng)過(guò)排序后，這些數(shù)據(jù)元素的相對(duì)次序保持不變，則稱這種排序算法是穩(wěn)定的，否則稱之為不穩(wěn)定的。原地排序：在原來(lái)占有的空間中進(jìn)行，只占有少量輔助空間。排序的分類內(nèi)部排序和外部排序：內(nèi)部排序是指在排序的整個(gè)過(guò)程中，待排序的所有數(shù)據(jù)元素全部被放置在內(nèi)存中；外部排序是指由于待排序的數(shù)據(jù)元素個(gè)數(shù)太多，而需要將一部分?jǐn)?shù)據(jù)元素放置在內(nèi)存，另一部分?jǐn)?shù)據(jù)元素放置在外設(shè)上。排序概述（三）排序過(guò)程中的基本操作比較兩個(gè)關(guān)鍵字將記錄從一個(gè)位置移到另一個(gè)位置待排序序列的存儲(chǔ)方式地址連續(xù)的存儲(chǔ)單元（類似于順序存儲(chǔ)）靜態(tài)鏈表中（排序時(shí)修改指針，不移動(dòng)位置）有地址向量的連續(xù)存儲(chǔ)單元（修改記錄地址）插入排序（一）直接插入排序（簡(jiǎn)單排序）基本操作：從數(shù)組的第二個(gè)單元開(kāi)始，依次從原始數(shù)據(jù)中取出數(shù)據(jù)，并將其插入到數(shù)組中該單元之前的已排好序的序列中合適的位置處。操作步驟：從已排好的序列尾部開(kāi)始，逐一比較，找到新記錄該插入的位置，完成第一次插入第i趟就是在含有i-1個(gè)記錄的有序子序列r[1..i-1]中插入記錄r[i]后變成含有i個(gè)記錄的有序序列為防止數(shù)組下標(biāo)出界，在r[0]處設(shè)置監(jiān)視哨整個(gè)過(guò)程進(jìn)行n-1次插入4938

384965

384965973849659776384965769713133849657697271327384965769749132738494965769765

9797767676131313132727272727494949494949簡(jiǎn)單插入排序已知線性表按照順序結(jié)構(gòu)存儲(chǔ)滿足原地排序和穩(wěn)定排序的條件，分類后關(guān)鍵字相等的若干個(gè)元素是相鄰的O(n)2voidinsertsort(sqlistr,intn){inti,j;for(i=2;i<=n;i++)/*一共進(jìn)行n-1趟排序*/{r[0]=r[i];/*r[0]用于暫時(shí)存放待插入的元素*/

j=i-1;/*j為待比較元素下標(biāo)，初始時(shí)指向待插入元素前一個(gè)單元*/

while(r[0].key<r[j].key){r[j+1]=r[j];j--;}r[j+1]=r[0];/*在j+1位置插入r[0]*/}}穩(wěn)定算法O（n）2插入排序（二）折半插入排序：簡(jiǎn)單插入的不足：當(dāng)n大時(shí)，耗時(shí)基本操作：在一個(gè)有序表中進(jìn)行查找和插入操作步驟：設(shè)立兩個(gè)指針：low、high通過(guò)比較，查找和刪除折半插入排序已知線性表按照順序結(jié)構(gòu)存儲(chǔ)該算法是不穩(wěn)定的原地排序。O(n*logn)2插入排序（三）希爾排序：優(yōu)點(diǎn)：在時(shí)間上做了改進(jìn)（分組插入法）基本思想：將待排記錄分成若干序列（定義一個(gè)增量）進(jìn)行直接排序，直到序列基本有序?！盎居行颉睍r(shí)對(duì)全體記錄進(jìn)行一次直接插入排序增量的選擇：增量應(yīng)該是沒(méi)有1之外的公因子，并且最后一個(gè)增量值必須是1不穩(wěn)定的算法49386597761327495504(49,13)(38,27)(65,49)(97,55)(76,04)第一趟結(jié)果：13274955044938659776(13,55,38,76)(27,04,65)(49,49,97)第二趟結(jié)果：13044938274955659776第三趟直接插入排序第三趟結(jié)果：04132738494955657697快速排序（一）冒泡排序基本思想：將每個(gè)記錄R[i]看作是重量為R[i].key的氣泡，根據(jù)輕氣泡不在重氣泡之下的原則，從下往上掃描數(shù)組R，逐一比較，交換順序適合n較小的情況冒泡排序法原地的穩(wěn)定的排序O(n)2最糟糕的情況是，原序列恰好是一個(gè)降序序列，則總的比較次數(shù)為n(n-1)/2，移動(dòng)次數(shù)為3n(n-1)/24938659776132749第一趟結(jié)果：3849657613274997第二趟結(jié)果：3849651327497697第三趟結(jié)果：3849132749657697第四趟結(jié)果：3813274949657697時(shí)間復(fù)雜度O（n）穩(wěn)定算法第五趟結(jié)果：1327384949657697快速排序（二）快速排序：對(duì)簡(jiǎn)單冒泡的改進(jìn)基本思想：將待排序的n個(gè)記錄中任取一個(gè)記錄（樞軸）作為標(biāo)準(zhǔn)，將所有記錄分為兩組，再重復(fù)上述方法，直到所有記錄都在適當(dāng)位置為止一趟快速排序的過(guò)程及算法不穩(wěn)定算法適用于離有序較遠(yuǎn)的情況，不適合接近有序的情況當(dāng)序列成遞增排列時(shí)，每次劃分只能將一個(gè)元素分離出去，故此時(shí)有最糟糕的效率，為 平均的復(fù)雜度為O(n*log2n)O(n)2一趟快速排序的過(guò)程：附設(shè)兩個(gè)指針low、high，設(shè)樞軸記錄為pivotkey，從high所指位置起向前搜索找到第一個(gè)小于pivotkey的記錄和樞軸交換，然后從low所指位置向后搜索，找到第一個(gè)大于pivotkey的記錄和樞軸交換，重復(fù)步驟，直至low=high為止。4938659776132749ij若j指向的元素>=p,j--；若j指向的元素<p,

數(shù)換位，i++；若i指向元素<=p,

i++，若i指向的元素>P,數(shù)換位，j--。直至i=j4938659776132749ij2738659776134949j2738659776134949ij2738499776136549iji2738139776496549ij2738134976976549ji2738134976976549ij選擇排序（一）簡(jiǎn)單選擇排序基本思想：每一趟在n-i+1個(gè)記錄中選擇關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄。是穩(wěn)定排序算法簡(jiǎn)單，易實(shí)現(xiàn)，但n不能大簡(jiǎn)單選擇排序求局部的最大元素穩(wěn)定的原地排序比較：移動(dòng)：n-1T=選擇排序（二）樹(shù)型選擇排序（錦標(biāo)賽排序）基本思想：對(duì)n個(gè)記錄的關(guān)鍵字進(jìn)行兩兩比較，然后在其中n/2個(gè)較小者之間再進(jìn)行兩兩比較，直至選出最小關(guān)鍵字記錄。該思想可以以一棵有n個(gè)葉結(jié)點(diǎn)的完全二叉樹(shù)表示存在多余比較，輔助空間多49386597761327494938659776132749386513273813134938659776∞274938657627382727選擇排序（三）堆排序：（需要輔助空間）堆定義：若以一維數(shù)組存儲(chǔ)一個(gè)堆，則堆對(duì)應(yīng)一棵完全二叉樹(shù)，且所有非葉子結(jié)點(diǎn)的值均不大于（或小于）其子女的值，根結(jié)點(diǎn)的值是最?。ɑ蜃畲蟮模┒雅判虻亩x：若在輸出堆頂?shù)淖钚≈岛螅沟檬Ｏ碌膎-1個(gè)元素的序列重又建成一個(gè)堆，則得到n個(gè)元素中的次小值。反復(fù)執(zhí)行，便能得到一個(gè)有序序列建成的堆。這樣一個(gè)自堆頂至葉子的調(diào)整過(guò)程稱為篩選選擇排序（四）堆排序需要解決的兩個(gè)問(wèn)題：如何由一個(gè)無(wú)序序列建成一個(gè)堆如何在輸出堆頂元素后，調(diào)整剩余元素成為一個(gè)新的堆例（無(wú)序變成堆）例（輸出后調(diào)整）不是穩(wěn)定排序時(shí)間復(fù)雜度低O(n*log2n)空間復(fù)雜度低O(C)適合n較大的情況，適合在較大n中找序列的前幾個(gè)數(shù)構(gòu)造過(guò)程：（構(gòu)造一個(gè)根結(jié)點(diǎn)最小的堆）將序列順序排成一棵二叉樹(shù)從第n/2個(gè)(取整)元素開(kāi)始向前篩選將該結(jié)點(diǎn)與孩子結(jié)點(diǎn)比較，將小的數(shù)作為根。若發(fā)生結(jié)點(diǎn)的上下層交換，則應(yīng)考慮新的下層結(jié)點(diǎn)是否需要繼續(xù)下墜至葉子節(jié)點(diǎn)。否則讀取第n/2-1的元素，重復(fù)比較過(guò)程直到讀取完第1個(gè)數(shù)為止493865977613274949386597761327494938654976132797493813497665279713384949766527971338274976654997考慮4號(hào)結(jié)點(diǎn)97考慮3號(hào)結(jié)點(diǎn)652號(hào)結(jié)點(diǎn)38已經(jīng)滿足堆定義，考慮1號(hào)結(jié)點(diǎn)97創(chuàng)建堆完畢n/2取整為4，從4號(hào)點(diǎn)開(kāi)始堆調(diào)整的步驟：用堆中最后一個(gè)元素代替根再?gòu)纳系较逻M(jìn)行調(diào)整，使二叉樹(shù)滿足堆的定義調(diào)整完后，再輸出根（堆頂元素），重復(fù)上述過(guò)程，直到所有元素都輸出，排序結(jié)束。13382749766549979738274976654913273897497665492738494976659727973849497665389749497665384949977665389776769765659776976576494965769776654997496549977665494997764949歸納：無(wú)論是創(chuàng)建堆還是堆調(diào)整，只要發(fā)生上下層的節(jié)點(diǎn)交換，就需要考慮新的下層結(jié)點(diǎn)是否需要繼續(xù)下墜至葉子位置上。歸并排序（二路歸并）基本思想：將兩個(gè)或兩個(gè)以上的有序表合并為一個(gè)有序表。（兩兩歸并）具體步驟：比較各子序列第一個(gè)記錄的關(guān)鍵字，最小的一個(gè)就是排序后序列的第一個(gè)記錄的關(guān)鍵字。取出該記錄，繼續(xù)比較各子序列現(xiàn)在的第一個(gè)記錄的關(guān)鍵字，找到排序后的第二個(gè)記錄時(shí)間復(fù)雜度O(n*log2n)穩(wěn)定算法，但使用較少?；鶖?shù)排序（一）前面所介紹的排序方法都是通過(guò)交換、移動(dòng)來(lái)實(shí)現(xiàn)的?；鶖?shù)排序是借助多關(guān)鍵字排序的思想，將單關(guān)鍵字按基數(shù)分為“多關(guān)鍵字”進(jìn)行排序。多關(guān)鍵字的排序（多個(gè)關(guān)鍵字分主，次）最高位優(yōu)先法（MSD法）：先按最主關(guān)鍵字排序，一直到按最次關(guān)鍵字排序后，將各組連接起來(lái)得到序列最低位優(yōu)先法（LSD法）：基數(shù)排序（二）鏈?zhǔn)交鶖?shù)排序基本思想：分配、收集對(duì)單關(guān)鍵字也可按多關(guān)鍵字排序方法進(jìn)行。拆分成多項(xiàng)，項(xiàng)的個(gè)數(shù)成為“基”（RADIX）采用LSD法進(jìn)行排序具體操作：從最低位起，按關(guān)鍵字的不同值將序列中的記錄分配到RADIX個(gè)隊(duì)列中，關(guān)鍵字相同的在同樣一鏈隊(duì)列中，最后按關(guān)鍵字大小順序鏈接起來(lái)穩(wěn)定算法109063930589184505269008083278把每位十進(jìn)制數(shù)字看成一個(gè)關(guān)鍵字：則k由3個(gè)關(guān)鍵字組成基為10e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]278109063930589184505269008083f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]930063083184505278008109589269505008109930063269278083184589個(gè)位e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]083930505184f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]063278008109589269十位e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]278930063008589184505269083f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]109008063083109184269278505589930百位各種內(nèi)部排序的比較各排序時(shí)間、空間復(fù)雜度表結(jié)