第六講查找與排序,查找：查找是在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中，根據(jù)給定的條件查找滿足條件的結(jié)點(diǎn)。不同的數(shù)據(jù)結(jié)構(gòu)采用不同的查找方法。查找的效率直接影響數(shù)據(jù)處理的效率。查找的結(jié)果：查找成功：找到滿足條件的結(jié)點(diǎn)查找失?。赫也坏綕M足條件的結(jié)點(diǎn)。,可以采用從前向后查，也可采用從后向前查的方法。在平均情況下，大約要與表中一半以上元素進(jìn)行比較，效率較低。平均查找長(zhǎng)度較大。,查找過程：對(duì)給定的一關(guān)鍵字K，從線性表的一端開始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和K的比較，直到找到關(guān)鍵字等于K的記錄或到達(dá)表的另一端。,6.1順序查找,監(jiān)視哨,使用了監(jiān)視哨，在查找過程中，不用每一步都去判斷是否查找結(jié)束。找到：返回元素在線性表中的存儲(chǔ)位置；未找到：返回0。,思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止。前提：必須在具有順序存儲(chǔ)結(jié)構(gòu)的有序表中進(jìn)行。,分三種情況：1）若中間項(xiàng)的值等于x,則說明已查到。2）若x小于中間項(xiàng)的值，則在線性表的前半部分查找；3）若x大于中間項(xiàng)的值，則在線性表的后半部分查找。,6.2折半查找（二分法查找）,查找23和79的過程如下圖：,mid=(low+high)/2不進(jìn)位取整,(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),基本思想:首先在所有記錄中選出關(guān)鍵字最小的記錄，把它與第1個(gè)記錄交換，然后在其余的記錄中再選出關(guān)鍵字次最小的記錄與第2個(gè)記錄交換，以次類推，直到所有記錄排序完成。,6.3選擇排序,選擇排序示例,49,38,65,97,76,13,27,49*,13,38,65,97,76,49,27,49*,13,27,65,97,76,49,38,49*,13,27,38,97,76,49,65,49*,13,27,38,49,76,97,65,49*,13,27,38,49,49*,97,65,76,13,27,38,49,49*,65,97,76,13,27,38,49,49*,65,76,97,6.4冒泡排序,基本思想:兩兩相鄰元素依次進(jìn)行比較,讓值較大的結(jié)點(diǎn)往下移(下沉)，讓值較小的結(jié)點(diǎn)往上移(上冒)。,冒泡排序示例,21254925*1608212525*1608492125160825*492116082525*491608212525*490816212525*49,6.5插入排序,基本思想:（1）將數(shù)據(jù)序列分為2個(gè)部分,前面已排序,后面未排序。（2）依次考察未排序的每個(gè)數(shù)據(jù)，將其按其關(guān)鍵字大小，插入到前面已經(jīng)排好序的適當(dāng)位置上。,插入排序舉例：,21254925*160821254925*160821254925*1608212525*49160816212525*49080816212525*49,6.6歸并排序,基本思想:通過對(duì)兩個(gè)有序數(shù)據(jù)序列的歸并來實(shí)現(xiàn)排序。所謂歸并是指將若干個(gè)已排好序的部分合并成一個(gè)有序的部分。歸并分類：二路歸并、三路歸并、多路歸并,歸并排序示例,(25)(57)(48)(37)(12)(92)(86),(2557)(3748)(1292)(86),(25374857)(128692),(12253748578692),6.7快速排序,基本思想:取待排序列中某個(gè)元素的值作為基準(zhǔn)值，將待排序列劃分為兩個(gè)部分，左邊部分的所有元素都小于等于這個(gè)基準(zhǔn)值，而右邊部分的所有元素都大于等于這個(gè)基準(zhǔn)值。然后，對(duì)左右兩個(gè)子表用同樣的方法(遞歸)進(jìn)行劃分.,快速排序示例(第一趟劃分),49,38,65,97,76,13,27,49*,38,65,97,76,13,27,49*,27,38,65,97,76,13,49*,27,38,97,76,13,65,49*,27,38,13,97,76,65,49*,27,38,13,76,97,65,49*,27,38,13,49,76,49,65,49*,49,temp,6.8堆排序,基本思想:在排序過程中，將r1到rn看成是一個(gè)完全二叉樹順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來選擇最小元素。,10,15,56,25,30,70,10,15,56,25,30,70,小頂堆示例,70,56,30,25,15,10,70,56,30,25,15,10,大頂堆示例,堆排序的過程：,（1）將無序序列建成一個(gè)堆。（2）輸出堆頂元素，將剩余元素調(diào)整為一個(gè)新堆。,例子：關(guān)鍵字序列為42，13，91，23，24，16，05，88，n=8，故從第四個(gè)結(jié)點(diǎn)開始調(diào)整,42,13,91,23,24,16,05,88,42,13,91,23,24,16,05,88,42,13,91,88,24,16,05,23,42,13,91,88,24,16,05,23,不調(diào)整,42,13,91,88,24,16,05,23,42,13,91,88,24,16,05,23,42,88,91,23,24,16,05,13,42,88,91,23,24,16,05,13,91,88,42,23,24,16,05,13,91,88,42,23,24,16,05,13,建成的堆,91,88,42,23,24,16,05,13,91,88,42,23,24,16,05,13,（1）初始堆R1到R8,13,88,42,23,24,16,05,91,13,88,42,23,24,16,05,91,（2）第一趟排序之后,（3）重建的堆r1到r7,88,24,42,23,13,16,05,91,88,24,42,23,13,16,05,91,05,24,42,23,13,16,88,91,05,24,42,23,13,16,88,91,（4）第二趟排序之后,（5）重建的堆r1到r6,42,24,16,23,13,05,88,91,42,24,16,23,13,05,88,91,（6）第三趟排序之后,05,24,16,23,13,42,88,91,05,24,16,23,13,42,88,91,（7）重建的堆r1到r5,24,23,16,05,13,42,88,91,24,23,16,05,13,42,88,91,（8）第四趟排序之后,13,23,16,05,24,42,88,91,13,23,16,05,24,42,88,91,（9）重建的堆r1到r4,23,13,16,05,24,42,88,91,23,13,16,05,24,42,88,91,（10）第五趟排序之后,05,13,16,23,24,42,88,91,05,13,16,23,24,42,88,91,（11）重建的堆r1到r3,16,13,05,23,24,42,88,91,16,13,05,23,24,42,88,91,（12）第六趟排序之后,05,13,16,23,24