數(shù)據(jù)結構(Java)-第9章排序

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

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

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

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

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

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

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

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

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

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

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

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

//如果關鍵字值key比有序表的下屆還大，則插入的元素下標應為toif(key>sortArray[to]){returnto;}inttemp=(from+to)/2;//獲得查找區(qū)間的中間點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希爾排序基本思想：將一個數(shù)據(jù)序列分成若干組，每組由若干相隔一段距離的元素組成，這段距離稱為增量，也稱步長因子，然后在一個組內采用直接插入排序算法進行排序。【例9.2】有一組記錄，它們的關鍵字分別為：（28，15，19，37，33，12，45，20，19*，41），用希爾排序算法進行排序（關鍵字遞增有序）。二、插入排序排序過程：

19*37

1920第二趟排序后：12152019*332819453741

3341

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

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

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

j=j-d;//查找下一個記錄

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

//計算希爾排序的增量，然后調用希爾排序算法實現(xiàn)排序 publicvoidshellSort(int[]a){ intincr=a.length; do{ incr=incr/2;//計算增量 shell(a,incr); }while(incr>=1); }}三、交換排序9.3.1冒泡排序基本思想：將長度為n的記錄，從頭到尾依次與相鄰的兩個記錄進行比較，若為逆序則將兩個記錄交換，將序列照此方法從頭到尾處理一遍稱作一趟冒泡排序，這樣就可以將關鍵字值最大的記錄交換到最后的位置上（假設按升序排列）。然后，對前面n-1個記錄進行同樣的操作，那么經(jīng)過第二趟排序，關鍵字值次大的記錄交換到n-1個位置上。依次類推，直到所有的記錄有序?！纠?.3】有一組記錄，它們的關鍵字分別為：（33，15，19，28，37，12），用冒泡排序算法進行排序（關鍵字遞增有序）。排序過程：三、交換排序第五趟排序后：121519333741第三趟排序后：151912333741第二趟排序后：151933123741第一趟排序后：153319371241數(shù)組下標：012345關鍵字序列：331541193712第四趟排序后：151219333741算法實現(xiàn)：publicclassBubbleSortTest{//對數(shù)組a按關鍵字升序進行冒泡排序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ù)組中取出一個元素作為基準值，把其它元素分為兩組：一組是全部小于基準值的元素；另一組是全部大于基準值的元素，然后通過遞歸對這兩個組再分別排序。排序過程：設1≤p<q≤n，r[p],r[p+1],...,r[q]為待排序列，快速排序的具體算法描述如下：步驟一：low=p；high=q；//設置兩個對象low和highr[0]=r[low]；//取第一個記錄為基準記錄，low位置暫設為空位步驟二：若low=high，則r[low]=r[0];//填入基準記錄，即確定了基準記錄的位置否則，若low<high，搜索需要交換的記錄，并交換之三、交換排序步驟三：若low<high且r[high]≥r[0]，則high=high-1；轉步驟三；//從high所指位置向前搜索，至多到 //low+1位置；然后尋找r[high]<r[0]r[low]=r[high]；//找到r[high]<r[0]，設置high為新基準位置，

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

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

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

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

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

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

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

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

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

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

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

inttemp;//temp作為交換的臨時變量

intindex=0;//存儲單趟排序最小元素的下標

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

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

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

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

} }四、選擇排序

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

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