1、1,計算機軟件技術(shù)基礎(chǔ),課件,第一章 數(shù)據(jù)結(jié)構(gòu),第二章 操作系統(tǒng),第三章 軟件工程,第四章 數(shù)據(jù)庫,2,第一章 數(shù)據(jù)結(jié)構(gòu),第一單元,第二單元,第三單元,第四單元,第五單元,第六單元,第七單元,第八單元,3,查找和排序,第八單元,第一章 數(shù)據(jù)結(jié)構(gòu),4,1.5 查找和排序,1.5.1 查找 一. 查找的概念 查找又稱檢索，它是數(shù)據(jù)處理中使用頻繁的一種重要操作。 查找表(search table) 被查找的數(shù)據(jù)對象是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合， 查找表是一種非常靈活的數(shù)據(jù)結(jié)構(gòu)。 給查找?guī)聿槐悖绊懖檎业男省?5,關(guān)鍵字(key) 規(guī)定能夠標識數(shù)據(jù)元素(或記錄)的一個數(shù)據(jù)項或幾個數(shù)據(jù)

2、項為關(guān)鍵字。 主關(guān)鍵字(primary key) 若此關(guān)鍵字可以唯一地標識一個記錄，則稱此關(guān)鍵字為主關(guān)鍵字； 次關(guān)鍵字(secondary key) 它可以標識若干個記錄。稱為次關(guān)鍵字。 當記錄只有一個數(shù)據(jù)項時，它就是該記錄的關(guān)鍵字。,6,查找(searching)定義 根據(jù)結(jié)定的值，在查找表中查找是否存在關(guān)鍵字等于給定值的記錄， 查找成功 若存在一個或幾個這樣的記錄，則稱查找成功，查找的結(jié)果可以是對應記錄在查找表中的位置或整個記錄的值。 查找不成功 若表中不存在關(guān)鍵字等于給定值的記錄，則稱查找不成功，查找的結(jié)果可以給出一個特定的值或“空”指針。,7,查找應明確下述兩個問題 (1) 查找的方法

3、 在研究各種查找方法時，必須弄清各種方法所使用的組織方式。 (2)查找算法的評價 衡量一個算法的標準主要有兩個 時間復雜度 空間復雜度。 平均查找長度,其中: Pi為查找第i個數(shù)據(jù)元素的概率;Ci為查找到第i個數(shù)據(jù)元素時,需進行的比較次數(shù)。,8,二 順序表的查找 1.順序查找 基本思想 從第一個元素開始，逐個把元素的關(guān)鍵字值和給定值比較，若某個元素的關(guān)鍵字值和給定值相等，則查找成功；否則，若直至第n個記錄都不相等，說明不存在滿足條件的數(shù)據(jù)元素，查找失敗。 順序查找的適用范圍 順序存儲結(jié)構(gòu)組織的查找表的查找 鏈式存儲結(jié)構(gòu)組織的查找表的查找,9,順序查找算法 int seqsearch(int d

4、ata, int x) /*在表中查找關(guān)鍵字值等于x的元素，若找到，則函數(shù)值為該元素在表中的位置，若沒有找到，則函數(shù)值為0 */ int i = N; /N為表的長度，從表尾開始查找 while(datai! = x) i-; return i; 順序查找算法查找成功的平均查找長度,ASL =,10,2、折半查找 折半查找的基本思想： 由于查找表中的數(shù)據(jù)元素按關(guān)鍵字有序(假設(shè)遞增有序)，則在查找時可不必逐個順序比較， 而采用跳躍的方式-先與中間位置的記錄關(guān)鍵字值比較，若相等，則查找成功；若給定值大于中間位置的關(guān)鍵字值，則在查找表中的后半部繼續(xù)進行折半查找；否則在前半部進行折半查找。 折半查找的

5、過程 先確定待查元素所在區(qū)域，然后逐步縮小區(qū)域，直到查找成功或失敗為止。,11,假設(shè)待查元素所在區(qū)域的下界為low, 上界為hig, 則中間位置mid = (low + hig)/2。 (1) 若此元素關(guān)鍵字值等于給定值, 則查找成功; (2) 若此元素關(guān)鍵字值大于給定值, 則在區(qū)域mid + 1 hig內(nèi)進行折半查找; (3) 若此元素關(guān)鍵字值小于給定值, 則在區(qū)域lowmid - 1內(nèi)進行折半查找。 折半查找的適用條件 只適用于以順序存儲結(jié)構(gòu)組織的有序查找表。,12,折半查找算法 int binsearch(int data, int x) /*在表中查找關(guān)鍵字值等于x的元素，若找到，則函

6、數(shù)值為該元素在表中的位置，若沒有找到，則函數(shù)值為0*/ int low,mid,hig； low=0; hig=last; while (low=hig) mid = (low+hig)/2; /確定中間位置 if(datamid= = x) return mid +1;,13,else if (x datamid) low = mid +1; else hig = mid -1; return 0 ; ; 折半查找成功率的平均查找長度 ASL=log(n+1)- 1,折半查找的優(yōu)點是比較次數(shù)少，查找速度快。但為了快速查找多付出的代價是要對數(shù)據(jù)元素關(guān)鍵字值的大小進行排序，而排序一般是很費時間的

7、。所以折半查找適用于已經(jīng)建立就很少變動而又經(jīng)常需進行查找的有序排列。,14,3、分塊查找 分塊查找要求把一個大的線性表分解成若干塊，在每一塊中結(jié)點的存放可以任意但塊與塊之間必須排序。 索引表 建立一個索引表，把每塊中的最大關(guān)鍵字值作為索引表的關(guān)鍵字值，按照塊的順序存放到一個輔助數(shù)組中，顯然，這個輔助數(shù)組是按關(guān)鍵字非遞減排序的。查找時，首先在索引表中進行查找，確定要找的結(jié)點所在的塊,15,分塊有序表的索引存儲表示,最大關(guān)鍵字,起始地址,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17,由于由索引項組成的索引表按關(guān)鍵字有序排列，則確定塊的查找可以用順序查找，亦

8、可用折半查找，而塊中記錄是任意排列的，則在塊中只能是順序查找。,16,分塊查找的速度 雖然不如折半查找算法，但比順序查找算法要快得多，同時又不需要對全部結(jié)點進行排序。 分塊查找的適用范圍 特別適合于結(jié)點動態(tài)變化的情況。 空間復雜性 在空間復雜性上，分塊查找的主要代價是增加了一個輔助數(shù)組。 注意： 當結(jié)點變化很頻繁時，可能會導致塊與塊之間的結(jié)點數(shù)相差很大，這將會導致查找效率的下降。,17,三種查找方法的比較 順序查找方法最簡單最大的缺點是查找效率低，其平均查找長度在三種查找方法中最大。 折半查找最大的優(yōu)點是查找效率高其平均查找長度在三種查找方法中最小。但是只有當數(shù)據(jù)采用順序存儲結(jié)構(gòu)組織，并且是有

9、序序列時才能使用這種方法進行查找。 數(shù)據(jù)元素是逐段有序的，則采用分塊查找方法，查找效率最高。,18,三哈希查找(散列查找) 哈希查找因使用哈希函數(shù)而得名。它是由關(guān)鍵字作某種運算后直接確定元素的地址。建立ki的地址間的關(guān)系 確定元素的關(guān)鍵字與元素地址的關(guān)系可以用哈希函數(shù)來表示 adr(ai)H(ki) 其中adr(ai)為ai的地址，H(ki)稱為哈希函數(shù)。哈希函數(shù)是種映象關(guān)系函數(shù)。,19, 例:用學生的學號作為學生記錄的關(guān)鍵字，取學號的后三位作為映象地址，那么可以得到下列這些關(guān)鍵字和地址的對照表,采用的哈希函數(shù)為H(ki)k一990000。 沖突現(xiàn)象,要求使用均勻的哈希函數(shù)，即映象后的地址是均

10、勻分布的,20,幾種哈希函數(shù) 1. 自身函數(shù) 關(guān)鍵字自身作為哈希函數(shù)，即 H(k)k，或自身加上一個常數(shù)作為哈希函數(shù)，即H(k)k十c。 例:要統(tǒng)計每周學生到課情況，則取17作為關(guān)鍵字,哈希函數(shù)取關(guān)鍵字自身,則可得到哈希表如下：,21,2. 模函數(shù) 這是一種簡單而較常用的函數(shù)，它利用了簡單的除模取余運算，即 H(k)k MOD m十c其中m和c都是整數(shù)，m決定存儲單元數(shù)，c決定存儲單元地址的范圍。為了得到較均勻的地址分布，m應取為質(zhì)數(shù)。 例: m101，c1000時，則存儲單元數(shù)為101，存儲地址范圍為1000至1100。當關(guān)鍵字k5000時，用這個哈希函數(shù)可將k轉(zhuǎn)換為地址1051。當k504

11、9時，可轉(zhuǎn)換為地址1100。,22,3. 平方取中函數(shù) 這是一種較常用的哈希函數(shù)。首先將關(guān)鍵字平方，然后取中間幾位作為地址，位數(shù)可根據(jù)要求的地址范圍來確定。有時不能滿足所要求的范圍，可再加以處理，如乘以一個比例因子等。 例: 有一個關(guān)鍵字M9633，平方后得到92775424，如需要的地址長度為3位，則可由中間取754作為地址。取中間幾位的目的是因為中間位與關(guān)鍵字的各位都有關(guān)系，哈希地址的分亦可更均勻些。,23,4 折疊函數(shù) 折疊函數(shù)是壓縮關(guān)鍵字位數(shù)的有效方法。這種方法將關(guān)鍵字分成位數(shù)相等的部分，最后部分的位數(shù)可能少些，每部分的位數(shù)取決于對存儲地址位數(shù)的要求。把各段加起來，去掉最高位的進位就得

12、到了所要求的地址。 例:有關(guān)鍵字34586612，要求存儲地址為3位十進制數(shù)，則可得到哈希地址是223，如圖1-70(a)所示。,24,圖1-70哈希地址構(gòu)造過程,在使用方法上，也可將兩邊的兩段反向然后相加，則可得到地址430，如圖 1-70(b)所示。,例:有關(guān)鍵字34586612，要求存儲地址為3位十進制數(shù)，則可得到哈希地址是223。,25,解決沖突的幾種方法 (1) 開放地址法 線性探查法 設(shè)表長為m，關(guān)鍵字個數(shù)為n。 探查法的基本思想 將散列表看成是一個環(huán)形表，若發(fā)生沖突的單元地址為d，則依次探查 d+1,d+2, m1, 0,1,dl,直至找到一個空單元為至。 開放地址公式為 di(

13、di)m (1im1) (式1) 其中dH(key)。,26,例1-10已知一組關(guān)鍵字集合(26,36,41,38,44,15,68,12,06,51,25),用線性探查法解決沖突，試構(gòu)造這組關(guān)鍵字的散列表。 令裝填因子1 ,取=0.75 。 因為n11，所以, 散列表長: mn/15，即散列表為HT15。 散列函數(shù) 利用除留余數(shù)法構(gòu)造散列函數(shù)，選p15,即散列函數(shù)為: H（key）15,27,28,“堆積” 用線性探查法解決沖突時,當表中 i, i1 , ik位置上已有結(jié)點時，一個散列地址為i, i+1, , i+k+1的結(jié)點都將插入在位置i+k+1上，我們把這種散列地址不同的結(jié)點，爭奪同一

14、個后繼散列地址的現(xiàn)象稱為“堆積” 二次探查法 二次探直法的探查序列依次是：12，-12， 22，-22 ，即，發(fā)生沖突時，將同義詞來回散列在第一個地址dH(key)的兩端。,29,當發(fā)生沖突時，求下一個開放地址的公式為： d2i1(di2)m d2i(d-i2)m (1i(m-1)2) (式2) 這種方法雖然減少了堆積，但不容易探查到整個散列表空間，只有當表長m為4j3的素數(shù)時，才能探查到整個表空間這里j為某一正整數(shù)。 隨機探查法 采用一個隨機數(shù)作為地址位移計算下一個單元地址，,30,求下一個開放地址的公式 di(dRi)m (1i(m1) (式3) 其中，d=H(key) , Rl , R2

15、,Rm1是1, 2, m1的一個隨機排列。如何得到隨機排列，涉及到隨機數(shù)的產(chǎn)生問題。在實用中，常常用移位寄存器序列代替隨機數(shù)序列。 （2）拉鏈法 拉鏈法解決沖突的方法： 將所有關(guān)鍵字為同義詞的結(jié)點鏈接到同一個單鏈表中。,31,例111已知一組關(guān)鍵字和選定的散列函數(shù)和上例相同，用拉鏈法解決沖突構(gòu)造這組關(guān)鍵字的散列表。 因為散列函數(shù)H(key)key15的值域為0 -12，故散列表為HTP13。當把H(key)i的關(guān)鍵字插入第i個單鏈表時，既可插在鏈表的頭上，也可以插在鏈表的尾上。若采用將新關(guān)鍵字插入鏈尾的方式，依次把給定的這組關(guān)鍵字插入表中，則所得到的散列表如圖172所示。,32,拉鏈法解決哈希

16、地址沖突,0 1 2 3 4 5 6 7 8 9 10 11 12,圖172拉鏈法解決哈希地址沖突,33,1.5.2 排序 功能 將一個數(shù)據(jù)元素的無序序列調(diào)整為一個有序序列。 排序的依據(jù) 排序所依據(jù)的是數(shù)據(jù)元素中的某一個數(shù)據(jù)項(或幾個數(shù)據(jù)項的組合)的值，在數(shù)據(jù)元素是一個基本項時，排序就依據(jù)該數(shù)據(jù)元素的值。 排序關(guān)鍵字(key word) 排序所依據(jù)的數(shù)據(jù)項(或數(shù)據(jù)項的組合)統(tǒng)稱為排序關(guān)鍵字。 增序排列、降序排列 和內(nèi)排序。,34,一插入排序 插入排序的基本思想 每次選擇待排序的記錄序列的第一個記錄，按照排序碼的大小將其插入到已排序的記錄序列中的適當位置，直到所有記錄全部排序完畢。 1. 直接插

17、入排序 直接插入排序是一種最簡單的排序方法，整個排序過程為：先將第一個記錄看作是一個有序的記錄序列，然后從第二個記錄開始，依次將未排序的記錄插入到這個有序的記錄序列中去，直到整個文件中的全部記錄排序完畢。,35,例112 假設(shè)有五個元素構(gòu)成的數(shù)組，其排序碼依次為：50, 20, 40, 75, 35。,20 40 75 35 從50開始,40 75 35,初始序列,將20插入到位置0,50后移到位置1,第一趟掃描后,75 35,第二趟掃描后,將40插入到位置1,50后移到位置2,第三趟掃描后,35,記錄75位置不變,第四趟掃描后,將35插入到位置1，后面記錄后移,圖 1-73 直 接 插 入

18、排 序 示 例,36,2. 折半插入排序,35,(a),k = 0 m = 1 r = 3 3540,故r = m-1 = 0,35,(b),k = m = r = 0 35=20,故k = m+1 =1 此時kr,折半結(jié)束，找到插入位置1，將35插入到位置1，原來從位置1開始到位置3的各個記錄右移一個位置。,(c),37,3. 希爾排序 希爾排序又稱縮小增量排序 希爾排序的基本思想 先選取一個小于n的整數(shù)di(稱之為步長),然后把排序表中的n個記錄分為di個組。從第一個記錄開始,間隔為di的記錄為同一組,各組內(nèi)進行直接插入排序。一趟之后,間隔di的記錄有序,隨著有序性的改善,減小步長di ,

19、重復進行,直到di1,使得間隔為1的記錄有序,也就是整體達到有序。步長為1時就是直接插入排序。,38,例114 設(shè)排序表關(guān)鍵字序列為：39, 80, 76, 41, 13, 29, 50, 78, 30, 11, 100, 7, 41, 86,步長因子分別取5、3、1，則排序過程如圖175所示。,初始序列,39 80 76 41 13 29 50 78 30 11 100 7 41 86,第一趟 di = 5,29,39,100,7,第一趟排序結(jié)果,80,50,41,76,78,30,41,86,11,13,39,第一趟排序結(jié)果,第二趟 di = 3,第二趟排序結(jié)果,13 7 39 29 11

20、 41 30 76 41 50 86 80 78 100,第三趟 di = 1及排序結(jié)果,7 11 13 29 30 39 41 41 50 76 78 80 86 100,40,希爾排序算法如下： #include #define MAX 14 int g4=5,3,1,0; /步長數(shù)組 void shellsort(int number) int i, j, k, gap,t=0,temp; gap = gt; /初始步長為5 while(gap 0) for(k = 0; k gap; k+) for(i = k+gap; i MAX; i+=gap) ,41,for(j = i - g

21、ap; j = k; j-=gap) if (numberj numberj+gap) temp=numberj; numberj=numberj+gap; numberj+gap=temp; else break; ,42,printf(步長為%d時序列為: n, gap); for(i = 0; i MAX; i+) printf(%4d, numberi); printf(n); t+; gap = gt; /取下一個步長 ,43,void main() int numberMAX = 39,80,76,41,13,29,50,78,30,11,100,7,41,86; int i; p

22、rintf(初始序列: n); for(i = 0; i MAX; i+) printf(%4d, numberi); printf(n); shellsort(number); /希爾排序 性能分析：希爾排序方法是一個不穩(wěn)定的排序方法。,44,二交換排序 交換排序的基本思想 兩兩比較待排序記錄的關(guān)鍵字，發(fā)現(xiàn)兩個記錄的次序相反時即進行交換，直到?jīng)]有反序的記錄為止。 交換排序基本思想的主要排序方法冒泡 排序和快速排序。 1. 冒泡排序 工作量的分析 最壞的情況下, 對size大小的表冒泡排序要作size - 1次大循環(huán), 內(nèi)循環(huán)的平均次數(shù)是size/2, 算法的復雜性是size(size-1)/

23、2。,45,冒泡排序過程排序前 19 13 05 27 01 26 31 16 02 09 11 21第一趟13 05 19 01 26 27 16 02 09 11 2131第二趟05 13 01 19 26 16 02 09 11 21 27 31第三趟05 01 13 19 16 02 09 11 21 26 27 31第四趟01 05 13 16 02 09 11 19 21 26 27 31第五趟01 05 13 02 09 11 16 19 21 26 27 31第六趟01 05 02 09 11 13 16 19 21 26 27 31第七趟01 02 05 09 11 13 1

24、6 19 21 26 27 31,46,19 13 05 27 01 26 31 16 02 09 11 21,13 19 05 27 01 26 31 16 02 09 11 21,13 05 19 27 01 26 31 16 02 09 11 21,13 05 19 27 01 26 31 16 02 09 11 21,13 05 19 01 27 26 31 16 02 09 11 21,13 05 19 01 26 27 31 16 02 09 11 21,13 05 19 01 26 27 31 16 02 09 11 21,13 05 19 01 26 27 16 31 02 0

25、9 11 21,47,13 05 19 01 26 27 16 31 02 09 11 21,13 05 19 01 26 27 16 02 31 09 11 21,13 05 19 01 26 27 16 02 09 31 11 21,13 05 19 01 26 27 16 02 09 11 31 21,13 05 19 01 26 27 16 02 09 11 21 31,每一趟比較 的過程示意圖 冒泡排序是一個穩(wěn)定的排序方法。,48,冒泡排序算法： void bubblesort(int a, int size) int i,j,tmp,k,flag=1; for(i=0; i a j

26、+1) tmp = a j ; a j = a j+1; a j+1 = tmp; flag=1; ,49,if(flag) printf(第%2d 趟:,i+1); /* 打印每趟排序結(jié)果 */ for(k=0; ksize; k+) printf(%3d,ak); printf(n); /* 換行 */ ,50,void main() int a12=19,13,5,27,1,26,31,16,2,9,11,21; int size=12; int i; printf(初始序列:); for(i=0; isize; i+)printf(%3d,ai); printf(n); bubbles

27、ort(a,12); /* 排序 */ ,51,2. 快速排序 快速排序又叫作分區(qū)交換排序，是目前已知的平均速度較快的一種排序方法，它是對冒泡排序方法的一種改進。 快速排序方法的基本思想 從待排序的n個數(shù)據(jù)元素中任意選取一個元素Ri（通常選取無序序列中的第一個元素）作標準，調(diào)整序中各個元素的位置，使排在Ri前面的元素的排碼都小于Ri.key，排在Ri后面的元素的排序碼都大于Ri.key。通常把這樣的一個過程稱作一次快速排序。,52,在第一次快速排序中，確定了元素Ri最終在序列中的排列位置，同時也把剩余的數(shù)據(jù)元素分成了兩個子序列。對兩個子序列再分別進行快速排序，又確定了兩個元素在序列中應處的位置

28、，并將剩余元素分成了四個子序列，如此重復下去，當各個子序列的長度為1時，全部元素排序完畢。 可見，快速排序中的基本操作是子序列的劃分操作。,53,設(shè)當前處理的元素序列的下界是low，上界是high，劃分操作的步驟如下： (1) 讓兩個指針i , j分別指向序列的第一個元素和最后一個元素(即i=low:j=high) ，并將第一個元素的排序碼保存在k中； （2）從右向左掃描過程 用k與j指向的元素的排序碼key比較，若k Rj.key，則再比較j的前一個元素的排序碼(j=j-1)；否則將元素Rj和Ri互換位置。此過程又稱為從右向左掃描過程。,54,(3)從左向右掃描過程 用k與i指向的元素的排序

29、碼key比較，若kRi.key，則再與i的后一個元素排序碼比較(i=i +1)；否則將元素Ri和Rj互換位置。此過程又稱從左向右掃描過程。 (4) 比較i和j，ij，則重復上面(2)、 (3)操作，直到i=j時，劃分操作結(jié)束 例: 一組待排序元素的排序碼序列為（49，38，60，90，70，15，30，49），試畫出在第一趟快速排序中元素的交換示意圖。,55,i = j 結(jié)束序 30 38 15 49 70 90 60 49 列狀態(tài)為,繼續(xù)循環(huán) 30 38 15 49 70 90 60 49,初始狀態(tài) 49 38 60 90 70 15 30 49,從右向左掃描后 30 38 60 90 70

30、 15 49 49,從左向右掃描后 30 38 49 90 70 15 60 49,重復從右向左后 30 38 15 90 70 49 60 49,重復從左向右后 30 38 15 49 70 90 60 49,56,結(jié)束 結(jié)束 49 60 70 90,初始狀態(tài) 49 38 60 90 70 15 30 49 ,一次劃分之后 30 38 15 49 70 90 60 49 ,分別進行快排序15 30 38,49 60 結(jié)束,結(jié)束,有序序列 15 30 38 49 49 60 70 90,快速排序示例排序的全過程,57,快速排序的劃分算法算法 struct Record int key; R11

31、=0,49,14,38,74,96,65, 8,49,55,27; int k=1; /記錄劃分次數(shù) int Partition(struct Record R,int low, int high) /*對Rlowhigh，以Rlow為基準對象進行劃分，算法返回基準對象記錄的最終位置*/ R0.key=Rlow.key; /*緩存基準對象記錄*/,58,while(low= R0.key) high-; if(lowhigh) Rlow.key = Rhigh.key; low+; /*將比基準對象小的記錄交換到前面*/ while(lowhigh /*將比基準對象大的記錄交換到后面* ,59

32、,Rlow.key = R0.key; /*基準對象記錄到位*/ return low; /*返回基準對象記錄所在的位置*/ 快速排序的算法： void Quick_Sort(struct Record R, int s, int t) /*對順序表Rlowhigh進行快速排序*/ int i,j;,60,if(st) i = Partition(R,s,t); /*將表一分為二*/ printf(第%d次劃分 :,k+); for(j=1; j11; j+)printf(%5d,Rj.key); printf(n); Quick_Sort(R,s,i-1); /*對基準對象前端子表進行快速排

33、序*/ Quick_Sort(R,i+1,t); /*對高端子表進行快速排序*/ ,快速排序是一個不穩(wěn)定的排序方法。,61,void main() int n=11,i; printf(初始序列為:); for(i=1; in; i+)printf(%5d,Ri.key); printf(n); Quick_Sort(R,1,10); /* 排序 */ printf(最終序列為:); for(i=1; in; i+)printf(%5d,Ri.key); printf(n); ,62,三選擇排序 選擇排序的基本思想 對等待排序的記錄Rl，R2，Rn進行n次選擇操作，其中第i次操作是選擇第i小(或大)的記錄故在第i個(或n-i+1個)位置上。 簡單選擇排序： 簡單選擇排序的基本思想是： 第一趟排序 第一趟排序是在無序的K1,K2,K3,Kn按排序碼選出最小的元素,將它與K1交換；,63,第二趟排序 第二趟排序是在無序的K2,K3,Kn中選出最小的元素，將它與K2交換； 第i趟排序 而第i趟排序時K1,K2,Ki-1已排好序，在當