C++程序設計與數(shù)據(jù)結構基礎：第11章 查找和排序

第三部分數(shù)據(jù)結構基礎第十

章

查找和排序本章內容查找順序查找二分查找排序直接插入排序直接選擇排序冒泡排序2§11.1 查找查找的基本概念查找（檢索）：在數(shù)據(jù)元素集合中查找關鍵字與給定值相等的數(shù)據(jù)元素。關鍵字：數(shù)據(jù)元素中的一個或多個數(shù)據(jù)項值，它可以唯一標識一個數(shù)據(jù)元素。平均查找長度(ASL)：n為查找表的長度；pi為查找第i個元素的概率，在等概率情況下pi等于1/n；Ci為找到第i個元素時的比較次數(shù)3順序查找查找表必須采用線性表。用給定值依次與線性表中每個元素的關鍵字進行比較。如果某個元素的關鍵字與給定值相同，則查找成功；如果找遍全表也沒有發(fā)現(xiàn)滿足條件的元素，則查找失敗。ASL約為表長度的一半，效率較低。4二分查找三個條件必須是線性表；必須以順序方式存儲；必須有序優(yōu)點：查找效率高缺點：18242931354756635§11.2 排序排序的基本概念排序：將文件中的記錄按排序碼非遞減（或非遞增）的順序重新排列。排序碼：數(shù)據(jù)元素中的一個或多個數(shù)據(jù)項。排序碼可以是關鍵字，也可以是其他若干數(shù)據(jù)項的組合。排序算法的穩(wěn)定性：如果在待排序的元素序列中，存在著多個排序碼相同的元素，按照某種排序算法排序后，這些元素的相對位置仍保持不變，則稱該排序算法是穩(wěn)定的，否則就是不穩(wěn)定的。6插入排序基本思想：把元素ei(0<i<n)依次插入到由S中前i個元素組成的已經排好序的序列{e0,e1,…,ei-1}的適當位置上，插入后S的前i+1個元素仍為有序所有元素分成兩個集合：已排序記錄集和待排序記錄集。初始時，已排序記錄集只有一個元素，即e0，待排序記錄集是所有剩余元素。然后每次從待排序記錄集中選取一個元素，找到其在已排序記錄集中的位置，將其插入到該位置，直到待排序記錄集為空。7直接插入排序以順序查找的辦法找到要插入的元素在已排好序的元素序列中應處的位置。直接插入排序是穩(wěn)定的排序算法3440752050{50,20,75,34,40}ASL：O(n2)8選擇排序基本思想：每次從待排序的元素序列中選擇一個最?。ù螅┑脑兀迦氲揭呀浥藕眯虻男蛄械暮筮呏苯舆x擇排序用逐個比較的辦法從待排序的元素序列中選出最小的元素。依次對i=0,1,2,…,n-2分別執(zhí)行如下的選擇和交換步驟：在元素序列ei,ei+1,…,en-1中選擇出最小的元素ek；當k≠i時，交換ei與ek的值。經上述n-1次的選擇和交換后，排序工作即已完成。{50,20,75,34,40}20507534402034755040203440755020344050759交換排序基本思想：消除逆序冒泡排序基本思想：從待排序記錄集的一端（這里假定為低端）對相鄰的兩個元素（e0和e1，e1和e2，…，en-2和en-1）依次比較它們的排序碼，若不符合排序的順序要求，就將相應的兩個元素互換，此過程稱為一趟冒泡排序，最多經過n-1趟冒泡排序，排序工作即可完成。最好情況下的時間復雜度為O(n)。最壞情況下的時間復雜度為O(n2)。

冒泡排序算法是穩(wěn)定的。1097275813496576待排序記錄27975813496576275897134965762758139749657627581349976576275813496597762758134965769727581349657697待排序記錄275813496576972758134965769727135849657697271349586576972713495865