數(shù)據(jù)結(jié)構(gòu) 第十章課件

1、第10章內(nèi)部排序，1，PPT學(xué)習(xí)通信，10.2插入排序，10.1概要，10.3快速排序，10.4選擇排序，10.5合并排序，10.6基數(shù)排序，10.7各種內(nèi)部排序方法的比較研究，2，PPT學(xué)習(xí)通信， 排序是計算機(jī)內(nèi)頻繁進(jìn)行的操作，其目的是將“無序”記錄序列調(diào)整為“有序”記錄序列。 舉例來說，可調(diào)整以下關(guān)鍵字序列52、49、80、36、14、58、61、23、97、75以使14、23、36、49、52、58、61、75、80、97、3、PPT學(xué)習(xí)通信，且可生成n個記錄K2、Kn )、和這些關(guān)鍵字可以相互比較，即，它們之間存在非減少關(guān)系Kp1Kp2Kpn，將根據(jù)該關(guān)系將記錄序列重新排序(Rp1、R

2、p2、以及Rpn )的操作稱為排序。排序的形式化定義、4、PPT學(xué)習(xí)通信、內(nèi)部排序和外部排序、要排序的記錄全部存儲在內(nèi)存中，如果整個排序過程不需要訪問外部內(nèi)存，則這種排序問題稱為內(nèi)部排序，要排序的記錄數(shù)量多， 如果無法一次將所有記錄存儲在內(nèi)存中，則在排序過程中還需要訪問外部時，這種排序問題稱為外部排序。 5、PPT學(xué)習(xí)了交流、排序方法的穩(wěn)定性，在一種排序方法中，排序后具有相同關(guān)鍵字的記錄如果保持原來的相對順序就很穩(wěn)定，否則稱為不穩(wěn)定。 例如：成績不升順序排序，6、PPT學(xué)習(xí)溝通，排序方法的穩(wěn)定性由方法本身決定。 對于不穩(wěn)定的排序方法，與其描述形式無關(guān)，總是舉出了不穩(wěn)定的實例，相反，對于穩(wěn)定的排

3、序方法，總是找到不穩(wěn)定的描述形式。 舉重比賽中的選手成績表，在排名前體重增加有秩序，在排名后成績沒有上升。 必須采用穩(wěn)定的排序方法，7、PPT學(xué)習(xí)交流、內(nèi)部排序的方法，內(nèi)部排序的過程是逐漸擴(kuò)大記錄秩序長度的過程。一次排序、排序區(qū)域、排序區(qū)域、排序區(qū)域、排序區(qū)域、8、PPT學(xué)習(xí)通信，基于不同的“放大”排序的長度的方法，內(nèi)部的排序方法大致分為以下類型：插入類、交換類、選擇類、合并類、其他PPT學(xué)習(xí)通信，1 .通過對插入類、無序子序列中的一個或幾個記錄進(jìn)行“插入”，增加記錄的排序子序列的長度。 10、PPT學(xué)習(xí)交流，2 .交換類，通過“交換”無序序列的記錄，獲得其中關(guān)鍵字最小或最大的記錄，添加到秩序

4、子序列，增加記錄秩序子序列的長度。 11、PPT學(xué)習(xí)通信，3 .選擇類，從記錄的無序子序列中選擇關(guān)鍵字最小或最大的記錄，添加到有序子序列中，增加記錄的有序子序列的長度。 12、PPT學(xué)習(xí)通信，4 .合并類通過“合并”兩個或多個記錄秩序子序列，逐漸增加記錄秩序序列的長度。 5 .其他方法、13、PPT學(xué)習(xí)交流、存儲方式、排序操作通?？梢酝ㄟ^以下存儲結(jié)構(gòu)進(jìn)行：順序表、鏈表(線性鏈表、靜態(tài)鏈表)、索引順序表、14、PPT學(xué)習(xí)交流、#define MAXSIZE 20 /順序表的最大長度的假設(shè)值type /請將關(guān)鍵字類型設(shè)定為整數(shù)typedef struct KeyType key關(guān)鍵字字段InfoT

5、ype otherinfo； /其他域RcdType； /記錄類型typedef struct RcdType rMAXSIZE 1； 用作/r0空閑或監(jiān)視哨單元int length順序表長度SqList； /順序表類型、要排序記錄的數(shù)據(jù)類型、15、PPT學(xué)習(xí)通信、10.2插入排序、16、PPT學(xué)習(xí)通信、順序序列R1.i-1、Ri、順序序列Ri.n、順序序列R1.i、順序序列Ri 1.n、17將Rj 1.i-1中的所有記錄向后移動一個位置，R1.i-1中的Ri插入位置，R1.j.key Ri.key Rj 1.i-1.key； 18、PPT學(xué)習(xí)交流，直接插入排名(基于逐次搜索)，不同的具體實現(xiàn)

6、方式導(dǎo)致不同的算法描述，插入一半排名(基于一半搜索)，希爾排名(基于逐次縮小增量)，19、PPT L.ri=L.ri-1； for(j=i-2； LT(L.r0.key，L.rj.key) -j ) L.rj 1=L.rj； L.rj 1=L.r0； 在順序序列r1.i-1中查找ri的插入位置時，直接利用“順序檢索”來實現(xiàn)。 10.2.1直接插入排名，20、PPT學(xué)習(xí)通信、voidinsertsort、算法10.1 (p265 )、21、PPT學(xué)習(xí)通信i=2(38)(38)65977627、I=3(38 ) (38 ) (386597 ) 7627，I=5(76 ) (386597 ) 132

7、7 I=6(13 ) (1338 49 65 7697 ) 2749，i=7 (27)(13 27 38 49 65 76 97)49，I=8(49)(132738496597)97 )，監(jiān)視(1)“比較”序列中的兩個關(guān)鍵字的大小、23、PPT學(xué)習(xí)通信、直接插入排序性能分析、最佳情況(文件初始狀態(tài)順序):最大比較次數(shù)：最壞情況(文件初始狀態(tài)順序):最小移動次數(shù)：最小移動次數(shù)：最大移動次數(shù)：24， 由于PPT學(xué)習(xí)通信r1.i-1是關(guān)鍵字順序，所以實現(xiàn)為“用r1.i-1查找ri的插入位置”的插入排序是半插入排序。10.2.2折半插入排名、25、PPT學(xué)習(xí)通信、voidsbinsertsort (s

8、qlist/for/binsertsort或high 1、算法10.2 (p267 )、26、PPT學(xué)習(xí)通信low，m，high，14 36 49 52 58 61 80，23 97 75，I，low，high，m，low，例如：還有：插入位置，插入位置，L.r，L.r，任何情況下，low=h 27、PPT學(xué)習(xí)交流，10.2.3希爾排行(縮小階段排行)，基本思想：對排行進(jìn)行“宏觀”調(diào)整，再進(jìn)行“微觀”調(diào)整。 把記錄“跳躍”后“一步一步地移動”。 具體來說： 28、PPT學(xué)習(xí)交流，將記錄序列分成幾個子序列，并對各自的子序列進(jìn)行插入排序。 的雙曲正切值。 其中，d稱為遞增，其值在排序中從大到小依次

9、變小，直到最后的排序變?yōu)?。 例如，將n個記錄分成d個子序列： R1，R1 d，R1 2d，R1 kd R2，R2 d，R2 kd Rd，R2 d，R3d，Rkd，R(k 1)d，29，PPT來學(xué)習(xí)通信的例子：(增加序列： ) 3-1 )初始關(guān)鍵字： 4938659761327495504，4913，一次排序結(jié)果： 132749504659776，3827，6549，9755，7604，135538，270465， 4997二次排序結(jié)果： 13 04 49 38 27 49 55 65 97 76，三次排序結(jié)果： 041327384956597，30，PPT學(xué)習(xí)交流，選擇一個增量分配序列nd1d2dt=1，其中n文件的長度； di (1it )增量(正整數(shù)) t增加個數(shù)、排序回合數(shù)。 將文檔按d1分組，將相互離開d1的記錄分成組，在組內(nèi)用直接插入法進(jìn)行排序。 按d2、dt重復(fù)上述分組和排序作業(yè)。 31、PPT學(xué)習(xí)通信、voidshellinsert (sqlist/if/shell