[計(jì)算機(jī)軟件及應(yīng)用]數(shù)據(jù)結(jié)構(gòu)第9章排序中國(guó)石油大學(xué)華東(編輯修改稿)
2024-11-15 04:12 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 類推，則完成排序。 冒泡排序 (Bubble Sort) 9 8 5 4 2 0 9 8 5 4 2 0 89594929099 9 8 5 4 2 0 9 584828088 8 4 2 0 5 8 9 5 5 2 0 4 5 8 9 4 4 0 2 4 5 8 9 2 2 結(jié)果 ㈠ ㈡ ㈢ ㈣ 開始 ㈤ 0 2 4 5 8 9 比較次數(shù)： 5 4 3 2 1 17 基本思想： ① 任取 待排序元素序列中的某個(gè)元素作為 基準(zhǔn)（支點(diǎn)，一般去第一個(gè)） ，按照該元素的排序碼大小，將整個(gè)元素序列劃分為 左右兩個(gè)子序列 ： ? 左側(cè)子序列中所有元素的都小于基準(zhǔn)元素 ? 右側(cè)子序列中所有元素的都大于基準(zhǔn)元素 ② 基準(zhǔn)元素則排在這兩個(gè)子序列中間 (這也是該元素 最終應(yīng)安放的位置 )。 ③ 然后分別對(duì)這兩個(gè)子序列重復(fù)施行上述方法，直到所有的元素都排在相應(yīng)位置上為止。 快速排序 (Quick Sort) 做法： 附設(shè)兩個(gè)指針 low和 high ，初值分別指向 第一個(gè)記錄和 最后一個(gè)記錄 ，設(shè) 支點(diǎn)記錄 為 r[1] ， (r[1]通常取第一個(gè)記錄的值為基準(zhǔn)值。 ) 首先從 high所指位置起 向前 搜索，找到第一個(gè) 小于基準(zhǔn)值的記錄與基準(zhǔn)記錄交換（大的原地不動(dòng)）， 然后從 low 所指位置起 向后 搜索，找到第一個(gè) 大于基準(zhǔn)值的記錄與基準(zhǔn)記錄交換（小的原地不動(dòng)）， 重復(fù)這兩步直至 low=high為止。 例 初始關(guān)鍵字： 49 38 65 97 76 13 27 50 L H r[1] .KEY=49 H 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分別進(jìn)行快速排序 : ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序結(jié)束： 13 27 38 49 50 65 76 97 4927L L H L 49 65H 13 49 49 97L H 20 選擇排序 基本思想是 : ? 首先從 1~n個(gè)元素中選出關(guān)鍵字 最小 的記錄交換到 第一個(gè) 位置上。然后再?gòu)牡?2 個(gè)到第 n個(gè)元素中選出次小的記錄交換到 第二個(gè) 位置上，依次類推。 ? 時(shí)間復(fù)雜度為 O(n2)， ? 適用于 待排序元素較少 的情況。 21 直接選擇排序 (Select Sort) 直接選擇排序的算法如下： void SelectSort( STBL L[ ],int n) { int i,j,k,t。 for (i=0,in。++i） { k=i； 第 I小的元素 for(j=i+1。jn。++j) if ( L[j].keyL[k].key) k=j。 if(k!=i) { t=L[i]。 L[i]=L[k]。 L[k]=t ； }
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1