數(shù)據(jù)結(jié)構(gòu)與算法-第22講交換排序

1第22講交換排序本講知識點(diǎn)：(1)了解交換排序的思想(2)掌握冒泡排序、快速排序的算法(3)掌握交換排序的應(yīng)用難點(diǎn)：快速排序2排序的基本概念各種排序方法各種排序方法的比較排序知識體系結(jié)構(gòu)排序

插入排序

選擇排序交換排序

歸并排序基數(shù)排序直接插入排序折半插入排序鏈表插入排序希爾排序直接選擇排序堆排序冒泡排序快速排序3未來科學(xué)家班參觀華農(nóng)大DNA測序?qū)嶒?yàn)室引4生物DNA多序列比對是生物基因信息系統(tǒng)中現(xiàn)代生物序列分析的重要內(nèi)容，也是當(dāng)今生物信息學(xué)研究的熱點(diǎn)課題。通過比對，可以預(yù)測新序列的結(jié)構(gòu)和功能，可以分析序列之間的相似和同源關(guān)系，以及進(jìn)行系統(tǒng)發(fā)育分析。

Levenshteindistance可以用來：Spellchecking(拼寫檢查)、Speechrecognition(語句識別)、DNAanalysis(DNA分析)、Plagiarismdetection(抄襲檢測)。數(shù)據(jù)量龐大的基因比對的前提是排序！問題5揭示？

教育要從娃娃抓起比較次數(shù)是排序方法好壞的關(guān)鍵排序視頻6交換排序的主要操作是交換，其主要思想是：在待排序列中選兩個記錄，將它們的關(guān)鍵字相比較，如果反序（即排列順序與排序后的次序正好相反），則交換它們的存儲位置。交換排序反序則交換RiRj7一、冒泡排序BubbleSort

小數(shù)往前放，大數(shù)往后放，相當(dāng)于氣泡往上升805981269385381過程示例

12813881815305981269385381第一趟：排序成果是什么？基本思想：兩兩比較相鄰記錄的關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序的記錄為止。下一趟怎么做？初態(tài)：第1趟：98歸納：一共需要多少趟？每一趟的動作是？9voidBubbleSort(ElemType

elem[],intn){}if(elem[j]>elem[j+1]){ Swap(elem[j],elem[j+1]);}

//如出現(xiàn)逆序,則交換for(inti=n-1;i>0;i--)//共需n-1趟{(lán)

}for(intj=0;j<i;j++)//每趟比較n-i次{

}算法實(shí)現(xiàn)1005981269385381059812693853810598126938538105981269385381過程示例第1趟：第2趟：第3趟：第4趟：11voidBubbleSort(ElemType

elem[],intn){}if(elem[j]>elem[j+1]){ Swap(elem[j],elem[j+1]);}

//如出現(xiàn)逆序,則交換for(inti=n-1;i>0;i--)//共需n-1趟{(lán)

}for(intj=0;j<i;j++)//每趟比較n-i次{

}intflag=0；flag=1;if(!flag)break;算法改進(jìn)12345179812152021222327322971再改進(jìn)：對已順序的范圍進(jìn)行界定23456789101112再改進(jìn)：雙向冒泡過程示例13疑問：速度快嗎？程序演示：看看真實(shí)面目！結(jié)論：無法忍受，必須改進(jìn)！問題：改進(jìn)要從哪里入手？探討真相14改進(jìn)的著眼點(diǎn)：在冒泡排序中，記錄的比較和移動是在相鄰單元中進(jìn)行的，記錄每次交換只能上移或下移一個單元，因而總的比較次數(shù)和移動次數(shù)較多。減少總的比較次數(shù)和移動次數(shù)增大記錄的比較和移動距離較大記錄從前面直接移動到后面較小記錄從后面直接移動到前面二、快速排序QuickSort

1513652750384955i小的大的38思路分析1613652750384955ji13386527504955jjiiij136549273855ijjj50一趟快排17首先選一個軸值（即比較的基準(zhǔn)），通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分，前一部分記錄的關(guān)鍵字均小于或等于軸值，后一部分記錄的關(guān)鍵字均大于或等于軸值，然后分別對這兩部分重復(fù)上述方法，直到整個序列有序。基本思想18int

Partition(ElemType

elem[],intlow,inthigh){ while(low<high) {}

retutnlow;//low為軸值記錄的最終位置}while(low<high&&elem[low]<=elem[high])high--；//自右向左掃描Swap(elem[low],elem[high]);while(low<high&&elem[low]<=elem[high])low++；//自左向右掃描Swap(elem[low],elem[high];算法分析19解決方法：對分割得到的兩個子序列遞歸地執(zhí)行快速排序。1327386550495513275038495565ijij如何處理分割得到的兩個待排序子序列？后續(xù)問題20voidQuickSortHelp(ElemType

elem[],intlow,inthigh){

if(low<high){int

pivotLoc=Partition(elem,low,high);//一次劃分

QuickSortHelp(elem,low,pivotLoc-1);//對前一個子序列進(jìn)行快速排序

QuickSortHelp(elem,pivotLoc+1,high);//對后一個子序列進(jìn)行快速排序}算法描述21例：{38,27,55,50,13,49,65}的快速排序遞歸樹：38135055496527快速排序的遞歸執(zhí)行過程可以用遞歸樹描述。時(shí)間性能分析快速排序的時(shí)間性能快速排序遞歸的深度每次劃分軸值的選取22最好情況：每一次劃分對一個記錄定位后，該記錄的左側(cè)子表與右側(cè)子表的長度相同，為O(nlog2n)。T(n)≤2T(n/2)＋n≤2(2T(n/4)＋n/2)＋n＝4T(n/4)＋2n≤4(2T(n/8)＋n/4)＋2n＝8T(n/8)＋3n………≤nT(1)＋nlog2n＝O(nlog2n)時(shí)間性能分析23最壞情況：每次劃分只得到一個比上一次劃分少一個記錄的子序列（另一個子序列為空），為O(n2)。最好情況：每一次劃分對一個記錄定位后，該記錄的左側(cè)子表與右側(cè)子表的長度相同，為O(nlog2n)。平均情況：為O(nlog2n)。)()1(21211nOnninni=-=-?-=）（時(shí)間性能分析24改進(jìn)空間：1、問題降到一定規(guī)模時(shí)，改用插入排序2、中軸元素的選取3、考慮分區(qū)分成3堆，一方面避免相同元素這種情況，另一方面也可以降低子問題的規(guī)模。算法改進(jìn)251、采用冒泡排序法，對排序碼序列

57258641315724529按從小到大的次序排序，請寫出第一趟起泡后的結(jié)果。2、采用快速排序法，對排序碼序列

57258641315724529按從小到大的次序排序，請寫出以第一個排序碼為基準(zhǔn)進(jìn)行一次分組后的結(jié)果。實(shí)戰(zhàn)26冒泡和快速的排序時(shí)間對比27三、應(yīng)用舉例DNASorting序列“未排序程度”的一個計(jì)算方式是元素亂序的元素對個數(shù)。

SampleInput106AACATGAAG