計(jì)算機(jī)軟件基礎(chǔ)

1、計(jì)算機(jī)軟件基礎(chǔ)計(jì)算機(jī)軟件基礎(chǔ)The software basic The software basic of computerof computer主講：李尊朝主講：李尊朝西安交通大學(xué)西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心第第7單元單元排序排序教學(xué)目標(biāo) 了解有關(guān)排序的基本概念排序的典型算法教學(xué)要求通過(guò)本單元的學(xué)習(xí)，了解、掌握有關(guān)排序的： 基本概念排序、排序分類、算法穩(wěn)定性 典型的排序算法插入排序、選擇排序、交換排序快速排序、歸并排序一、基本概念 將記錄按關(guān)鍵字遞增(遞減)的次序排列起來(lái),形成新的有序序列,稱為排序。 設(shè)n個(gè)記錄的序列為R1,R2,Rn,其相應(yīng)關(guān)鍵字序列為K1,K2,K

2、n,需確定一種排序P1,P2,Pn,使其相應(yīng)的關(guān)鍵字滿足遞增(升序),或遞減(降序)的關(guān)系: Kp1 Kp2 . Kpn 或 Kp1 Kp2 . Kpn排序分類 根據(jù)排序元素所在位置的不同,排序分: 內(nèi)排序和外排序。內(nèi)排序 在排序過(guò)程中，所有元素調(diào)到內(nèi)存中進(jìn)行的排序，稱為內(nèi)排序。內(nèi)排序效率用比較次數(shù)來(lái)衡量。外排序 在數(shù)據(jù)量大的情況下，不能將全部元素存放在內(nèi)存，還要使用外存。外排序用讀/寫外存的次數(shù)來(lái)衡量其效率。 若待排序的序列中，存在多個(gè)具有相同關(guān)鍵字的記錄，經(jīng)過(guò)排序，這些記錄的相對(duì)次序保持不變，則稱該算法是穩(wěn)定的； 若經(jīng)排序后，記錄的相對(duì)次序發(fā)生了改變，則稱該算法是不穩(wěn)定的。排序算法的穩(wěn)定性

3、二、典型排序算法 插入排序 選擇排序 交換排序 快速排序 歸并排序插入排序（算法3-5） 基本思想： 將n個(gè)元素的數(shù)列分為已有序和無(wú)序兩個(gè)部分。 a1，a2，a3，a4，,an a1(1)，a2(1)，a3(1)，a4(1) ,an(1) . a1(n-1)，a2(n-1) ，, an(n-1) 每次處理就是將無(wú)序數(shù)列的第一個(gè)元素與有序數(shù)列的元素從后往前逐個(gè)進(jìn)行比較,找出插入位置,將該元素插入到有序數(shù)列的合適位置中。有序有序 無(wú)序無(wú)序插入排序算法步驟Step1 從有序數(shù)列a1和無(wú)序數(shù)列a2,a3,an開(kāi)始進(jìn)行排序;Step2 處理第i個(gè)元素時(shí)(i=2,3,n),數(shù)列 a1,a2,ai-1是已有

4、序的,而數(shù)列ai,ai+1,an是無(wú)序的。用ai與ai-1、a i-2,a1進(jìn)行比較,找出合適的位置將ai插入。Step3 重復(fù)Step2，共進(jìn)行n-1的插入處理，數(shù)列全部有序。插入排序算法 insert_sort(item , n ) int item ,n ; int i，j，t ; for（i=1；i=0 & t itemj) itemj+1=itemj; j- - ; itemj+1=t; 算法討論 插入算法比較次數(shù)和交換次數(shù)約為 n2/2，因此，其時(shí)間復(fù)雜度為O（ n2 ）。 該算法是穩(wěn)定的。選擇排序（算法3-6） 基本思想：每次從待排序的記錄中選出關(guān)鍵字最?。ɑ蜃畲螅┑挠涗?/p>

5、，順序放在已有序的記錄序列的最后（或最前）面，直到全部數(shù)列有序。 a1，a2，a3，a4，,an a1(1)，a2(1)，a3(1)，a4(1),an(1) . a1(n-1)，a2(n-1) ，, an(n-1)有序有序 無(wú)序無(wú)序選擇排序舉例 設(shè)有數(shù)列 18，12，10，12，30，16 初始狀態(tài)：，18，12，10，12，30，16 比較次數(shù) i=1 10，12， 18， 12，30，16 5 i=2 10，12，18， 12，30，16 4 i=3 10，12，12，18，30，16 3 i=4 10，12，12，16，30 ，18 2 i=5 10，12，12，16，18，30 1 選

6、擇排序算法步驟Step1 從原始數(shù)列a1 , a2,a3,an開(kāi)始進(jìn)行排序，比較n-1次，從中選出最小關(guān)鍵字，放在有序數(shù)列中，形成a1、 a2,a3,an有序數(shù)列和無(wú)序數(shù)列兩部分，完成第1趟排序。Step2 處理第i趟排序時(shí)(i=2,3,n),從剩下的n-i+1個(gè)元素中找出最小關(guān)鍵字，放在有序數(shù)列的后面。Step3 重復(fù)Step2，共進(jìn)行n-1趟的選擇處理，數(shù)列全部有序。選擇排序算法select_sort(int item,int count) int i,j,k，t; for(i=0;icount-1;+i) k=i; t=itemi; for(j=i+1;jcount;+j) if(ite

7、mjai+1(i=1,2,n-1),則交換ai和ai+1的位置,直到隊(duì)列尾部。一趟冒泡處理，將序列中的最大值交換到an的位置。 step2 如法炮制，第k趟冒泡，從待排序隊(duì)列的前端開(kāi)始(a1)兩兩比較ai和ai+1（i=1，2，n-k)，并進(jìn)行交換處理,選出序列中第k大的關(guān)鍵字值,放在有序隊(duì)列的最前端。 Step3 最多執(zhí)行n-1趟的冒泡處理,序列變?yōu)橛行?。冒泡排序算?-7bubble(int *item,int count) int i,j，t; /count個(gè)元素 for(i=1;icount;+i) for(j=1;jitemj) t=itemj-1; itemj-1=itemj; i

8、temj=t; 改進(jìn)的冒泡排序3-8 從上述舉例中可以看出，從第4趟冒泡起，序列已有序，結(jié)果是空跑了3趟。若兩次冒泡處理過(guò)程中，沒(méi)有進(jìn)行交換，說(shuō)明序列已有序，則停止交換。 用改進(jìn)的冒泡算法進(jìn)行處理，比較次數(shù)有所減少。 對(duì)于數(shù)列 65,97,76,13,27,49,58 比較次數(shù) 第1趟 65，76，13，27，49，58，97 6 第2趟 65，13，27，49，58，76，97 5 第3趟 13，27，49，58，65，76，97 4 第4趟 13，27，49，58，65，76，97 3 改進(jìn)的冒泡排序算法3-8bubble_a(int *item,int count) int i,j,t,

9、c; for(i=1;icount;+i) c=1; for(j=1;jitemj) t=itemj-1; itemj-1=itemj; itemj=t; c=0; if(c=1) break; 算法討論 若待排序列有序(遞增或遞減),則只需進(jìn)行一趟冒泡處理即可;若反序，則需進(jìn)行n-1趟的冒泡處理。在最壞的情況下,冒泡算法的時(shí)間復(fù)雜度是O( n2 )。 當(dāng)待排序列基本有序時(shí)，采用冒泡排序法效果較好。 冒泡排序算法是穩(wěn)定的。 4、快速排序 快速排序法是一位計(jì)算機(jī)科學(xué)家C.A.R.Hoare推出并命名的。曾被認(rèn)為是最好的一種排序方法。快速排序法是對(duì)冒泡排序法的一種改進(jìn)，也是基于交換排序的一種算法。

10、因此，被稱為“分區(qū)交換排序”?？焖倥判蚧舅枷?在待排序序列中選取一個(gè)元素K，以它為分界點(diǎn)，用交換的方法將序列分為兩個(gè)部分：比該值小的放在左邊，否則在右邊。形成 左子序列K右子序列 再分別對(duì)左、右兩部分實(shí)施上述分解過(guò)程，直到各子序列長(zhǎng)度為1，即有序?yàn)橹??？焖倥判颍ㄋ惴?-9） Step1 分別從兩端開(kāi)始，指針i指向第一個(gè)元素Aleft，指針j指向最后一個(gè)元素Aright，分界點(diǎn)取K ； Step2 循環(huán)（ij）從右邊開(kāi)始進(jìn)行比較： 若K Aj，則將Aj交換到左邊； 若K Aj ，則 j=j-1，再進(jìn)行比較；從左邊開(kāi)始進(jìn)行比較： 若K Ai，則 i=i+1，再進(jìn)行比較； 若K Ai，則將Ai交換

11、到右邊。當(dāng)i=j時(shí)，一次分解操作完成。 Step3 在對(duì)分解出的左、右兩個(gè)子序列按上述步驟繼續(xù)進(jìn)行分解，直到子序列長(zhǎng)度為1（不可再分）為止，也即序列全部有序?？焖倥判蛩惴?-9quick_sort(item,count)int *item,count; qs(item,0,count-1); qs（）子函數(shù)qs(int *item,int left,int right) int i,j,x,y,k; i=left; j=right; x=item(left+right)/2; do while(itemix & iright ) i+ ； while(xleft) j-; if(i=j

12、) y=itemi; itemi=itemj; itemj=y; i+; j-; while(i=j); if(leftj) qs(item,left,j); if(iXj 則Xj送Swapm，j+；m+； 當(dāng)序列L1或L2的全部記錄已歸并到數(shù)組X中,即i=u1+1,或j=u2+1時(shí), 比較結(jié)束,然后將另一個(gè)序列中剩余的所有記錄依此放回到數(shù)組Swap中,完成L1和L2的合并。歸并排序算法3-12merge_sort(int *x,int n) int i,k,l; int swapN; k=1; while(kn) merge(x,swap,k,n); /* 將x中長(zhǎng)度為k的兩個(gè)序列合并， 放

13、入swap中 */ for(i=0;in;i+) /* 將數(shù)列從SWAP放回X中*/ xi=swapi; k=2*k; /* 序列長(zhǎng)度加倍 */ 歸并排序算法3-12(續(xù)一）merge(int *x,int *swap,int k,int n) /*將x中長(zhǎng)度為k的兩個(gè)序列合并， 放入swap中，共有n個(gè)元素 */ int i, j, l1, l2, u1, u2, m; l1=0; m=0; while(l1+kn) l2=l1+k; u1=l2-1; u2=(l2+k-1n)?l2+k-1:n-1; for(i=l1,j=l2;i=u1&j=u2;m+) if(xi=xj) swa

14、pm=xi; i+; else swapm=xj; j+; while(i=u1) /* 將序列1中剩余元素順序放回SWAP中*/ swapm=xi; m+; i+; while(j=u2) /* 將序列1中剩余元素順序放回SWAP中*/ swapm=xj; m+; j+; l1=u2+1; /* 改變子序列 */ /*將原始序列中剩余的、不足一組的記錄順序放到SWAP中 */ for(i=l1;i ai ,則交換它們的位置。 Step3 重復(fù)上述步驟，直到dK = 1。 希爾排序舉例設(shè)有數(shù)列“f d a c b e”,第1趟 d=5 f d a c b e 得到 e d a c b f第2趟

15、 d=3 e d a c b f 得到 c b a e d f第3趟 d=2 c b a e d f 得到 a b c e d f第4趟 d=1 a b c e d f 得到 a d c d e f SHELL排序子函數(shù)shell(char *item,int count) int i,j,k, w; char x; int a=9,5,3,2,1; for(w=0;w5;w+) k=aw; for(i=k;icount;i+) x=itemi; j=i-k; while(x=0)插入排序 itemj+k=itemj; j=j-k; itemj+k=x; SHELL排序主函數(shù)#include stdio.hmain() char s80;int l; printf(Enter a string:);