[理學]大學教程零起點數(shù)據(jù)結構--排序-預覽頁
【正文】 48 68] 13 【 例 】 打撲克牌時的抓牌就是插入排序一個很好的例子，每抓一張牌，插入到合適位置，直到抓完牌為止，即可得到一個有序序列。 //list 為定義待排序記錄的數(shù)據(jù)類型 //并規(guī)定待排序記錄中 0元素不存數(shù)據(jù) 6 插入排序 直接插入排序（基于順序查找） 表插入排序（基于鏈表存儲） 折半插入排序（基于折半查找） 希爾排序（基于逐趟縮小增量） 7 插入排序 直接插入排序（基于順序查找） 直接插入排序思想： 依次將待排序記錄中的第 i個記錄插入到有序序列中 . 初始情況：將 r1作為有序序列，將 r2rn逐個插入 , 通過順序查找方式找到 ri在有序表中的位置 , 找位置的同時移動有序序列中元素的位置 , 找位置時從后向前找 . 在一個已排好序的記錄子集的基礎上，每一步將下一個待排序的記錄有序地插入到已排好序的記錄子集中，直到將所有待排記錄全部插入為止。 15 插入排序 直接插入排序（基于順序查找） Void StraightSort（ list r, int n） { for（ i=2； i=n。 j。 //記錄數(shù)組，從 1到 n int n。 } r[i].key amp。 i=n1。 j++ ) if( r[j+1].key r[j].key ) { flag=0。 } if( flag==1 ) return。 ji。amp。 ji。使得一組所有記錄的關鍵字小于基準記錄的關鍵字，另一組所有記錄的關鍵字大于等于基準記錄的關鍵字。 if(i =j) return。 if( ij ) { r[i]=r[j]。 r[i].key=r[0].key ) i++。 quick ( r,i+1,high) } 36 用快速排序法對數(shù)據(jù)序列 (49， 38， 65， 97， 16， 53， 134， 27， 39) 進行排序，寫出其第一趟排序的全過程 49， 38， 65， 97， 16， 53， 134， 27， 39 49 i j 37 快速排序 時間復雜度： O（ nlogn） 該算法不穩(wěn)定 若數(shù)據(jù)序列本身有序， 則算法執(zhí)行效率最低，近似 O（ n2） 38 選擇排序 直接（簡單）選擇排序算法思想 首先從待排序序列中選取最小記錄，把它與第一個記錄交換，然后在剩余的記錄中選擇最小記錄與第二個記錄進行交換，直至排序完成 直接（簡單）選擇排序 堆排序 39 初始關鍵字： 51 33 62 96 87 17 28 51 第一趟排序： [17]33 62 96 87 51 28 51 第二趟排序： [17 28] 62 96 87 51 33 51 第三趟排序： [17 28 33] 96 87 51 62 51 第四趟排序： [17 28 33 51] 87 96 62 51 第五趟排序： [17 28 33 51 51] 96 62 87 第六趟排序： [17 28 33 51 51 62] 96 87 第七趟排序： [17 28 33 51 51 62 87 96] N個數(shù)據(jù)需要多少趟排序？ 40 直接選擇排序算法 Void select （ list r， int n） { for( i=1。 j=n。 一趟選出的關鍵字最小的記錄稱為 “ 冠軍 ” ， 而 “ 亞軍 ” 是從與 “ 冠軍 ” 比較失敗的記錄中找出 。 交換后，子樹堆被破壞，繼續(xù)對不滿足堆性質(zhì)的子樹進行上述交換操作，直到葉子結點，堆被建成。此時可能會反復調(diào)整某些結點，直到 i=1為止，初建堆完成。 什么是堆 ? 寫出對應于序列 (10， 20， 7， 75， 41， 67， 3， 9， 30， 45) 的初始堆 (堆頂元素取最小值 )。 while（ ian amp。 k++。 } } //循環(huán)結束后是否所有記錄已存入 c中？ ………… } 61 有序序列的合并算法 Void merge（ list a， list b， list c） { ………… //循環(huán)結束后是否所有記錄已存入 c中？ while( ian ) { c[k]=a[i]。 j++。 63 分配排序 箱（桶）排序 箱排序也稱桶排序 算法思想： 設置若干個箱子 ， 依次掃描待排序記錄 ， 把關鍵字等于 K的記錄全部裝入第 k個箱子 （ 分配過程 ） ， 然后依次將各個非空的箱子首尾連接起來 （ 收集過程 ） 。 68 對關鍵字序 (278,109,063,930,589,184,505,269,008,083) 進行基數(shù)排序 930 083 063 184 505 008 278 269 589 109 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 69 930 083 063 184 505 008 278 269 589 109 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 收集 930 063 083 184 505 278 008 109 589 269 70 收集 930 063 083 184 505 278 008 109 589 269 505 930 184 083 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 063 278 008 109 589 269 收集 505 008 109 930 063 269 278 083 184 589 71 收集 505 008 109 930 063 269 178 083 184 589 008 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 505 083 589 109 178 930 063 269 184 收集 008 063 083 109 178 184 269 505 589 930 72 各種內(nèi)部排序算法的比較
教學課件相關推薦
鄂ICP備17016276號-1