數(shù) 據(jù) 結(jié) 構(gòu),10.1 概述,10.2 插入類排序,10.4 選擇類排序,第10章 內(nèi)部排序,10.3 交換類排序,10.5 歸并排序,10.6 基數(shù)排序,10.7 各種排序方法的總和比較,1,數(shù) 據(jù) 結(jié) 構(gòu),10.1 概述,第10章 內(nèi)部排序,排序是計算機內(nèi)經(jīng)常進行的一種操作，其目的是將 一組“無序”的記錄序列調(diào)整為“有序”的記錄序列。,例如：將下列關(guān)鍵字序列,52, 49, 80, 36, 14, 58, 61, 23, 97, 75,調(diào)整為,14, 23, 36, 49, 52, 58, 61, 75, 80, 97,2,數(shù) 據(jù) 結(jié) 構(gòu),10.1 概述,第10章 內(nèi)部排序,排序的定義： 假設(shè)含n個記錄的序列為 a0, a1, ， an-1 其相應(yīng)的關(guān)鍵字序列為 K0, K1, ，Kn-1 ,這些關(guān)鍵字相互之間可以進行比較，即在 它們之間存在著這樣一個關(guān)系 ： Kp0Kp1Kpn-1,按此固有關(guān)系將上式記錄序列重新排列為 ap0, ap1, ，apn-1 的操作稱作排序。,3,數(shù) 據(jù) 結(jié) 構(gòu),10.1 概述,第10章 內(nèi)部排序,排序,內(nèi)部排序,外部排序,整個排序過程不需要訪問外存便能完成。,若參加排序的記錄數(shù)量很大，整個序列的排序過程不可能在內(nèi)存中完成。,穩(wěn)定排序,不穩(wěn)定排序,排序,相同關(guān)鍵字的領(lǐng)先關(guān)系在排序過程中未發(fā)生變化。,相同關(guān)鍵字的領(lǐng)先關(guān)系在排序過程中發(fā)生變化。,4,數(shù) 據(jù) 結(jié) 構(gòu),10.1 概述,第10章 內(nèi)部排序,內(nèi)部排序的過程： 是一個逐步擴大記錄的有序序列長度的過程。,經(jīng)過一趟排序,有序序列區(qū),無 序 序 列 區(qū),有序序列區(qū),無 序 序 列 區(qū),內(nèi)部排序的方法,5,數(shù) 據(jù) 結(jié) 構(gòu),10.1 概述,第10章 內(nèi)部排序,基于不同的“擴大” 有序序列長度的方法，內(nèi)部排序方法大致可分下列幾種類型：,插入類,交換類,選擇類,歸并類,其它方法,6,數(shù) 據(jù) 結(jié) 構(gòu),10.1 概述,第10章 內(nèi)部排序,待排記錄的數(shù)據(jù)類型定義如下:,#define MAXSIZE 1000 typedef int KeyType; typedef struct KeyType key; OtherType other_data; RecordType; typedef struct RcdType rMAXSIZE+1; int length; SqList;,7,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,將無序子序列中的一個或幾個記錄“插入”到有 序序列中，從而增加記錄的有序子序列的長度。,有序序列a1.i-1,ai,無序序列 ai.n-1,一趟直接插入排序的基本思想：,有序序列a1.i,無序序列 ai+1.n-1,8,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,實現(xiàn)“一趟插入排序”可分三步進行：,3將ai 插入(復(fù)制)到aj+1的位置上。,2將aj+1.i中的所有記錄均后移一個位置；,1在a1.i-1中查找ai的插入位置， a1.j.key ai.key < aj+1.i.key；,9,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,直接插入排序（基于順序查找）,希爾排序（基于逐趟縮小增量）,不同的具體實現(xiàn)方法導(dǎo)致不同的算法描述,折半插入排序（基于折半查找）,表插入排序（基于鏈表存儲）,10,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,直接插入排序,利用順序查找實現(xiàn)在r1.i-1中查找ri的插入位置,48,62,35,77,55,14,35,98,第1 趟,48,62,r0,62,35,2,35,48,62,3,77,77,4,55,55,62,77,5,14,14,35,48,55,62,77,6,35,35,48,55,62,77,7,98,98,從ri-1起向前進行順序查找，監(jiān)視哨設(shè)置在r0；,r0 = ri;,循環(huán)結(jié)束表明ri的插入位置為 j +1,r0,j,ri,for (j=i-1; r0.key<rj.key; -j);,j=i-1,插入位置,11,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,對于在查找過程中找到的那些關(guān)鍵字不小于ri.key的記錄，并在查找的同時實現(xiàn)記錄向后移動；,for (j=i-1; r0.key<rj.key; -j); rj+1 = rj；,上述循環(huán)結(jié)束后可以直接進行“插入” rj+1 = r0；,r0,j,ri,j=i-1,插入位置,直接插入排序,12,令 i = 2，3，, n, 實現(xiàn)整個序列的排序。,for ( i=2; i<=n; +i ) if (ri.key<ri-1.key) 在 r1.i-1中查找ri的插入位置; 插入ri ; ,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,直接插入排序,13,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,直接插入排序,void InsertionSort ( SqList +i ) if (L.ri.key < L.ri-1.key) ,L.r0 = L.ri; for ( j=i-1; L.r0.key < L.rj.key; - j ) L.rj+1 = L.rj; L.rj+1 = L.r0;,14,內(nèi)部排序的時間分析：,實現(xiàn)內(nèi)部排序的基本操作有兩個：,（2）“移動”記錄。,（1）“比較”序列中兩個關(guān)鍵字的大??；,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,直接插入排序,15,對 于 直 接 插 入 排 序,最好的情況 （關(guān)鍵字在記錄序列中順序有序）：,“比較”的次數(shù)：,最壞的情況 （關(guān)鍵字在記錄序列中逆序有序）：,“比較”的次數(shù)：,0,“移動”的次數(shù)：,“移動”的次數(shù)：,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,直接插入排序,16,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,折半插入排序,因為 r1.i-1 是一個按關(guān)鍵字有序的有序序列，則 可以利用折半查找實現(xiàn)“在r1.i-1中查找ri的插 入位置”，如此實現(xiàn)的插入排序為折半插入排序。,i,low,high,m,high,m,high,m,low,例如:,插入 位置,L.r,17,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,折半插入排序,void BiInsertionSort ( SqList i<=L.length; +i ) ,L.r0 = L.ri;,for ( j=i-1; j=low; -j ) L.rj+1 = L.rj;,L.rlow = L.r0;,18,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,折半插入排序,low = 1; high = i-1; while (low<=high) ,m= (low+high)/2;,if (L.r0.key < L.rm.key) high = m-1; else low = m+1;,在 L.r1.i-1中折半查找插入位置；,19,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,希爾排序,基本思想： 對待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。,所謂“宏觀”調(diào)整，指的是，“跳躍式”的插入排序。,（又稱縮小增量排序）,20,將記錄序列分成若干子序列，分 別對每個子序列進行插入排序。,其中，d 稱為增量，它的值在排序過程中從 大到小逐漸縮小，直至最后一趟排序減為1。,例如：將 n 個記錄分成 d 個子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d ,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,希爾排序,（又稱縮小增量排序）,具體做法為：,21,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,希爾排序,（又稱縮小增量排序）,d1=4,17,55,05,13,d2=2,05,13,46,94,d3=1,13,17,70,94,22,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,希爾排序,（又稱縮小增量排序）,void ShellInsert ( SqList ,23,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,希爾排序,（又稱縮小增量排序）,void ShellSort (SqList ,24,數(shù) 據(jù) 結(jié) 構(gòu),10.3 交換類排序,第10章 內(nèi)部排序,基本思想：,通過交換逆序元素進行排序的方法。,冒泡排序（相鄰比逆法）,快速排序,通過“交換”無序序列中的記錄從而得到其中關(guān)鍵字 最小或最大的記錄，并將它加入到有序子序列中， 以此方法增加記錄的有序子序列的長度。,25,數(shù) 據(jù) 結(jié) 構(gòu),10.3 交換類排序,第10章 內(nèi)部排序,冒泡排序（相鄰比逆法）,思想：在掃描的過程中順次比較相鄰的兩個 元素的大小，若逆序就交換位置。,第1趟,35,62,55,77,14,77,35,77,22,98,40,98,9次,第2趟,77,35,48,55,14,35,62,22,40,8次,第n-1趟,排序結(jié)束,n-i次,第i 趟,26,數(shù) 據(jù) 結(jié) 構(gòu),10.3 交換類排序,第10章 內(nèi)部排序,冒泡排序（相鄰比逆法）,void BubbleSort(RecordType r ,int length) n=length; for(i=1; irj+1.key) x=aj;rj=rj+1;rj+1=x; ,27,數(shù) 據(jù) 結(jié) 構(gòu),10.3 交換類排序,第10章 內(nèi)部排序,冒泡排序,時間分析:,28,數(shù) 據(jù) 結(jié) 構(gòu),10.3 交換類排序,第10章 內(nèi)部排序,快速排序,改進冒泡排序中一次交換只能消除一個逆序 的缺點，即實現(xiàn)一次交換消除多個逆序。,思想： 找一個記錄，以它的關(guān)鍵字作為“樞軸”，凡其關(guān)鍵字 小于樞軸的記錄均移動至該記錄之前，凡其關(guān)鍵字 大于樞軸的記錄均移動至該記錄之后。 即對無序的記錄序列進行“一次劃分”，,之后分別對分割所得兩個子序列“遞歸”進行快速排序。,29,數(shù) 據(jù) 結(jié) 構(gòu),10.3 交換類排序,第10章 內(nèi)部排序,快速排序,一次劃分（一趟快速排序）,r0,48,low,high,high,35,low,62,high,14,low,low,77,high,high,48,30,數(shù) 據(jù) 結(jié) 構(gòu),10.3 交換類排序,第10章 內(nèi)部排序,快速排序,int QKpass (RecordType r , int low, int high) ,r0 = rlow;,while (low<high) ,while(low= r0.key) - high;,rlow = rhigh;,while (low<high ,rhigh = rlow;,rlow = r0; return low;,一趟快速排序算法,31,void QKSort(RecordType r ,int low,int high) r0=rlow; if(low<high) pos=QKpass(r,low,high); QKSort(r,low,pos-1); QkSort(r,pos+1,high); ,數(shù) 據(jù) 結(jié) 構(gòu),10.3 交換類排序,第10章 內(nèi)部排序,快速排序,算法,32,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,從記錄的無序子序列中“選擇”關(guān)鍵字最小或 最大的記錄，并將它加入到有序子序列中， 以此方法增加記錄的有序子序列的長度。,簡單選擇排序,堆排序,樹型選擇排序,33,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,簡單選擇排序,i,第 1 趟,k,j,j,k,j,j,j,k,j,j,14,48,2,i,k,j,35,62,3,35,62,4,48,77,5,55,6,62,77,7,77,8,98,void SelectSort(RecordType r ,int n) n=length; for(i=1;i<=n-1;i+) k=i; for(j=i+1;j<=n; +j) if(rj.key<rk.key) k=j; if(k!=i) x=ri;ri=rk;rk=x; ,34,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,樹型選擇排序,是一種按錦標賽的思想進行排序的方法。,49,38,27,65,97,76,49,13,38,65,13,27,38,13,13,76,13,27,27,27,49,49,38,38,49,49,49,49,65,49,49,76,65,65,97,97,76,76,97,97,35,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,堆排序,對樹型排序的進一步改進。,堆是滿足下列性質(zhì)的數(shù)列r1, r2, ，rn：,或,堆的定義:,12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49,例如:,是小頂堆,12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49,不是堆,(小頂堆),(大頂堆),36,ri,r2i,r2i+1,若將該數(shù)列視作完全二叉樹，則 r2i 是 ri 的左孩子；r2i+1 是 ri 的右孩子。,例如:,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,堆排序,12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49,12,36,27,65,40,34,98,81,73,55,49,14,14,是小頂堆,不,37,堆排序即是利用堆的特性對記錄序列進行排序。,例如：,建大頂堆, 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 , 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 ,交換 98 和 12,重新調(diào)整為大頂堆, 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 , 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 ,經(jīng)過篩選,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,堆排序,38,1、如何由一個無序序列“建初堆”？,堆排序的兩個問題:,2、輸出堆頂后，如何“篩選”？,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,堆排序,所謂“篩選”指的是，對一棵左/右子樹均為堆的完全 二叉樹，“調(diào)整”根結(jié)點使整個二叉樹也成為一個堆。,39,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,堆排序,48,98,77,62,48,40,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,堆排序,例如：, 48, 62, 35, 77, 55, 14, 35, 98,48,62,35,77,55,14,35,98,顯然不是一個堆,調(diào)整,如何建初堆？,41,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,堆排序,98,77,98,77,62,98,77,62,48,42,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,堆排序,98,48,98,77,62,48,77,35,77,62,55,35,62,62,14,55,48,14,55,55,35,48,35,48,48,14,35,14,35,35,35,35,35,14,14,43,時間復(fù)雜度分析,1. 對深度為k的堆，“篩選”所需進行的關(guān)鍵字 比較的次數(shù)至多為2(k-1)；,3. 調(diào)整“堆頂”n-1次，總共進行的關(guān)鍵字比較的次數(shù) 不超過 2(log2(n-1)+log2(n-2)+ +log22)<2n(log2n),因此，堆排序的時間復(fù)雜度為O(nlogn)。,2. 對n個關(guān)鍵字，建成深度為h(=log2n+1)的堆， 所需進行的關(guān)鍵字比較的次數(shù)至多4n；,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,堆排序,44,數(shù) 據(jù) 結(jié) 構(gòu),10.5 歸并類排序,第10章 內(nèi)部排序,通過“歸并”兩個或兩個以上的記錄有序 子序列，逐步增加記錄有序序列的長度。,在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個位置相鄰的記錄有序子序列,歸并為一個記錄的有序序列。,有 序 序 列 rl.n,有序子序列 rl.m,有序子序列 rm+1.n,45,數(shù) 據(jù) 結(jié) 構(gòu),10.5 歸并類排序,第10章 內(nèi)部排序,例如：19，13，05，27，01，26，31，16,13，19,05，27,01，26,16 ，31,05，13，19，27,01，16，26，31,01，05，13，16，19，26，27，31,很少進行內(nèi)排序，主要用于外排序。,46,數(shù) 據(jù) 結(jié) 構(gòu),10.6 基數(shù)排序,第10章 內(nèi)部排序,主要利用分配和收集兩種基本操作。 典型的就是基數(shù)類排序。,多關(guān)鍵字的排序,鏈式基數(shù)排序,47,數(shù) 據(jù) 結(jié) 構(gòu),10.6 基數(shù)排序,第10章 內(nèi)部排序,多關(guān)鍵字的排序,最低位優(yōu)先LSD法,最高位優(yōu)先MSD法,先對K0進行排序，并按 K0 的不同值將記錄序列分 成若干子序列之后，分別對 K1 進行排序，.， 依次類推，直至最后對最次位關(guān)鍵字排序完成為止。,先對 Kd-1 進行排序，然后對 Kd-2 進行排序，依 次類推，直至對最主位關(guān)鍵字 K0 排序完成為止。,排序過程中不需要根據(jù) “前一個” 關(guān)鍵字的排序結(jié)果， 將記錄序列分割成若干個(“前一個”關(guān)鍵字不同的)子 序列。,48,例如:學生記錄含三個關(guān)鍵字:系別、班號和 班內(nèi)的序列號，其中以系別為最主位關(guān)鍵字。,1,2,15,2,3,18,3,1,20,2,1,20,3,2,30,3,1,20,2,1,20,1,2,15,3,2,30,2,3,18,1,2,15,2,1,20,2,3,18,3,1,20,3,2,30,LSD的排序過程如下:,數(shù) 據(jù) 結(jié) 構(gòu),10.6 基數(shù)排序,第10章 內(nèi)部排序,多關(guān)鍵字的排序,49,數(shù) 據(jù) 結(jié) 構(gòu),10.6 基數(shù)排序,第10章 內(nèi)部排序,鏈式基數(shù)排序,假如多關(guān)鍵字的記錄序列中，每個關(guān)鍵字的取值范 圍相同，則按LSD法進行排序時，可以采用“分配-收 集”的方法，其好處是不需要進行關(guān)鍵字間的比較。,對于數(shù)字型或字符型的單關(guān)鍵字，可以看成是由多個 數(shù)位或多個字符構(gòu)成的多關(guān)鍵字，此時可以采用這種 “分配-收集”的辦法進行排序，稱作基數(shù)排序法。,50,例如：對下列這組關(guān)鍵字 209, 386, 768, 185, 247, 606, 230, 834, 539 ,首先按其 “個位數(shù)” 取值分別為 0, 1, , 9 “分配” 成 10 組，之后按從 0 至 9 的順序?qū)?它們 “收集” 在一起；,然后按其 “十位數(shù)” 取值分別為 0, 1, , 9 “分配” 成 10 組，之后再按從 0 至 9 的順序?qū)⑺鼈儭笆占痹谝黄穑?最后按其“百位數(shù)”重復(fù)一遍上述操作。,數(shù) 據(jù) 結(jié) 構(gòu),10.6 基數(shù)排序,第10章 內(nèi)部排序,鏈式基數(shù)排序,51,在計算機上實現(xiàn)基數(shù)排序時，為減少所需輔助存儲空間，應(yīng)采用鏈表作存儲結(jié)構(gòu)，即鏈式基數(shù)排序。 具體作法為：,待排序記錄以指針相鏈，構(gòu)成一個鏈表；,“分配” 時，按當前“關(guān)鍵字位”所取值，將記 錄分配到不同的 “鏈隊列” 中，每個隊列中記 錄的 “關(guān)鍵字位” 相同；,“收集”時，按當前關(guān)鍵字位取值從小到大將 各隊列首尾相鏈成一個鏈表;,對每個關(guān)鍵字位均重復(fù) 2) 和 3) 兩步。,數(shù) 據(jù) 結(jié) 構(gòu),10.6 基數(shù)排序,第10章 內(nèi)部排序,鏈式基數(shù)排序,52,例如：,p369367167239237138230139,進行第一次分配,進行第一次收集,f0 r0,f7 r7,f8 r8,f9 r9,p230,230,367,167,237,367167237,138,369239139,369,239,139,138,數(shù) 據(jù) 結(jié) 構(gòu),10.6 基數(shù)排序,第10章 內(nèi)部排序,鏈式基數(shù)排序,53,數(shù) 據(jù) 結(jié) 構(gòu),10.6 基數(shù)排序,第10章 內(nèi)部排序,鏈式基數(shù)排序,進行第二次分配,p230237138239139,f3 r3,f6 r6,230,237,138,239,139,367,167,369,367167369,進行第二次收集,54,f1 r1,進行第三次分配,f2 r2,f3 r3,138,139,167,230,237,239,367,369,數(shù) 據(jù) 結(jié) 構(gòu),10.6 基數(shù)排序,第10章 內(nèi)部排序,鏈式基數(shù)排序,進行第三次收集之后便得到記錄的有序序列,55,數(shù) 據(jù) 結(jié) 構(gòu),10.7各種排序方法的綜合比較,第10章 內(nèi)部排序,各種排序方法的性能比較,56,數(shù) 據(jù) 結(jié) 構(gòu),10.7各種排序方法的綜合比較,第10章 內(nèi)部排序,各種排序方法的穩(wěn)定性比較,57,數(shù) 據(jù) 結(jié) 構(gòu),10.7各種排序方法的綜合比較,第10章 內(nèi)部排序,有效結(jié)論：,簡單排序法一般只用于n較小的情況；,當序列中的記錄“基本有序”時，直接插入排序最佳；,就平均時間性能而言，快速排序是最好的；,當n值很大而關(guān)鍵字的位數(shù)d較小時，選擇基數(shù)排序；,可將簡單排序與性能較好的排序方法結(jié)合使用。,總之，應(yīng)具體情況具體對待。,58,此課件下載可自行編輯修改，供參考！ 感謝您的支持，我們努力做得更好！,59,