數(shù)據(jù)結(jié)構(gòu)與算法分析課件第7章

數(shù)據(jù)結(jié)構(gòu)與算法分析

APracticalIntroductionto

DataStructuresandAlgorithmAnalysis

陳星

第三部分排序和檢索

第7章內(nèi)排序。第8章文件管理和外排序。第9章檢索。第10章索引技術(shù)。參考文獻(xiàn)：DataStructuresandAlgorithmAnalysis，C.A.Shaffer，電子工業(yè)出版社2002。數(shù)據(jù)結(jié)構(gòu)（C語言版），嚴(yán)蔚敏等，清華大學(xué)出版社1997。數(shù)據(jù)結(jié)構(gòu)—C++與面向?qū)ο蟮耐緩?，張乃?裘宗燕，高等教育出版社，2001。第7章內(nèi)排序在計算機(jī)主存內(nèi)對一組記錄進(jìn)行排序的標(biāo)準(zhǔn)算法。先介紹三種簡單但較慢（Θ(n2)）的算法.1.插入排序。

2.起泡（冒泡排序）。

3.選擇排序。再介紹幾種復(fù)雜但較快的算法.

如Shell排序、快速排序、堆排序、歸并排序……排序操作中的基本運(yùn)算.1.比較2.交換排序方法插入類排序選擇類排序交換類排序歸并排序插入排序希爾排序選擇排序堆排序快速排序分配類排序：基數(shù)排序起泡排序排序技術(shù)種類

按平均時間將排序分為四類：（1）平方階(O(n2))排序

一般稱為簡單排序，例如直接插入、直接選擇和冒泡排序（2）線性對數(shù)階(O(nlogn))排序

如快速、堆和歸并排序；

（3）O(n1+￡)階排序

￡是介于0和1之間的常數(shù)，即0<￡<1，如希爾排序；

（4）線性階(O(n))排序

如分配和基數(shù)排序。排序技術(shù)種類7.1排序術(shù)語及記號記錄之間通過一個比較器類進(jìn)行比較。關(guān)鍵字是數(shù)據(jù)元素中的某個數(shù)據(jù)項。每個記錄中都有一個關(guān)鍵碼域(key)。比較器類就是對該關(guān)鍵碼進(jìn)行比較;設(shè)對每一種記錄類型都已定義Swap函數(shù)。思考?

有一堆雜亂無章的撲克牌,要求你從A到2的順序在手上理好。想一想你會采用什么方法理好牌？

7.2三種代價為Θ（n2）的排序方法算法簡單、易懂、易于實(shí)現(xiàn)，但速度慢。7.2.1插入排序原理：將無序序列中的各元素依次與前面已排序的子序列進(jìn)行比較，將它插入到有序子序列中正確的位置。步驟：(1)首先將只含第1個元素的看成有序表。

(2)從線性表的第2個元素直到最后一個元素，依次將每個元素插入前面已經(jīng)有序的子表中。

(3)插入第j個元素的方法：將j放在變量T中，從有序子表（原線性表的前j-1個元素）的最后一個元素開始，往前逐個與T比較，將大于T的元素?zé)o向后移一個位置，直到發(fā)現(xiàn)一個元素不大于T為止，將T插入到剛移出的空位置上，有序子表的長度增加為j。插入排序比較1次交換1次

比較6次交換5次比較3次交換2次比較5次交換4次比較2次交換1次比較3次交換3次比較2次交換2次比較22次交換18次

插入排序的代價分析時間代價：最差情況下(原始紀(jì)錄全是逆序)：需要的比較次數(shù)：Θ(n2)

最佳情況下(原始紀(jì)錄已經(jīng)有序)：只需要n-1次比較；Θ(n)平均情況下：平均的時間代價是最差情況的一半，仍為Θ(n2)

空間代價：只需要一個暫存單元:Θ(1)

7.2.2起泡排序起泡排序的基本思想對所有相鄰記錄的關(guān)鍵字值進(jìn)行比效，如果是逆序（a[j]>a[j+1]），則將其交換，最終達(dá)到有序化。其處理過程為：對待排序的記錄序列從后向前（或從前向后）進(jìn)行掃描。依次比較相鄰記錄的關(guān)鍵字。交換比較中發(fā)現(xiàn)的逆序。因此關(guān)鍵字值小的記錄左移，關(guān)鍵字值大的記錄右移。一次掃描后，最小值移動序列的頂端。做n-1遍從后向前（或從前向后）的掃描和逆序交換，或直到未發(fā)現(xiàn)逆序?yàn)橹?。起泡排序算法P144-145算法：template<classElem,classComp>voidbubsort(ElemA[],intn){for(inti=0;i<n-1;i++)for(intj=n-1;j>i;j--)if(Comp::lt(A[j],A[j-1]))swap(A,j,j-1);}教科書上有錯起泡排序代價分析比較次數(shù)：時間代價：Θ(n2)

需增加一個輔助單元進(jìn)行交換；空間代價：Θ(1)問：如何改進(jìn)P144-145算法，減少起泡排序的比較和交換次數(shù)？7.2.3選擇排序基本思想：掃描整個線性表，從中選出最小的元素，將它交換到表的最前面；然后對剩下的子表采用同樣的辦法，直到子表空為止。template<classElem,classComp>voidselsort(ElemA[],intn){for(inti=0;i<n-1;i++){intlowindex=i;//Rememberitsindexfor(intj=n-1;j>i;j--)//Findleastif(Comp::lt(A[j],A[lowindex]))lowindex=j;//Putitinplaceswap(A,i,lowindex);}}選擇排序和起泡排序的比較相同：表面上來看，一輪比較和交換后，最小值都放到了頂部；實(shí)質(zhì)上而言，選擇排序就是起泡排序；不同：選擇排序中最小元素一次交換到位；選擇排序的交換次數(shù)要比起泡排序少得多。起泡排序選擇排序選擇排序的時間代價選擇排序?qū)嵸|(zhì)上是起泡排序。選擇排序比較次數(shù)：Θ(n2)交換的次數(shù)比起泡排序少。因此，總的時間代價為Θ(n2)

。交換指針只交換指針，不移動記錄本身，換來更高的效率,特別當(dāng)記錄很大的時候?？梢越档团判蛩惴ㄖ薪粨Q記錄所需要的時間。7.2.4交換排序算法的時間代價InsertionBubbleSelectionComparisons:BestCase(n)Q(n2)Q(n2)AverageCaseQ(n2)Q(n2)Q(n2)WorstCaseQ(n2)Q(n2)Q(n2)SwapsBestCase00(n)AverageCaseQ(n2)Q(n2)(n)WorstCaseQ(n2)Q(n2)(n)這些排序方法只比較相鄰的記錄。交換排序的最小時間代價(平均來說):考慮一個有n個元素的序列L；L中有n(n-1)/2對不同的元素，每一對都可能是一個逆置；平均而言，一半正序，一半逆序(即每個序列有n(n-1)/4對逆置序列)；相鄰元素交換只能處理掉一個逆序；任何一種將比較限制在相鄰兩個元素之間進(jìn)行的交換算法的平均時間代價都是Q

(n2)。7.3Shell排序又稱為縮小增量排序。基本思想：將整個線性表進(jìn)行分割，相隔某個增量h的元素構(gòu)成一個子表，對子表分別進(jìn)行插入排序，并逐漸減小增量h。最后當(dāng)h為1時，進(jìn)行一次插入排序，排序完成。希爾排序中，確定增量的大小是關(guān)鍵，但迄今未能得到解決。增量序列一般取ht=n/2k(k=1,2,3,…,[logn])，其中n為待排序列的長度。

增量序列也可以以每次除以3來選?。ā?，121，40，13，4，1）希爾排序例子對關(guān)鍵字序列<07,19,24,13,31,08,82,18,44,63,05,29>

進(jìn)行希爾排序：該例中n=12，[logn]=[log12]=3；取增量系列為ht=12/2k(k=1,2,3)，即h1=12/2=6,h2=12/4=3,h3=12/8≈1071924133108821844630529h1=6071824130508821944633129結(jié)果h2=3071824130508821944633129結(jié)果070508131824631929823144h3=1結(jié)果070508131824631929823144050708131819242931446382Shell排序分析相當(dāng)困難，其效率依賴于增量序列的選取。可以認(rèn)為Shell排序的平均時間代價為Θ(n1.5)希爾排序的空間代價為Θ(1)；同插入排序一樣，希爾排序也只需要一個記錄大小的輔助空間，用于暫存當(dāng)前待插入的記錄。當(dāng)n為中等規(guī)模大小時Shell排序是不錯的選擇二叉查找樹中序遍歷有序序列888082688582

7571778880826885827177757.4快速排序分治法(divideandconquer)的思想：根結(jié)點(diǎn)將左、右子樹分開，形成：左子樹<根右子樹二叉查找樹中序周游可得到有序序列，但弊端多：存儲占用大量結(jié)點(diǎn)空間、二叉樹不平衡時插入時間代價大。

快速排序以一種更有效的方法實(shí)現(xiàn)了“分治法”思想。基本思想：從待排序序列中選取一個元素，以該關(guān)鍵字值為軸值(pivot)，將待排序列分割為兩個子序列。軸值左側(cè)子序列中記錄都小于或等于軸值，右側(cè)子序列中記錄都大于或等于軸值。對子序列反復(fù)進(jìn)行分割，直到每個子序列的元素個數(shù)為1。整個線性表變成了有序表。快速排序以60為軸值，一趟分割后結(jié)果以6為軸值，二趟分割后結(jié)果以73為軸值，二趟分割后結(jié)果關(guān)鍵技術(shù)：線性表的分割考慮：1、大（?。┑脑匾苿拥奖淼暮螅ㄇ埃┌氩糠?。2、在原表中移動，要考慮空位。具體步驟：附設(shè)兩個指針i和j，初值分別指向第一個記錄和最后一個記錄，將分割中項保存在臨時變量T中

，再將第一個記錄移動分割中項的位置。首先從j所指位置起向前搜索，找到小于T的記錄移動到i指向的位置，然后從i所指位置起向后搜索，找到大于T的記錄移動到j(luò)指向的位置。重復(fù)這兩步直至i=j為止?？焖倥判虻牟襟E123 456783865764913273997

j

i分割中項T快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。整個表：從38，97和49中取出中項49作為分割中項T進(jìn)行快速排序123 456783865764913273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。將分割中項49保存在變量T中，將i所指向的記錄38移到分割中項位置。123 4567865763813273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。首先指針j指向的記錄與T進(jìn)行比較。97>T，不交換。123 4567865763813273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。指針j繼續(xù)向前掃描。39<T。123 4567865763813273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。將39移動i所指位置。123 4567865763813273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。指針i開始向后掃描，65>T。123 4567865763813273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。將65移動j所指位置，指針j開始向前掃描。123 4567865763813273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。27<T123 4567865763813273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。將27移動i所指位置，指針i開始向后掃描。123 4567865763813273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。76>T。123 4567865763813273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。將76移動j所指位置，指針j開始掃描。123 4567865763813273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。13<T。123 4567865763813273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。123 4567865763813273997將13移動i所指位置，指針i開始向后掃描。123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。123 456786576381327399738<T，不移動，指針i繼續(xù)向后掃描。123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。123 4567865763813273997指針i和j相遇，將分割中項填入i和j所指位置。一趟分割結(jié)束。49快速排序的時間代價最佳情況:分割中項每次都為序列中記錄中間值，時間代價為Θ(nlogn);最環(huán)情況:分割中項每次都為序列中記錄的最大值或最小值，時間代價為Θ(n2);平均情況:平均時間代價Θ(nlogn)?？焖倥判虻目臻g代價快速排序每次只能對一個子表進(jìn)行排序，已劃分的另一個子表需要用棧來記錄下來，留待以后進(jìn)行排序。通常情況下空間代價(記錄子表的棧)為Θ(logn);最壞情況下空間代價為Θ(n);快速排序的優(yōu)化軸值pivot的選取第一個或最后一個記錄的關(guān)鍵字易退化為起泡算法。隨機(jī)選取值開銷大數(shù)組中間點(diǎn)三者取中法首中尾三個記錄的中間值用于小子表的更佳算法劃分過程沒有必要劃分到子表長度為1的情況，當(dāng)子表長度小于某個值時，調(diào)用其他排序方法會快點(diǎn)。消除遞歸將遞歸改成非遞歸算法。速度加快?？焖倥判蚩偨Y(jié)快速排序是一個遞歸的過程。在遞歸調(diào)用時需要占據(jù)一定的存儲空間用來保存每一層遞歸調(diào)用時的必要信息?？焖俚男逝c起泡排序相比有很大地提高。在起泡排序過程中是對相鄰兩個記錄進(jìn)行關(guān)鍵字比較和互換的，這樣每次交換記錄后，只能改變一對逆序記錄；而快速排序則從待排序記錄的兩端開始進(jìn)行比較和交換，并逐漸向中間靠攏，每經(jīng)過一次交換，有可能改變幾對逆序記錄，從而加快了排序速度。到目前為止快速排序是平均速度最快的一種排序方法，歸并排序歸并是指將兩個或兩個以上的有序表合并成一個新的有序表。歸并排序的基本思想是將一個具有n個待排序記錄的序列看成是n個長度為1的有序序列，然后進(jìn)行兩兩歸并，得到n/2個長度為2的有序序列，再進(jìn)行兩兩歸并，得到n/4個長度為4的有序序列，如此重復(fù)，直至得到一個長度為n的有序序列為止。歸并排序的關(guān)鍵技術(shù)

－將兩個有序序列合并為一個有序序列方法：順序比較兩個表中的元素，將值小者移入合并后的新表中，反復(fù)如此，直至所有元素都移入新表。0123 44913659776780AB0123 4567Cijk設(shè)置指針i,j,k分別指向A,B,C的第一個單元。歸并排序的關(guān)鍵技術(shù)

－將兩個有序序列合并為一個有序序列方法：設(shè)置指標(biāo)，順序比較兩個表中的元素，將值小者移入合并后的新表中，反復(fù)如此，直至所有元素都移入新表。0123 44913659776780AB0123 4567Cijk7<13，移走7，指標(biāo)j和k后移一位。7歸并排序的關(guān)鍵技術(shù)

－將兩個有序序列合并為一個有序序列方法：設(shè)置指標(biāo)，順序比較兩個表中的元素，將值小者移入合并后的新表中，反復(fù)如此，直至所有元素都移入新表。0123 449659776780AB0123 4567Cijk

13<76，移走13，指標(biāo)i和k后移一位。713歸并排序的關(guān)鍵技術(shù)

－將兩個有序序列合并為一個有序序列方法：設(shè)置指標(biāo)，順序比較兩個表中的元素，將值小者移入合并后的新表中，反復(fù)如此，直至所有元素都移入新表。0123 4659776780AB0123 4567Cijk

49<76，移走13，指標(biāo)i和k后移一位。71349歸并排序的關(guān)鍵技術(shù)

－將兩個有序序列合并為一個有序序列方法：設(shè)置指標(biāo)，順序比較兩個表中的元素，將值小者移入合并后的新表中，反復(fù)如此，直至所有元素都移入新表。0123 49776780AB0123 4567Cijk

65<76，移走65，指標(biāo)i和k后移一位。7134965歸并排序的關(guān)鍵技術(shù)

－將兩個有序序列合并為一個有序序列方法：設(shè)置指標(biāo)，順序比較兩個表中的元素，將值小者移入合并后的新表中，反復(fù)如此，直至所有元素都移入新表。0123 497780AB0123 4567Cijk

76<97，移走76，指標(biāo)j和k后移一位。713496576歸并排序的關(guān)鍵技術(shù)

－將兩個有序序列合并為一個有序序列方法：設(shè)置指標(biāo)，順序比較兩個表中的元素，將值小者移入合并后的新表中，反復(fù)如此，直至所有元素都移入新表。0123 4977AB0123 4567Cijk

80<97，移走80。71349657680歸并排序的關(guān)鍵技術(shù)

－將兩個有序序列合并為一個有序序列方法：設(shè)置指標(biāo)，順序比較兩個表中的元素，將值小者移入合并后的新表中，反復(fù)如此，直至所有元素都移入新表。0123 47AB0123 4567Cijk由于B已移空，停止比較，將A中剩余元素全部移到C中。7134965768097歸并排序的偽代碼Listmergesort(Listinlist){if(length(inlist)<=1)returninlist;Listl1=halfoftheitemsfrominlist;Listl2=otherhalfofitemsfrominlist;returnmerge(mergesort(l1),mergesort(l2));}template<classElem,classComp>voidmergesort(ElemA[],Elemtemp[],intleft,intright){if((right-left)<=THRESHOLD){

inssort<Elem,Comp>(&A[left],right-left+1);return;}inti,j,k,mid=(left+right)/2;if(left==right)return;mergesort<Elem,Comp>(A,temp,left,mid);mergesort<Elem,Comp>(A,temp,mid+1,right);for(i=mid;i>=left;i--)temp[i]=A[i];for(j=1;j<=right-mid;j++)temp[right-j+1]=A[j+mid];for(i=left,j=right,k=left;k<=right;k++)if(temp[i]<temp[j])A[k]=temp[i++];elseA[k]=temp[j--];}用插入排序處理較短的數(shù)組兩個子數(shù)組相向插入，不需要檢查子序列是否處理完成歸并排序的優(yōu)化實(shí)現(xiàn)歸并排序的時/空間代價每次合并的時間代價為Θ(n)；從步長為1開始，整個合并完成需要logn次，總的時間代價為Θ(nlogn)。該時間代價并不依賴于待排數(shù)組中數(shù)值的相對順序，因此，它也就是歸并排序最佳、平均和最差的運(yùn)行時間。歸并排序同樣也適用于處理鏈?zhǔn)酱鎯Φ拇抨P(guān)鍵字序列.需要與待排序空間等量的輔助空間，空間代價為Θ(n).這是歸并排序的嚴(yán)重缺陷。7.4堆排序堆排序耗時：初始建堆時間＋(n-1)?調(diào)整一次堆的時間。最初，堆調(diào)整的路長決定于樹的深度Θ(logn)，隨著選出結(jié)點(diǎn)的增多，待排的堆體積不斷減小，調(diào)整的路長也不斷減小，所以調(diào)整的時間代價最多為Θ(logn)；即堆排序總的時間為Θ(n)+(n-1)?Θ(logn)，也就是說堆排序的時間代價為Θ(nlogn)；堆排序需要一個輔助空間，即空間代價為Θ(1)。堆排序?qū)υ加涗浀呐帕袪顟B(tài)并不敏感，適用于規(guī)模(n)較大的待排序序列。分配排序一個簡單、有效的排序:for(i=0;i<n;i++)B[A[i]]=A[i];關(guān)鍵碼B[]用來確定一個記錄在排序中的最終記錄，用“盒子”來存放待排記錄。這種排序方法的時間代價是(n),

但是它只能處理對一個從0到n-1的排列進(jìn)行排序。擴(kuò)展分配排序方法一：盒子可變長，允許關(guān)鍵碼重復(fù)。即數(shù)組B中元素為一個鏈表的頭結(jié)點(diǎn).

關(guān)鍵碼重復(fù)的記錄在一個鏈表中，需要額外進(jìn)行排序。方法二：允許關(guān)鍵碼范圍大于n，先將所有的A[i]放入B中，再依次從關(guān)鍵碼B中讀出記錄.B的大小決定于記錄的最大值MaxKeyValue.將所有記錄A[i]放入B中的時間代價是(n)，從B中讀出所有記錄的時間代價是(MaxKeyValue)，故總時間代價是(n+MaxKeyValue)。但是,記錄的規(guī)模n和MaxKeyValue之間沒有任何必然聯(lián)系,因此,該算法的時間代價可能為(n2)甚至更糟.分配排序的擴(kuò)展桶式排序

BucketSort每一個“盒子(桶)”中存放一組相關(guān)的關(guān)鍵碼,然后借助其他排序技術(shù)對每一個“桶”中的記錄排序。分桶處理技術(shù)＋收尾排序?；鶖?shù)排序?qū)⑴判蜿P(guān)鍵字K看作是由多個關(guān)鍵字組成的組合關(guān)鍵字，即K=k1k2…kd。每個關(guān)鍵字ki表示關(guān)鍵字的一位，其中k1為最高位，kd為最低位，d為關(guān)鍵字的位數(shù)。例如，序列(101,203,567,231,478,352)，可以將每個關(guān)鍵字K看成由三個單關(guān)鍵字組成，即K=k1k2k3，每個關(guān)鍵字的取