數(shù)據(jù)結(jié)構(gòu)排序ppt課件-文庫(kù)吧資料
2024-11-09 22:18本頁(yè)面
【正文】 13254 ? 簡(jiǎn)單選擇排序與冒泡排序的區(qū)別：交換數(shù)量減少、趟次增加、不穩(wěn)定。 //在 [i..length]中查找 key最小的記錄 if(i!=j) [i] [j]。 i。 //將該記錄與第 i個(gè)記錄交換 } } 第 2 趟 13 27 65 97 76 49 38 49 *第 3 趟 13 27 38 97 76 49 65 49 *簡(jiǎn)單選擇排序 ? 算法 2(P277)： void Select_Sort(SqList amp。 j++) //注意前后兩個(gè)循環(huán) 走向相同 if([j].key [min].key) min=j。 //首先假設(shè)子表中首元素最小 for(j=i+1。 i++) //i：趟次，即找到的最小元素的目標(biāo)位置。L) { for(i=1。但注意存儲(chǔ)記錄的輔助空間只需要 1個(gè) ? 穩(wěn)定性：不穩(wěn)定。 //對(duì)樞軸高端子表遞歸排序 } } 例子程序參見(jiàn)： 快速排序 ? 性能分析： ? 平均時(shí)間復(fù)雜度： O(nlogn)，最壞時(shí)，如序列恰好有序或恰好逆序時(shí)為： O(n2)。 //以樞軸為基準(zhǔn)，將順序表一分為二，返回樞軸位置 QSort(L, low, pivot_location 1)。 但不能省略 if判斷，否則上一句 while循環(huán)最后是執(zhí)行 — high時(shí)，返回的 low值有問(wèn)題 注意不能省略兩處比較中的等號(hào)，否則死循環(huán) 快速排序 void QSort(SqList amp。 //low==high時(shí)結(jié)束循環(huán)，該處即樞軸最終位置 return low。 //高端比樞軸大的記錄位置保持不變 [high] = [low]。amp。 //高端比樞軸小的記錄移動(dòng)到低端。 [high].key = pivot_key) high。 //注意 low不一定是 1，也不要把 [0]誤看作 [low1] while(lowhigh) //從順序表的 兩端交替向中間掃描 ，直到 low==high { while(lowhigh amp。 pivot_key=[low].key。該過(guò)程稱為一趟快速排序或一次 劃分 。 ? 答：借助劃分的思路，或前幾頁(yè)最后一個(gè)方法 (如圖 ,但不一定好 ) 1 2 3 3 4 1 2 2lo w h ig h比較 n次，最多移動(dòng) n+1次，空間 1 1 2 3 3 4 1 2 2lo w h ig h比較 n次，最多移動(dòng) n+1次，空間 1 快速排序 ? 劃分算法的整體思路： Partition(L) { 暫存樞軸： t=[low] while(lowhigh) { 從右向左找關(guān)鍵字比樞軸小的元素 移動(dòng)該元素： [low]=[high] 從左向右找關(guān)鍵字比樞軸大的元素 移動(dòng)該元素： [high]=[low] } 樞軸歸位： [low]=t } int Partition(SqList amp。 ? 答：恰好有序時(shí) 2次；恰好無(wú)序時(shí) 3次。 ? 例如以第一個(gè)元素為基準(zhǔn)，經(jīng)一趟排序后期望達(dá)到的效果如圖： ? 下一趟排序，由于比較操作將局限在各部分內(nèi)進(jìn)行，不會(huì)與整個(gè)表中每個(gè)元素逐一比較，比較次數(shù)會(huì)逐趟減半，趟次也大大減少。 1 2 3 4 3 2 1 2p 1 2 3 3 4l o w h i g h 比較 n次，移動(dòng) 2n次，空間 2n 1 2 3 3 4 1 2 2p 1 2 3 4 3lo w h ig h比較 n次，移動(dòng) 2n次，空間 n 1 2 3 3 4 1 2 2lo w h ig h比較 n次，最多移動(dòng) ，空間 1 1 2 3 3 4 1 2 2lo w h ig h比較 n次，最多移動(dòng) n+1次，空間 1 快速排序 ? 每一趟排序以某個(gè)元素為基準(zhǔn)將待排記錄分割成獨(dú)立的兩部分，小于基準(zhǔn)的記錄放在基準(zhǔn)的前面，大的放在后面。 ? 穩(wěn)定性：穩(wěn)定 ? 提問(wèn)：對(duì)整數(shù)序列 32154進(jìn)行從小到大的排序，經(jīng)過(guò)一趟冒泡排序之后的序列怎樣？完成排序至少需要多少趟？ ? 答： 13245， 3趟。} //注意無(wú) else語(yǔ)句 } } //結(jié)束條件是該趟沒(méi)有進(jìn)行過(guò)交換操作 第 2 趟 13 27 49 38 65 97 76 49 *第 3 趟 13 27 38 49 49 * 65 97 76冒泡排序性能分析 ? 性能分析： ? 比較操作： O(n2)；移動(dòng)操作： O(n2)。 j) //從后向前交換相鄰逆序元素 if([j+1].key [j].key) //這里下標(biāo)＝位序 {[j+1] [j]。 for(j=。 change==true。 i amp。 //注意無(wú) else語(yǔ)句 } 第 2 趟 13 27 49 38 65 97 76 49 *第 3 趟 13 27 38 49 49 * 65 97 76冒泡排序 ? 算法 2(參見(jiàn) P16，改進(jìn)方法：一旦某趟沒(méi)有進(jìn)行過(guò)交換操作則排序結(jié)束，設(shè)置 change標(biāo)志標(biāo)識(shí)之 )： void BubbleSort(SqList amp。 j) //交換 [i～ length]中相鄰逆序元素。 //每一趟交換 [i～ length]中相鄰逆序元素 //結(jié)果：最小元素到達(dá)第 i處 for(j=。 i。 冒泡排序
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1