數(shù)據(jù)結(jié)構(gòu)排序ppt課件-在線(xiàn)瀏覽
2024-12-21 22:17本頁(yè)面
【正文】 序的結(jié)點(diǎn)，因此，已有部分結(jié)點(diǎn)有序，這樣，在排序中記錄移動(dòng)的次數(shù)就少，排序的效率也就高。 圖 希爾排序示例 例如，有 8個(gè)關(guān)鍵字序列為 {91,67,35,62,29,72,46,57}，插入排序的步長(zhǎng)序列為 4,2,1。 步長(zhǎng)序列的選擇沒(méi)有嚴(yán)格的規(guī)定 ，只要該序列 {d1, d2,…,dt} 滿(mǎn)足 d1d2…dt ，并且當(dāng) t≥1時(shí)， d1=1，該序列都可選作步長(zhǎng)序列。 用 C語(yǔ)言描述的希爾排序算法如下： 算法 希爾排序算法。 NODE x。 step0。 in。 j=istep。amp。 j=jstep。 } } } 希爾排序的分析是一個(gè)復(fù)雜的問(wèn)題，但它的排序速度要比直接插入排序快，另外，它是一種不穩(wěn)定排序 交換排序 交換排序 基本思想 ： 比較 二個(gè)待排序記錄的 關(guān)鍵字 ，若為 逆序 ，則 交換 位置，反之，保持原序。然后再 array[n1]到 array[1]之間進(jìn)行一趟“冒泡”，將具有次小關(guān)鍵字的記錄排到序列的第 2個(gè)位置上。 下一趟區(qū)間 下標(biāo) 0 1 2 3 4 5 6 初始關(guān)鍵字 [6， 0] [91 67 35 62 29 72 46] 第一趟冒泡后 [6， 1] 29 [91 67 35 62 46 72] 第二趟冒泡后 [6， 2] 29 35 [91 67 46 62 72] 第三趟冒泡后 [6， 3] 29 35 46 [91 67 62 72] 第四趟冒泡后 [6， 4] 29 35 46 62 [91 67 72] 第五趟冒泡后 [6， 5] 29 35 46 62 67 [91 72] 第六趟冒泡后 序列有序 29 35 46 62 67 72 91 圖 冒泡排序示例 例如，有一組關(guān)鍵字序列為 {91,67,35,62,29,72,46}，冒泡排序過(guò)程如圖 。 void BubbleSort (NODE array[],int n) /* 對(duì)存放在數(shù)組 array[]中，長(zhǎng)度為 n的序列冒泡排序 */ { int i,j,flag。 for(i=0。i++) { flag=0。ji。 array[j]=array[j1]。 flag=1。 /* 若一趟“冒泡”中沒(méi)有逆序，則序列已有序 */ } } 冒泡排序的時(shí)間復(fù)雜度為O(n2)，并且是一種穩(wěn)定排序?；舅枷胧牵和ㄟ^(guò) 一趟排序 后，大幅度減小排序序列的長(zhǎng)度 。一次劃分得到兩個(gè)小序列，再 遞歸 地對(duì) 這兩個(gè)小序列進(jìn)行劃分 ，直到序列的長(zhǎng)度為 1，這時(shí)待排序序列已排成有序。 對(duì) array[start]到 array[end]序列進(jìn)行 劃分 ，首先要確定一個(gè)劃分標(biāo)準(zhǔn)，通常 選取序列 的 第一個(gè)記錄的關(guān)鍵字 ，用變量 mid暫存，另附設(shè) 兩個(gè)指針 i和 j，其初值 分別 為 start和end，劃分的具體做法如下 (i=start， j=end )： (1)j從所指的位置開(kāi)始從后向前掃描，直到 array[j].key 時(shí)， array[j]和 array[i]交換， i增 1。 (3)重復(fù) (1),(2)，直到 i=j結(jié)束，將 array[i]=mid。 例如，有一組關(guān)鍵字序列為 {49,38,65,97,76,13,38,50}，其進(jìn)行一趟劃分的過(guò)程如圖 (a)所示，整個(gè)序列快速排序過(guò)程如圖 (b)。 void Quick_Sort(NODE array[],int start,int end) /* 對(duì)從 array[start]到 array[end]的記錄快速排序 */ { int i,j。 if(start=end) return。 j=end。 while(ij) { while(ij amp。 array[j].key ) j。 i++。amp。 if(ij) { array[j]=array[i]。 } } array[i]=mid。 /* 對(duì) start到 i1的記錄進(jìn)行劃分 */ Quick_Sort(array,i+1,end)?？焖倥判蚴遣环€(wěn)定的排序。 直接選擇排序 直接選擇排序又稱(chēng)為簡(jiǎn)單選擇排序，其算法是：對(duì) n個(gè)記錄排
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1