第二十八講插入排序

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)系內(nèi)數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)網(wǎng)站：系內(nèi)數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)網(wǎng)站：00:8080/ds濱州學(xué)院計算機科學(xué)技術(shù)系第十章第十章 排序排序 插入排序插入排序濱州學(xué)院計算機科學(xué)技術(shù)系本講內(nèi)容本講內(nèi)容1.排序的相關(guān)概念及術(shù)語排序的相關(guān)概念及術(shù)語2.插入排序插入排序l直接插入排序直接插入排序l折半插入排序折半插入排序l希爾排序希爾排序濱州學(xué)院計算機科學(xué)技術(shù)系1. 排序的相關(guān)概念及術(shù)語排序的相關(guān)概念及術(shù)語l排序是計算機內(nèi)經(jīng)常進行的一種操作，排序是計算機內(nèi)經(jīng)常進行的一種操作，其目的是將一組其目的是將一組“無序無序”的記錄序列的記錄序列調(diào)整為調(diào)整為“有序有序”的記錄序列。的記錄序列。濱州學(xué)

2、院計算機科學(xué)技術(shù)系 一般情況下，一般情況下，假設(shè)含假設(shè)含n n個記錄的序列為個記錄的序列為 R1, R2, ， Rn 其相應(yīng)的關(guān)鍵字序列為其相應(yīng)的關(guān)鍵字序列為 K1, K2, ，Kn 這些關(guān)鍵字相互之間可以進行比較，即在這些關(guān)鍵字相互之間可以進行比較，即在它們之間存在著這樣一個關(guān)系它們之間存在著這樣一個關(guān)系 ： Kp1Kp2Kpn按此固有關(guān)系將上式記錄序列重新排列為按此固有關(guān)系將上式記錄序列重新排列為 Rp1, Rp2, ，Rpn 的操作稱作排序的操作稱作排序。1. 排序的相關(guān)概念及術(shù)語排序的相關(guān)概念及術(shù)語濱州學(xué)院計算機科學(xué)技術(shù)系l數(shù)據(jù)表數(shù)據(jù)表( (datalistdatalist):): 它

3、是待排序數(shù)據(jù)對象的有它是待排序數(shù)據(jù)對象的有限集合。限集合。l關(guān)鍵字關(guān)鍵字(key):(key): 通常數(shù)據(jù)對象有多個屬性域，通常數(shù)據(jù)對象有多個屬性域，即多個數(shù)據(jù)成員組成，其中有一個屬性域可用即多個數(shù)據(jù)成員組成，其中有一個屬性域可用來區(qū)分對象，作為排序依據(jù)。該域即為關(guān)鍵字。來區(qū)分對象，作為排序依據(jù)。該域即為關(guān)鍵字。每個數(shù)據(jù)表用哪個屬性域作為關(guān)鍵字，要視具每個數(shù)據(jù)表用哪個屬性域作為關(guān)鍵字，要視具體的應(yīng)用需要而定。即使是同一個表，在解決體的應(yīng)用需要而定。即使是同一個表，在解決不同問題的場合也可能取不同的域做關(guān)鍵字。不同問題的場合也可能取不同的域做關(guān)鍵字。1. 排序的相關(guān)概念及術(shù)語排序的相關(guān)概念及術(shù)語

4、濱州學(xué)院計算機科學(xué)技術(shù)系l主關(guān)鍵字主關(guān)鍵字: : 如果在數(shù)據(jù)表中各個對象的關(guān)鍵字互不如果在數(shù)據(jù)表中各個對象的關(guān)鍵字互不相同，這種關(guān)鍵碼即主關(guān)鍵字。按照主關(guān)鍵字進行排相同，這種關(guān)鍵碼即主關(guān)鍵字。按照主關(guān)鍵字進行排序，排序的結(jié)果是唯一的。序，排序的結(jié)果是唯一的。l次關(guān)鍵字次關(guān)鍵字: : 數(shù)據(jù)表中有些對象的關(guān)鍵字可能相同，數(shù)據(jù)表中有些對象的關(guān)鍵字可能相同，這種關(guān)鍵字稱為次關(guān)鍵字。按照次關(guān)鍵字進行排序，這種關(guān)鍵字稱為次關(guān)鍵字。按照次關(guān)鍵字進行排序，排序的結(jié)果可能不唯一。排序的結(jié)果可能不唯一。l排序算法的穩(wěn)定性排序算法的穩(wěn)定性: : 如果在對象序列中有兩個對象如果在對象序列中有兩個對象ri和和rj，它們

5、的，它們的關(guān)鍵字關(guān)鍵字 ki = kj，且在排序之前，對象，且在排序之前，對象ri排在排在rj前面前面。如果在排序之后，對象如果在排序之后，對象ri仍在對象仍在對象rj的前面，的前面，則則稱這個排序方法是穩(wěn)定的，否則稱這個排序方法是不穩(wěn)定稱這個排序方法是穩(wěn)定的，否則稱這個排序方法是不穩(wěn)定的。的。濱州學(xué)院計算機科學(xué)技術(shù)系 若若整個排序過程不需要訪問外存整個排序過程不需要訪問外存便能完成，便能完成，則稱此類排序問題則稱此類排序問題為內(nèi)部排序；為內(nèi)部排序； 反之，若參加排序的記錄數(shù)量很大，整個反之，若參加排序的記錄數(shù)量很大，整個序列的排序過程序列的排序過程不可能在內(nèi)存中完成不可能在內(nèi)存中完成，則稱此

6、，則稱此類排序問題類排序問題為外部排序為外部排序。1. 排序的相關(guān)概念及術(shù)語排序的相關(guān)概念及術(shù)語濱州學(xué)院計算機科學(xué)技術(shù)系內(nèi)部排序的方法內(nèi)部排序的方法內(nèi)部排序的過程是一個逐步擴大內(nèi)部排序的過程是一個逐步擴大記錄的有序序列長度的過程。記錄的有序序列長度的過程。經(jīng)過一趟排序經(jīng)過一趟排序有序序列區(qū)無 序 序 列 區(qū)有序序列區(qū)無 序 序 列 區(qū)濱州學(xué)院計算機科學(xué)技術(shù)系 基于不同的基于不同的“擴大擴大” 有序序列有序序列長度的方法，內(nèi)部排序方法大致可長度的方法，內(nèi)部排序方法大致可分下列幾種類型：分下列幾種類型：插入類插入類交換類交換類選擇類選擇類 歸并類歸并類其它方法其它方法濱州學(xué)院計算機科學(xué)技術(shù)系排序過

7、程中需進行的操作排序過程中需進行的操作l比較關(guān)鍵字大小比較關(guān)鍵字大小l移動記錄移動記錄l排序原則：盡量避免移動操作排序原則：盡量避免移動操作濱州學(xué)院計算機科學(xué)技術(shù)系有序序列有序序列R1.i-1Ri無序序列無序序列 Ri.n一趟直接插入排序的基本思想：一趟直接插入排序的基本思想：有序序列有序序列R1.i無序序列無序序列 Ri+1.n2. 插入排序插入排序濱州學(xué)院計算機科學(xué)技術(shù)系實現(xiàn)實現(xiàn)“一趟插入排序一趟插入排序”可分三步進可分三步進行：行：3將將Ri 插入插入(復(fù)制復(fù)制)到到Rj+1的位置上的位置上。2將將Rj+1.i-1中的所有中的所有記錄記錄均均后移后移 一個位置；一個位置；1在在R1.i-

8、1中中查找查找Ri的插入位置的插入位置j+1， R1.j.key Ri.key Rj+1.i-1.key；濱州學(xué)院計算機科學(xué)技術(shù)系直接插入排序直接插入排序（基于順序查找）（基于順序查找）2-路插入排序（折半排序的改進）不同的具體實現(xiàn)方法導(dǎo)致不同的算法描述不同的具體實現(xiàn)方法導(dǎo)致不同的算法描述折半插入排序折半插入排序（基于折半查找）（基于折半查找）希爾排序希爾排序（基于逐趟縮小增量）（基于逐趟縮小增量）濱州學(xué)院計算機科學(xué)技術(shù)系l利用利用 “順序查找順序查找”實現(xiàn)實現(xiàn)“在在R1.i-1中中查找查找Ri的插入位置的插入位置”2. 插入排序插入排序- 直接插入排序直接插入排序濱州學(xué)院計算機科學(xué)技術(shù)系從從

9、Ri-1起向前進行順序查找，起向前進行順序查找， 監(jiān)視哨設(shè)置在監(jiān)視哨設(shè)置在R0；R0 = Ri; / 設(shè)置“哨兵”循環(huán)結(jié)束表明循環(huán)結(jié)束表明Ri的插入位置為的插入位置為 j +1R0jRifor (j=i-1; R0Rj; -j); / 從后往前找j=i-1插入位置插入位置濱州學(xué)院計算機科學(xué)技術(shù)系 對于在查找過程中找到的那些關(guān)鍵對于在查找過程中找到的那些關(guān)鍵字不小于字不小于Ri.key的記錄，并在查找的的記錄，并在查找的同時實現(xiàn)記錄向后移動；同時實現(xiàn)記錄向后移動；for (j=i-1; R0Rj; -j); Rj+1 = Rj；R0jRij= i-1上述循環(huán)結(jié)束后可以直接進行上述循環(huán)結(jié)束后可以直

10、接進行“插入插入”插入位置插入位置濱州學(xué)院計算機科學(xué)技術(shù)系令令 i = 2，3，, n, 實現(xiàn)整個序列的排序。實現(xiàn)整個序列的排序。for ( i=2; i=n; +i ) if (RiRi-1) 在 R1.i-1中查找Ri的插入位置; 插入Ri ; 濱州學(xué)院計算機科學(xué)技術(shù)系void InsertionSort ( int &L, int n) / 對順序表 L 作直接插入排序。 for ( i=2; i=n; +i ) if (L i Li-1) / InsertSortL0 = Li; / 復(fù)制為監(jiān)視哨for ( j=i-1; L0 Lj; - j ) Lj+1 = Lj; / 記錄

11、后移Lj+1 = L0; / 插入到正確位置濱州學(xué)院計算機科學(xué)技術(shù)系各趟排序結(jié)果各趟排序結(jié)果0 1 2 3 4 5 60 1 2 3 4 5 6 temp250 1 2 3 4 5 6 temp49濱州學(xué)院計算機科學(xué)技術(shù)系25*0 1 2 3 4 5 60 1 2 3 4 5 6 temp160 1 2 3 4 5 6 temp0825*1608濱州學(xué)院計算機科學(xué)技術(shù)系16490 1 2 3 4 50 1 2 3 4 5 6 temp0 1 2 3 4 5 6 temp1616濱州學(xué)院計算機科學(xué)技術(shù)系2525*0 1 2 3 4 5 60 1 2 3 4 5 6 temp0 1 2 3 4 5

12、 6 temp21161616濱州學(xué)院計算機科學(xué)技術(shù)系最好的情況（關(guān)鍵字在記錄序列中順序有序）：最好的情況（關(guān)鍵字在記錄序列中順序有序）：“比較”的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：“比較”的次數(shù)：112nni02) 1)(4() 1(2nnini“移動”的次數(shù)：“移動”的次數(shù)：2) 1)(4() 1(2nnini2i直接插入排序的時間分析：直接插入排序的時間分析：濱州學(xué)院計算機科學(xué)技術(shù)系 因為 R1.i-1 是一個按關(guān)鍵字有序的有序序列，則可以利用折半查找折半查找實現(xiàn)“在R1.i-1中查找查找Ri的插入位置”，如此實現(xiàn)的插入排序為折半插

13、折半插入入排序。2. 插入排序插入排序- 折半插入排序折半插入排序濱州學(xué)院計算機科學(xué)技術(shù)系void BiInsertionSort ( int &L ,int n ) / BiInsertionSort在在 L.r1.i-1中折半查找插入位置；中折半查找插入位置；for ( i=2; i=high+1; -j ) Lj+1 = Lj; / 記錄后移Lhigh+1 = L0; / 插入濱州學(xué)院計算機科學(xué)技術(shù)系low = 1; high = i-1;while (low=high) m = (low+high)/2; / 折半if (L0 Lm) high = m-1; / 插入點在低半?yún)^(qū)

14、else low = m+1; / 插入點在高半?yún)^(qū)濱州學(xué)院計算機科學(xué)技術(shù)系希爾排序方法又稱為縮小增量的插入排序?；柵判蚍椒ㄓ址Q為縮小增量的插入排序?；舅枷耄簩Υ庞涗浶蛄邢茸鞅舅枷耄簩Υ庞涗浶蛄邢茸鳌昂暧^宏觀”調(diào)整，再調(diào)整，再作作“微觀微觀”調(diào)整。所謂調(diào)整。所謂“宏觀宏觀”調(diào)整，指的是，調(diào)整，指的是，“跳躍式跳躍式”的插入排序。的插入排序。 設(shè)待排序?qū)ο笮蛄杏性O(shè)待排序?qū)ο笮蛄杏衝個對象，首先取一個整個對象，首先取一個整數(shù)數(shù) d =1) for ( i=dk+1; i=n; +i ) if ( Li0&(L0Lj); j-=dk) Lj+dk = Lj; / 記錄后移，查找插入位置記錄后移，查找插入位置 Lj+dk = L0; / 插入