數(shù)據(jù)結(jié)構(gòu)(Java)-第9章排序

基本內(nèi)容1.概述第9章排序2.插入排序3.交換排序4.選擇排序5.基數(shù)排序6.各種內(nèi)部排序的比較7.排序項(xiàng)目實(shí)踐排序是以關(guān)鍵字為基準(zhǔn)的，將關(guān)鍵字重新排列成遞增或遞減的序列。一、概述1.排序算法的穩(wěn)定性假設(shè)待排序的序列中存在多個(gè)具有相同關(guān)鍵字的數(shù)據(jù)元素，若使用某個(gè)排序算法后，這些元素的相對(duì)位置保持不變，則稱此排序算法是穩(wěn)定的；若元素的相對(duì)位置發(fā)生了變化，則稱為不穩(wěn)定的。2.內(nèi)排序與外排序內(nèi)排序：指在排序的整個(gè)過程中，數(shù)據(jù)全部放在計(jì)算機(jī)的內(nèi)存儲(chǔ)器中。外排序：指待排序的記錄數(shù)量很大，以致內(nèi)存不能一次容納全部記錄，在排序過程中需對(duì)外存進(jìn)行訪問的排序過程。二、插入排序9.2.1直接插入排序基本思想：從第2個(gè)記錄開始，依次將每個(gè)記錄按其關(guān)鍵字的大小，插入到一個(gè)有序的子序列中，使之仍然是有序的，直至所有的記錄插完為止?！纠?.1】有一組記錄，它們的關(guān)鍵字分別為：（28，15，19，37，33，12），用直接插入法進(jìn)行排序（關(guān)鍵字遞增有序）。二、插入排序排序過程：第三趟排序后：(15192837)3312第二趟排序后：(151928)373312第一趟排序后：(1528)19373312數(shù)組下標(biāo)：012345關(guān)鍵字序列：(28)1519373312第四趟排序后：(1519283337)12第五趟排序后：(121519283337)二、插入排序算法實(shí)現(xiàn)：publicclassInsertSortTest{

publicvoidInsertSort(int[]a){ intt; for(inti=0;i<a.length-1;i++){//n-1趟掃描

t=a[i+1]; intj=i; while(j>=0){//為每個(gè)待插入元素尋找插入位置

if(t<a[j]){//發(fā)現(xiàn)插入位置后，執(zhí)行元素移動(dòng)

a[j+1]=a[j];//元素后移

} else break; j--; } a[j+1]=t;//將待插入元素放入合適的位置

} }}二、插入排序9.2.2折半插入排序基本思想：利用折半查找代替直接插入排序中的順序查找，則構(gòu)成折半插入排序。算法實(shí)現(xiàn)：publicclassBinaryInsertSort{//對(duì)數(shù)組a按關(guān)鍵字升序進(jìn)行折半插入排序

publicvoidsort(int[]a){sort(a,1);}二、插入排序//將下標(biāo)為findFlag的元素插入到已排好序的子序列sortArray中

privatevoidsort(int[]sortArray,intfindFlag){if(findFlag>sortArray.length){//排序結(jié)束

return;}//將下標(biāo)為findFlag的元素插入到下標(biāo)范圍在0到findFlag-1的數(shù)組sortArraysort(sortArray,0,findFlag-1,findFlag);if(findFlag<sortArray.length-1){sort(sortArray,findFlag+1);}}二、插入排序

//將下標(biāo)為findFlag的元素插入到下標(biāo)范圍在from到to的數(shù)組sortArrayprivatevoidsort(int[]sortArray,intfrom,intto,intfindFlag){//獲得即將插入的元素的下標(biāo)

intsortKey=fintFlag(sortArray,from,to,sortArray[findFlag]);for(;sortKey<=to;sortKey++){charge(sortArray,sortKey,findFlag);}}//將下標(biāo)為from和下標(biāo)為to的數(shù)組元素交換privatevoidcharge(int[]sortArray,intfrom,intto){if(sortArray[from]>sortArray[to]){inttemp=sortArray[to];sortArray[to]=sortArray[from];sortArray[from]=temp;}}二、插入排序

//返回即將插入的關(guān)鍵字值為key的元素在有序表sortArray中的下標(biāo)privateintfintFlag(int[]sortArray,intfrom,intto,intkey){if(to-from<=1){if(key<sortArray[from]){returnfrom;}else{returnto;}}

//如果關(guān)鍵字值key比有序表的上屆還小，則插入的元素下標(biāo)應(yīng)為fromif(key<sortArray[from]){returnfrom;}二、插入排序

//如果關(guān)鍵字值key比有序表的下屆還大，則插入的元素下標(biāo)應(yīng)為toif(key>sortArray[to]){returnto;}inttemp=(from+to)/2;//獲得查找區(qū)間的中間點(diǎn)if(key<sortArray[temp+1]&&key>sortArray[temp]){returntemp;}if(sortArray[temp]<key){returnfintFlag(sortArray,temp,to,key);//遞歸查找右半?yún)^(qū)}

else{returnfintFlag(sortArray,from,temp,key);//遞歸查找左半?yún)^(qū)}}二、插入排序9.2.3希爾排序基本思想：將一個(gè)數(shù)據(jù)序列分成若干組，每組由若干相隔一段距離的元素組成，這段距離稱為增量，也稱步長因子，然后在一個(gè)組內(nèi)采用直接插入排序算法進(jìn)行排序。【例9.2】有一組記錄，它們的關(guān)鍵字分別為：（28，15，19，37，33，12，45，20，19*，41），用希爾排序算法進(jìn)行排序（關(guān)鍵字遞增有序）。二、插入排序排序過程：

19*37

1920第二趟排序后：12152019*332819453741

3341

15451228第一趟排序后：12151919*33284520374112203319371519*28454112152019*332819453741第三趟排序后：12151919*202833374145281519373312452019*41二、插入排序算法實(shí)現(xiàn)：publicclassShellSortTest{//對(duì)數(shù)組a按增量d進(jìn)行希爾排序

publicvoidshell(int[]a,intd){ intt; intn=a.length; intj=0; for(inti=d;i<n;i++){//對(duì)每組子序列執(zhí)行插入操作

if(a[i]<a[i-d]){ t=a[i]; j=i-d; do{ a[j+d]=a[j];//記錄后移

j=j-d;//查找下一個(gè)記錄

}while(j>0&&t<a[j]); a[j+d]=t;//插入a[i] } } }二、插入排序

//計(jì)算希爾排序的增量，然后調(diào)用希爾排序算法實(shí)現(xiàn)排序 publicvoidshellSort(int[]a){ intincr=a.length; do{ incr=incr/2;//計(jì)算增量 shell(a,incr); }while(incr>=1); }}三、交換排序9.3.1冒泡排序基本思想：將長度為n的記錄，從頭到尾依次與相鄰的兩個(gè)記錄進(jìn)行比較，若為逆序則將兩個(gè)記錄交換，將序列照此方法從頭到尾處理一遍稱作一趟冒泡排序，這樣就可以將關(guān)鍵字值最大的記錄交換到最后的位置上（假設(shè)按升序排列）。然后，對(duì)前面n-1個(gè)記錄進(jìn)行同樣的操作，那么經(jīng)過第二趟排序，關(guān)鍵字值次大的記錄交換到n-1個(gè)位置上。依次類推，直到所有的記錄有序。【例9.3】有一組記錄，它們的關(guān)鍵字分別為：（33，15，19，28，37，12），用冒泡排序算法進(jìn)行排序（關(guān)鍵字遞增有序）。排序過程：三、交換排序第五趟排序后：121519333741第三趟排序后：151912333741第二趟排序后：151933123741第一趟排序后：153319371241數(shù)組下標(biāo)：012345關(guān)鍵字序列：331541193712第四趟排序后：151219333741算法實(shí)現(xiàn)：publicclassBubbleSortTest{//對(duì)數(shù)組a按關(guān)鍵字升序進(jìn)行冒泡排序publicvoidbubbleSort(int[]a){ intt; intn=a.length; for(inti=0;i<n-1;i++){ for(intj=0;j<n-i-1;j++){ if(a[j]>a[j+1]){//若為逆序，則將a[j]與a[j+1]交換

t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } }}}三、交換排序三、交換排序9.3.2快速排序基本思想：從數(shù)組中取出一個(gè)元素作為基準(zhǔn)值，把其它元素分為兩組：一組是全部小于基準(zhǔn)值的元素；另一組是全部大于基準(zhǔn)值的元素，然后通過遞歸對(duì)這兩個(gè)組再分別排序。排序過程：設(shè)1≤p<q≤n，r[p],r[p+1],...,r[q]為待排序列，快速排序的具體算法描述如下：步驟一：low=p；high=q；//設(shè)置兩個(gè)對(duì)象low和highr[0]=r[low]；//取第一個(gè)記錄為基準(zhǔn)記錄，low位置暫設(shè)為空位步驟二：若low=high，則r[low]=r[0];//填入基準(zhǔn)記錄，即確定了基準(zhǔn)記錄的位置否則，若low<high，搜索需要交換的記錄，并交換之三、交換排序步驟三：若low<high且r[high]≥r[0]，則high=high-1；轉(zhuǎn)步驟三；//從high所指位置向前搜索，至多到 //low+1位置；然后尋找r[high]<r[0]r[low]=r[high]；//找到r[high]<r[0]，設(shè)置high為新基準(zhǔn)位置，

//然后小于基準(zhǔn)記錄關(guān)鍵字的記錄前移。步驟四：若low<high且r[low]<r[0]low=low+1；轉(zhuǎn)步驟四；//從low所指位置向后搜索，至多到high-1位 //置，然后尋找r[low]≥r[0] r[high]=r[low]；//找到r[low]≥r[0]，設(shè)置low為新基準(zhǔn)記錄位置，

//大于等于基準(zhǔn)記錄關(guān)鍵字的記錄后移。 轉(zhuǎn)步驟二//繼續(xù)尋找空位算法實(shí)現(xiàn)：publicclassQuickSortTest{publicvoidquickSort(int[]c,intlow,inthigh){ inttemp=c[low];//取出基準(zhǔn)記錄

intn=high-low+1;//獲得排序的元素個(gè)數(shù)

inti=low,j=high; while(i<j){ while(c[j]>temp&&i<j){//從j開始搜索小于基準(zhǔn)記錄的值

j--; } if(i<j){//出現(xiàn)小于基準(zhǔn)記錄的值后，將j對(duì)應(yīng)的值放到i處

c[i]=c[j]; i++; } while(c[i]<=temp&&i<j){//從i向后搜索，找出大于基準(zhǔn)記錄的值

i++; }三、交換排序 if(i<j){//出現(xiàn)大于基準(zhǔn)記錄的值后，將i處的值放入j處

c[j]=c[i]; j--; } } c[i]=temp;//把基準(zhǔn)記錄放入合適的位置

if(low<i-1) quickSort(c,low,i-1);//對(duì)左子序列進(jìn)行快速排序

if(high>i+1) quickSort(c,i+1,high);//對(duì)右子序列進(jìn)行快速排序

}}三、交換排序四、選擇排序9.4.1簡單選擇排序基本思想：從待排序的所有記錄中，選取關(guān)鍵字值最小的記錄并將它與原始序列中的第一個(gè)記錄交換位置；然后，去掉關(guān)鍵字值最小的記錄，從剩下的記錄中選取關(guān)鍵字值最小的記錄并將它與原始序列中第二個(gè)記錄交換位置……如此反復(fù)進(jìn)行下去，直到序列中全部記錄排序完畢?！纠?.5】有一組記錄，它們的關(guān)鍵字分別為：（83,40,63,13,84,35），用簡單選擇排序算法進(jìn)行排序（關(guān)鍵字遞增有序）。排序過程：四、選擇排序第五趟排序后：133540638384第三趟排序后：133540838463第二趟排序后：133563838440第一趟排序后：134063838435數(shù)組下標(biāo)：012345關(guān)鍵字序列：834063138435第四趟排序后：133540638483算法實(shí)現(xiàn)：publicclassSelectSortTest{ publicvoidselectSort(int[]a){ intmin;//min存儲(chǔ)單趟排序的最小元素

inttemp;//temp作為交換的臨時(shí)變量

intindex=0;//存儲(chǔ)單趟排序最小元素的下標(biāo)

intn=a.length;//存取待排序列的長度

for(inti=0;i<n;i++){//n個(gè)元素排n-1趟

min=a[i]; index=i; for(intj=i+1;j<n;j++){//查找最小元素

if(a[j]<min){ min=a[j]; index=j;//記錄最小元素的下標(biāo)

} }四、選擇排序

if(index!=i){//如果最小元素不是下標(biāo)為i的元素，則進(jìn)行交換 temp=a[i]; a[i]=a[index]; a[index]=temp; }

} }}四、選擇排序四、選擇排序9.4.2堆排序堆的定義：具有n個(gè)元素的序列{k1,k2,…,kn}當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)，稱之為堆。（1）ki≤k2i并且ki≤k2i+1（2）ki≥k2i并且ki≥k2i+1滿足條件（1）稱為小根堆，滿足條件（2）稱為大根堆。962791138831327384965765097小根堆大根堆四、選擇排序基本思想：利用小根堆（或大根堆）來選取當(dāng)前無序序列中關(guān)鍵字最?。ɑ蜃畲螅┑挠涗泚砼判颉ＴO(shè)有n個(gè)元素，首先將這n個(gè)元素按關(guān)鍵字建成堆，將堆頂元素輸出，得到n個(gè)元素中關(guān)鍵字最小(或最大)的元素。然后，再對(duì)剩下的n-1個(gè)元素建成堆，輸出堆頂元素，得到n個(gè)元素中關(guān)鍵字次小(或次大)的元素。如此反復(fù)，便得到一個(gè)按關(guān)鍵字有序的序列。堆排序分兩個(gè)階段：（1）創(chuàng)建最小堆（或最大堆），即：將n個(gè)元素的序列按關(guān)鍵字建成堆；（2）調(diào)整堆，即：輸出堆頂元素后，調(diào)整剩余n-1個(gè)元素，使其按關(guān)鍵字成為一個(gè)新堆。四、選擇排序（1）創(chuàng)建最小堆在具有n個(gè)結(jié)點(diǎn)的完全二叉樹中，首先從第個(gè)結(jié)點(diǎn)為根的子樹開始，將該子樹的根結(jié)點(diǎn)與它的孩子結(jié)點(diǎn)的值進(jìn)行比較，將較小者與之交換，使該子樹成為堆，然后向前依次對(duì)各結(jié)點(diǎn)為根的子樹重復(fù)上述步驟，使之成為堆，直到根結(jié)點(diǎn)?！纠?.6】設(shè)關(guān)鍵字序列為{（49，38，65，97，76，13，27，50）}，創(chuàng)建最小堆。49653827137697504965382713765097491338276576509749133827657650971327384965765097四、選擇排序（2）調(diào)整堆輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，并與其中小者進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱這個(gè)從堆頂至葉子的調(diào)整過程為“篩選”。例9.6已創(chuàng)建好了一個(gè)最小堆，寫出其堆排序的過程。13273849657650979727384965765013輸出：132749389765765013輸出：139749382765765013輸出：13273849502765769713輸出：13276549502738769713輸出：1327384965502738769713輸出：1327387665502738499713輸出：132738495065762738499713輸出：132738499765762738495013輸出：13273849506597762738495013輸出：13273849509765762738495013輸出：1327384950657665972738495013輸出：1327384950659765762738495013輸出：132738495065769765762738495013輸出：1327384950657697五、歸并排序2－路歸并排序基本思想：假設(shè)初始序列有n個(gè)記錄，首先把n個(gè)記錄看成n個(gè)長度為1的有序序列，進(jìn)行兩兩歸并，得到個(gè)長度為2的關(guān)鍵字有序序列，再兩兩歸并直到所有記錄歸并成一個(gè)長度為n的有序序列為止?！纠?.8】有一組記錄，它們的關(guān)鍵字分別為：（51，60，38，17，59，22，20，85），用2-路歸并法進(jìn)行排序（關(guān)鍵字遞增有序）。五、歸并排序排序過程：數(shù)組下標(biāo)：01234567關(guān)鍵字序列：5160381759222085第三趟排序后：[1720223851596085]第一趟排序后：[5160][1738][2259][2085]第二趟排序后：[17385160][20225985]六、基數(shù)排序9.6.1多關(guān)鍵字排序多關(guān)鍵字的定義例對(duì)52張撲克牌按以下次序排序：2<3<……<A<2<3<……<A<2<3<……<A<2<3<……<A兩個(gè)關(guān)鍵字：花色（<<<）面值（2<3<……<A）并且“花色”地位高于“面值”六、基數(shù)排序多關(guān)鍵字排序最高位優(yōu)先法（MSD)：先對(duì)最高位關(guān)鍵字k1（如花色）排序，將序列分成若干子序列，每個(gè)子序列有相同的k1值；然后讓每個(gè)子序列對(duì)次關(guān)鍵字k2（如面值）排序，又分成若干更小的子序列；依次重復(fù)，直至就每個(gè)子序列對(duì)最低位關(guān)鍵字kd排序；最后將所有子序列依次連接在一起成為一個(gè)有序序列。最低位優(yōu)先法(LSD)：從最低位關(guān)鍵字kd起進(jìn)行排序，然后再對(duì)高一位的關(guān)鍵字排序，……依次重復(fù)，直至對(duì)最高位關(guān)鍵字k1排序后，便成為一個(gè)有序序列。六、基數(shù)排序