算法1、二分查找算法1.1、二分查找算法的原理1.2、二分查找算法的Java實(shí)現(xiàn)2、冒泡排序算法2.1、冒泡排序算法的原理2.2、冒泡排序算法的Java實(shí)現(xiàn)3、插入排序算法3.1、插入排序算法的原理3.2、插入排序算法的Java實(shí)現(xiàn)4、快速排序算法4.1、快速排序算法的原理4.2、快速排序算法的Java實(shí)現(xiàn)5、希爾排序算法5.1、希爾排序算法的原理5.2、希爾排序算法的Java實(shí)現(xiàn)6、歸并排序算法6.1、歸并排序算法的原理6.2、歸并排序算法的Java實(shí)現(xiàn)7、桶排序算法7.1、桶排序算法的原理7.2、桶排序算法的Java實(shí)現(xiàn)8、基數(shù)排序算法8.1、基數(shù)排序算法的原理8.2、基數(shù)排序算法的Java實(shí)現(xiàn)9、其他算法9.1、剪枝算法9.2、回溯算法9.3、最短路徑算法在計(jì)算機(jī)世界里“數(shù)據(jù)結(jié)構(gòu)算法程序”?因此算法在程序開發(fā)中起著至關(guān)重要的作用。雖然我們?cè)陂_發(fā)中自己設(shè)計(jì)算法的情況不多在工作中卻離不開算法。無論是開發(fā)包提供的算法還是我們自己設(shè)計(jì)的算法算法在程序中都無處不在。常用的算法有查找算法和排序算法。查找算法有線性查找算法、深度優(yōu)先搜索算法、廣度優(yōu)先搜索算法和二分查找算法這里重點(diǎn)介紹最常用也最快速的二分查找算法。排序算法是很常見的算法大到數(shù)據(jù)庫設(shè)計(jì)小到對(duì)列表的排序都適用。常用的排序算法有冒泡排序算法、插入排序算法、快速排序算法、希爾排序算法、歸并排序算法、桶排序算法、堆排序算法和基數(shù)排序算法。除此之外還會(huì)介紹一些在應(yīng)用中必不可少的算法例如剪枝算法、回溯算法、最短路徑算法、最大子數(shù)組算法和最長公因子算法。1、二分查找算法二分查找算法又叫作折半查找要求待查找的序列有序每次查找都取中間位置的值與待查關(guān)鍵字進(jìn)行比較如果中間位置的值比待查關(guān)鍵字大則在序列的左半部分繼續(xù)執(zhí)行該查找過程如果中間位置的值比待查關(guān)鍵字小則在序列的右半部分繼續(xù)執(zhí)行該查找過程直到查找到關(guān)鍵字為止否則在序列中沒有待查關(guān)鍵字。1.1、二分查找算法的原理如圖所示在有序數(shù)組[3,4,6,20,40,45,51,62,70,99,110]中查找key20的數(shù)據(jù)根據(jù)二分查找算法只需查找兩次便能命中數(shù)據(jù)。這里需要強(qiáng)調(diào)的是二分查找算法要求要查找的集合是有序的如果不是有序的集合則先要通過排序算法排序后再進(jìn)行查找。1.2、二分查找算法的Java實(shí)現(xiàn)二分查找算法的Java實(shí)現(xiàn)如下publicstaticintbinarySearch(int[]array,inta){intlow0;inthigharray.length-1;intmid;while(lowhigh){mid(lowhigh)/2;//中間位置if(array[mid]a){returnmid;}elseif(aarray[mid]){//向右查找lowmid1;}else{//向左查找highmid-1;}}return-1;}以上代碼定義了方法binarySearch()用于二分查找在該方法中有3個(gè)變量low、mid和high分別表示二分查找的最小、中間和最大的數(shù)據(jù)索引。在以上代碼中通過一個(gè)while循環(huán)在數(shù)組中查找傳入的數(shù)據(jù)在該數(shù)據(jù)大于中間位置的數(shù)據(jù)時(shí)向右查找即最大索引位置不變將最小索引設(shè)置為上次循環(huán)的中間索引加1在該數(shù)據(jù)小于中間位置的數(shù)據(jù)時(shí)向左查找即最小索引位置不變?nèi)缓髮⒆畲笏饕O(shè)置為上次循環(huán)的中間索引并減1。重復(fù)以上過程直到中間索引位置的數(shù)據(jù)等于要查找的數(shù)據(jù)說明找到了要查找的數(shù)據(jù)將該數(shù)據(jù)對(duì)應(yīng)的索引返回。如果遍歷到lowhigh還沒有找到要查找的數(shù)據(jù)則說明該數(shù)據(jù)在列表中不存在返回-1。2、冒泡排序算法冒泡排序Bubble Sort算法是一種較簡單的排序算法它在重復(fù)訪問要排序的元素列時(shí)會(huì)依次比較相鄰的兩個(gè)元素如果左邊的元素大于右邊的元素就將二者交換位置如此重復(fù)直到?jīng)]有相鄰的元素需要交換位置這時(shí)該列表的元素排序完成。該算法名稱的由來是越大的元素會(huì)經(jīng)過交換慢慢“浮”到數(shù)列的頂端升序或降序排列?就如同水的氣泡最終會(huì)上浮到頂端一樣。2.1、冒泡排序算法的原理如圖所示為對(duì)數(shù)組[4,5,6,3,2,1]進(jìn)行冒泡排序每次都將當(dāng)前數(shù)據(jù)和下一個(gè)數(shù)據(jù)進(jìn)行比較如果當(dāng)前數(shù)據(jù)比下一個(gè)數(shù)據(jù)大就將二者交換位置否則不做任何處理。這樣經(jīng)過第1趟排序就會(huì)找出最大值6并將其放置在最后一位經(jīng)過第2趟排序就會(huì)找出次大的數(shù)據(jù)5放在倒數(shù)第二位如此重復(fù)直到所有數(shù)據(jù)都排序完成。2.2、冒泡排序算法的Java實(shí)現(xiàn)冒泡排序算法的Java實(shí)現(xiàn)如下publicstaticint[]bubbleSort(int[]arr){//外層循環(huán)控制排序趟數(shù)for(inti0;iarr.length-1;i){//內(nèi)層循環(huán)控制每一趟排序多少次for(intj0;jarr.length-1-i;j){if(arr[j]arr[j1]){inttemparr[j];arr[j]arr[j1];arr[j1]temp;}}}returnarr;}以上代碼實(shí)現(xiàn)了一個(gè)名為bubbleSort()的冒泡排序算法分為外層循環(huán)和內(nèi)層循環(huán)外層循環(huán)控制排序的次數(shù)內(nèi)層循環(huán)控制每一趟排序多少次。在內(nèi)層循環(huán)中比較當(dāng)前數(shù)據(jù)和下一個(gè)數(shù)據(jù)的大小如果當(dāng)前數(shù)據(jù)大于下一個(gè)數(shù)據(jù)就交換二者的位置這樣重復(fù)進(jìn)行判斷直至整個(gè)排序完成最終返回排序后的數(shù)組。3、插入排序算法插入排序Insertion Sort算法是一種簡單、直觀且穩(wěn)定的排序算法。如果要在一個(gè)已排好序的數(shù)據(jù)序列中插入一個(gè)數(shù)據(jù)但要求此數(shù)據(jù)序列在插入數(shù)據(jù)后仍然有序就要用到插入排序法。插入排序的基本思路是將一個(gè)數(shù)據(jù)插入已經(jīng)排好序的序列中從而得到一個(gè)新的有序數(shù)據(jù)該算法適用于少量數(shù)據(jù)的排序是穩(wěn)定的排序方法。3.1、插入排序算法的原理插入排序算法的原理如圖5-3所示類似于撲克牌游戲的抓牌和整理過程。在開始摸牌時(shí)左手是空的。接著每次從桌上摸起一張牌時(shí)都根據(jù)牌的大小在左手撲克牌序列中從右向左依次比較在找到第一個(gè)比該撲克牌大的位置時(shí)就將該撲克牌插入該位置的左側(cè)這樣依次類推無論什么時(shí)候左手中的牌都是排好序的。如圖所示為插入排序算法的工作流程。輸入原始數(shù)組[6, 2, 5, 8, 7 ]?在排序時(shí)將該數(shù)組分成兩個(gè)子集一個(gè)是有序的Lleft子集一個(gè)是無序的Rright子集。初始時(shí)設(shè)L[ 6 ], R [ 2, 5, 8, 7 ]?。在L里面只有一個(gè)元素4本身就是有序的。接著我們每次都從R中拿出一個(gè)元素插入L中從右到左比自己大的元素后面然后將L中比自己大的所有元素整體后移這樣就保證了L子集仍然是有序的。重復(fù)以上插入操作直到R子集的數(shù)據(jù)為空這時(shí)整個(gè)數(shù)組排序完成排序的結(jié)果被保存在L子集中。3.2、插入排序算法的Java實(shí)現(xiàn)插入排序算法的Java實(shí)現(xiàn)如下publicstaticint[]insertSort(intarr[]){for(inti1;iarr.length;i){//插入的數(shù)intinsertValarr[i];//被插入的位置準(zhǔn)備和前一個(gè)數(shù)進(jìn)行比較intindexi-1;//如果插入的數(shù)比被插入的數(shù)小while(index0insertValarr[index]){//則將arr[index]向后移動(dòng)arr[index1]arr[index];//將index向前移動(dòng)index--;}//將插入的數(shù)放入合適的位置arr[index1]insertVal;}returnarr;}以上代碼定義了insertSort()用于插入排序其中insertVal用于從數(shù)組中取出待插入的數(shù)據(jù)index是待插入的位置。在insertSort()中通過while循環(huán)從數(shù)組中找到比待插入數(shù)據(jù)大的數(shù)據(jù)的索引位置index然后將該index位置后的元素向后移動(dòng)接著將待插入的數(shù)據(jù)插入index1的位置如此重復(fù)直到整個(gè)數(shù)組排序完成。4、快速排序算法快速排序Quick Sort是對(duì)冒泡排序的一種改進(jìn)通過一趟排序?qū)⒁判虻臄?shù)據(jù)序列分成獨(dú)立的兩部分其中一部分的所有數(shù)據(jù)比另一部分的所有數(shù)據(jù)都要小然后按此方法對(duì)兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序整個(gè)排序過程遞歸進(jìn)行最終使整個(gè)數(shù)據(jù)序列變成有序的數(shù)據(jù)序列。4.1、快速排序算法的原理快速排序算法的原理是選擇一個(gè)關(guān)鍵值作為基準(zhǔn)值一般選擇第1個(gè)元素為基準(zhǔn)元素?將比基準(zhǔn)值大的都放在右邊的序列中將比基準(zhǔn)值小的都放在左邊的序列中。具體的循環(huán)過程如下。從后向前比較用基準(zhǔn)值和最后一個(gè)值進(jìn)行比較。如果比基準(zhǔn)值小則交換位置如果比基準(zhǔn)值大則繼續(xù)比較下一個(gè)值直到找到第1個(gè)比基準(zhǔn)值小的值才交換位置。在從后向前找到第1個(gè)比基準(zhǔn)值小的值并交換位置后從前向后開始比較。如果有比基準(zhǔn)值大的則交換位置如果沒有則繼續(xù)比較下一個(gè)直到找到第1個(gè)比基準(zhǔn)值大的值才交換位置。重復(fù)執(zhí)行以上過程直到從前向后比較的索引大于等于從后向前比較的索引則結(jié)束一次循環(huán)。這時(shí)對(duì)于基準(zhǔn)值來說左右兩邊都是有序的數(shù)據(jù)序列。重復(fù)循環(huán)以上過程分別比較左右兩邊的序列直到整個(gè)數(shù)據(jù)序列有序。如圖所示是對(duì)數(shù)組[6,9,5,7,8]進(jìn)行快速排序。先以第1個(gè)元素6為基準(zhǔn)值從數(shù)組的最后一位從后向前比較比較順序?yàn)?6、76、56?找到第1個(gè)比6小的數(shù)據(jù)5然后進(jìn)行第1次位置交換即將數(shù)據(jù)6索引為0和數(shù)據(jù)5索引為2交換位置之后基準(zhǔn)值6位于索引2處接著從前向后比較比較順序?yàn)?6、96?找到第1個(gè)比6大的數(shù)據(jù)9然后進(jìn)行第2次位置交換即將數(shù)據(jù)6索引為2和數(shù)據(jù)9索引為1交換位置交換后6位于索引1處這時(shí)高位和低位都在6處第一次遞歸完成。在第一次遞歸完成后基準(zhǔn)值6前面的數(shù)據(jù)都比6小基準(zhǔn)值6后面的數(shù)據(jù)都比6大。重復(fù)執(zhí)行上述過程直到整個(gè)數(shù)組有序。4.2、快速排序算法的Java實(shí)現(xiàn)快速排序算法的Java實(shí)現(xiàn)如下publicstaticint[]quickSort(int[]arr,intlow,inthigh){intstartlow;//從前向后比較的索引intendhigh;//從后向前比較的索引intkeyarr[low];//基準(zhǔn)值while(endstart){//從后向前比較while(endstartarr[end]key)end--;//如果沒有比基準(zhǔn)值小的則比較下一個(gè)直到有比基準(zhǔn)值小的則交換位置然后又從前向后比較if(arr[end]key){inttemparr[end];arr[end]arr[start];arr[start]temp;}//從前向后比較while(endstartarr[start]key)start;//如果沒有比基準(zhǔn)值大的則比較下一個(gè)直到有比基準(zhǔn)值大的則交換位置if(arr[start]key){inttemparr[start];arr[start]arr[end];arr[end]temp;}//此時(shí)第1次循環(huán)比較結(jié)束基準(zhǔn)值的位置已經(jīng)確定。左邊的值都比關(guān)鍵值小//右邊的值都比關(guān)鍵值大但是兩邊的順序還有可能不一樣接著進(jìn)行下面的遞歸調(diào)用}//遞歸左邊序列從第1個(gè)索引位置到“關(guān)鍵值索引-1”if(startlow)quickSort(arr,low,start-1);//遞歸右邊序列從“關(guān)鍵值索引1”到最后一個(gè)位置if(endhigh)quickSort(arr,end1,high);returnarr;}以上代碼定義了名為quickSort()的快速排序方法在該方法中定義了3個(gè)變量start、end和key分別表示從前向后比較的索引、從后向前比較的索引和基準(zhǔn)值。具體過程為①通過while循環(huán)從后向前比較找到比基準(zhǔn)值小的則交換位置②通過while循環(huán)從前向后比較找到比基準(zhǔn)值大的則交換位置③根據(jù)從前向后比較的索引和從后向前比較的索引的大小不斷遞歸調(diào)用直到遞歸完成返回排序后的結(jié)果。5、希爾排序算法希爾排序Shell Sort算法是插入排序算法的一種又叫作縮小增量排序Diminishing Increment Sort算法是插入排序算法的一種更高效的改進(jìn)版本也是非穩(wěn)定排序算法。希爾排序算法將數(shù)據(jù)序列按下標(biāo)的一定增量進(jìn)行分組對(duì)每組使用插入排序算法排序隨著增量逐漸減少每組包含的關(guān)鍵詞越來越多在增量減至1時(shí)整個(gè)文件被分為一組算法終止。5.1、希爾排序算法的原理希爾排序算法的原理是先將整個(gè)待排序的記錄序列分割成若干子序列分別進(jìn)行直接插入排序待整個(gè)序列中的記錄基本有序時(shí)再對(duì)全部記錄依次進(jìn)行直接插入排序。希爾排序算法的具體做法為假設(shè)待排序元素序列有N個(gè)元素則先取一個(gè)小于N的整數(shù)增量值increment作為間隔將全部元素分為increment個(gè)子序列將所有距離為increment的元素都放在同一個(gè)子序列中在每一個(gè)子序列中分別實(shí)行直接插入排序然后縮小間隔increment重復(fù)上述子序列的劃分和排序工作直到最后取increment1將所有元素都放在同一個(gè)子序列中時(shí)排序終止。由于開始時(shí)increment的取值較大每個(gè)子序列中的元素較少所以排序速度較快到了排序后期increment的取值逐漸變小子序列中的元素個(gè)數(shù)逐漸增多但由于前面工作的基礎(chǔ)大多數(shù)元素已經(jīng)基本有序所以排序速度仍然很快。例如對(duì)數(shù)組[21,25,49,26,16,8]的排序過程如下。1第1趟排序。第1趟排序的間隔為“incrementN/313”?它將整個(gè)數(shù)據(jù)列劃分為間隔為3的3個(gè)子序列然后對(duì)每個(gè)子序列都執(zhí)行直接插入排序相當(dāng)于對(duì)整個(gè)序列都執(zhí)行了部分排序如圖所示。2第2趟排序。第2趟排序的間隔為“incrementincrement/312”?將整個(gè)元素序列劃分為兩個(gè)間隔為2的子序列分別進(jìn)行排序如圖所示。3第3趟排序。第3趟排序的間隔為“incrementincrement/311”?在增量為1時(shí)說明整個(gè)數(shù)組已經(jīng)完成排序。5.2、希爾排序算法的Java實(shí)現(xiàn)希爾排序算法的Java實(shí)現(xiàn)如下publicstaticint[]shellSort(int[]arr){intdkarr.length/31;while(dk1){ShellInsertSort(arr,dk);dkdk/31;}returnarr;}publicstaticvoidShellInsertSort(int[]a,intdk){//類似于插入排序算法但插入排序算法的增量是1這里的增量是dk將1換成dk即可for(intidk;ia.length;i){if(a[i]a[i-dk]){intj;intxa[i];//x為待插入的元素a[i]a[i-dk];for(ji-dk;j0xa[j];jj-dk){//通過循環(huán)逐個(gè)后移一位找到要插入的位置a[jdk]a[j];}a[jdk]x;//將數(shù)據(jù)插入對(duì)應(yīng)的位置}}}6、歸并排序算法歸并排序算法是基于歸并Merge操作的一種有效排序算法是采用分治法Divide and Conquer的典型應(yīng)用。歸并排序算法將待排序序列分為若干個(gè)子序列先對(duì)每個(gè)子序列進(jìn)行排序等每個(gè)子序列都有序后再將有序子序列合并為整體的有序序列。若將兩個(gè)有序表合并成一個(gè)有序表則稱之為二路歸并。6.1、歸并排序算法的原理歸并排序的原理是先將原始數(shù)組分解為多個(gè)子序列然后對(duì)每個(gè)子序列進(jìn)行排序最后將排好序的子序列合并起來。如圖5-8所示為對(duì)數(shù)組[4,1,3,9,6,8]進(jìn)行歸并排序先經(jīng)過兩次分解將數(shù)組分解成4個(gè)子序列然后對(duì)子序列數(shù)組進(jìn)行排序和歸并最終得到排好序的數(shù)組[1,3,4,6,8,9]?。6.2、歸并排序算法的Java實(shí)現(xiàn)歸并排序算法的Java實(shí)現(xiàn)如下publicstaticint[]mergeSort(int[]data){sort(data,0,data.length-1);returndata;}//對(duì)左右兩邊的數(shù)據(jù)進(jìn)行遞歸publicstaticvoidsort(int[]data,intleft,intright){if(leftright)return;//找出中間索引intcenter(leftright)/2;//對(duì)左邊的數(shù)組進(jìn)行遞歸sort(data,left,center);//對(duì)右邊的數(shù)組進(jìn)行遞歸sort(data,center1,right);//將兩個(gè)數(shù)組進(jìn)行歸并merge(data,left,center,right);}/ 將兩個(gè)數(shù)組進(jìn)行歸并兩個(gè)數(shù)組在歸并前是有序數(shù)組在歸并后依然是有序數(shù)組 paramdata數(shù)組對(duì)象left左邊數(shù)組第1個(gè)元素的索引 center左邊數(shù)組最后一個(gè)元素的索引center1是右邊數(shù)組第1個(gè)元素的索引 right右邊數(shù)組最后一個(gè)元素的索引 /publicstaticvoidmerge(int[]data,intleft,intcenter,intright){//臨時(shí)數(shù)組int[]tmpArrnewint[data.length];//右邊數(shù)組第1個(gè)元素的索引intmidcenter1;//third記錄臨時(shí)數(shù)組的索引intthirdleft;//緩存左邊數(shù)組第1個(gè)元素的索引inttmpleft;while(leftcentermidright){//從兩個(gè)數(shù)組中取出最小的值放入臨時(shí)數(shù)組中if(data[left]data[mid]){tmpArr[third]data[left];}else{tmpArr[third]data[mid];}}//將剩余部分依次放入臨時(shí)數(shù)組實(shí)際上兩個(gè)while只會(huì)執(zhí)行其中一個(gè)中while(midright){tmpArr[third]data[mid];}while(leftcenter){tmpArr[third]data[left];}//將臨時(shí)數(shù)組中的內(nèi)容復(fù)制到原數(shù)組中//原left-right范圍內(nèi)的內(nèi)容被復(fù)制到原數(shù)組中while(tmpright){data[tmp]tmpArr[tmp];}}以上代碼定了3個(gè)方法mergeSort()是歸并排序方法的入口sort()對(duì)數(shù)據(jù)進(jìn)行遞歸拆解和合并merge()進(jìn)行數(shù)據(jù)排序和合并。其中sort()每次都將數(shù)組進(jìn)行二分拆解然后對(duì)左側(cè)的數(shù)組和右側(cè)的數(shù)據(jù)分別進(jìn)行遞歸。merge()先將數(shù)組進(jìn)行冒泡排序然后依次將冒泡排序的結(jié)果放入臨時(shí)數(shù)組中最后將排好序的臨時(shí)數(shù)組放入排序數(shù)組中。7、桶排序算法桶排序Bucket Sort算法也叫作箱排序算法它將數(shù)組分到有限數(shù)量的桶中對(duì)每個(gè)桶再進(jìn)行排序有可能使用其他排序算法或以遞歸方式繼續(xù)使用桶排序進(jìn)行排序?最后將各個(gè)桶合并。7.1、桶排序算法的原理桶排序算法的原理是先找出數(shù)組中的最大值和最小值并根據(jù)最大值和最小值定義桶然后將數(shù)據(jù)按照大小放入桶中最后對(duì)每個(gè)桶進(jìn)行排序在每個(gè)桶的內(nèi)部完成排序后就得到了完整的排序數(shù)組。如圖所示為對(duì)數(shù)組[3,6,5,9,7,8]進(jìn)行桶排序首先根據(jù)數(shù)據(jù)的長度和min、max創(chuàng)建三個(gè)桶分別為03、47、810然后將數(shù)組的數(shù)據(jù)按照相應(yīng)的大小放入桶中接著將桶內(nèi)部的數(shù)據(jù)分別進(jìn)行排序最后將各個(gè)桶進(jìn)行合并便得到了完整排序后的數(shù)組。7.2、桶排序算法的Java實(shí)現(xiàn)桶排序算法的Java實(shí)現(xiàn)如下publicstaticint[]bucketSort(int[]arr){intmaxInteger.MIN_VALUE;intminInteger.MAX_VALUE;for(inti0;iarr.length;i){maxMath.max(max,arr[i]);minMath.min(min,arr[i]);}//創(chuàng)建桶intbucketNum(max-min)/arr.length1;ArrayListArrayListIntegerbucketArrnewArrayList(bucketNum);for(inti0;ibucketNum;i){bucketArr.add(newArrayListInteger());}//將每個(gè)元素都放入桶中for(inti0;iarr.length;i){intnum(arr[i]-min)/(arr.length);bucketArr.get(num).add(arr[i]);}//對(duì)每個(gè)桶都進(jìn)行排序for(inti0;ibucketArr.size();i){Collections.sort(bucketArr.get(i));}returnarr;}以上代碼定義了bucketSort()的桶排序算法具體實(shí)現(xiàn)分為以下3步。在待排序數(shù)組中找出最大值max和最小值min并根據(jù)“bucketNummax-min/arr.length1”創(chuàng)建桶。遍歷待排序的數(shù)組arr計(jì)算每個(gè)元素arr[i]的大小并放入桶中。對(duì)每個(gè)桶各自排序在每個(gè)桶的內(nèi)部排序完成后就得到了完整的排序數(shù)組。8、基數(shù)排序算法基數(shù)排序Radix Sort算法是桶排序算法的擴(kuò)展它將數(shù)據(jù)按位切割為不同的數(shù)字位數(shù)不夠的補(bǔ)0然后在每個(gè)位數(shù)上分別進(jìn)行比較最終得到排好序的序列。8.1、基數(shù)排序算法的原理基數(shù)排序算法的原理是將所有待比較數(shù)據(jù)統(tǒng)一為同一長度在位數(shù)不夠時(shí)前面補(bǔ)零然后從低位到高位根據(jù)每個(gè)位上整數(shù)的大小依次對(duì)數(shù)據(jù)進(jìn)行排序最終得到一個(gè)有序序列。如圖所示為對(duì)數(shù)組[1,56,7,5,304,12,102,45,183,3,345,123]進(jìn)行基數(shù)排序先將數(shù)組中的所有元素補(bǔ)為三位數(shù)并進(jìn)行按位分割之后分別按照個(gè)位、十位、百位進(jìn)行排序最終就得到了排序后的數(shù)組。8.2、基數(shù)排序算法的Java實(shí)現(xiàn)基數(shù)排序算法的Java實(shí)現(xiàn)如下//array數(shù)組 maxigit數(shù)組最大位數(shù)privatestaticint[]radixSort(int[]array,intmaxDigit){//數(shù)組最大位數(shù)的數(shù)據(jù)上限比如3位數(shù)的最大上限為1000doublemaxMath.pow(10,maxDigit1);intn1;//代表位數(shù)對(duì)應(yīng)的數(shù)1,10,100……intk0;//保存每一位排序后的結(jié)果用于下一位的排序輸入intlengtharray.length;//bucket用于保存每次排序后的結(jié)果將當(dāng)前位上排序結(jié)果相同的數(shù)字放在同一個(gè)桶里int[][]bucketnewint[10][length];int[]ordernewint[length];//用于保存每個(gè)桶里有多少個(gè)數(shù)字while(nmax){for(intnum:array)//將數(shù)組array里的每個(gè)數(shù)字都放在相應(yīng)的桶里{intdigit(num/n)%10;bucket[digit][order[digit]]num;order[digit];}//將前一個(gè)循環(huán)生成的桶里的數(shù)據(jù)覆蓋到原數(shù)組中用于保存這一位的排序結(jié)果for(inti0;ilength;i){//在這個(gè)桶中有數(shù)據(jù)從上到下遍歷這個(gè)桶并將數(shù)據(jù)保存到原數(shù)組中if(order[i]!0){for(intj0;jorder[i];j){array[k]bucket[i][j];k;}}order[i]0;//將桶中的計(jì)數(shù)器設(shè)置為0用于下一次位排序}n10;k0;//將k設(shè)置為0用于下一輪保存位排序結(jié)果}returnarray;}以上代碼定義了名為radixSort()的基數(shù)排序方法在該方法中array為待排序數(shù)組maxDigit為數(shù)組的最大位數(shù)。并且在該方法中定義的max代表數(shù)組最大位數(shù)的數(shù)據(jù)上限用于控制while循環(huán)排序的趟次n代表位數(shù)個(gè)位為1十位為10; k保存每一位排序后的結(jié)果用于下一位的排序輸入bucket數(shù)組為排序桶用于保存每次排序后的結(jié)果將當(dāng)前位上排序結(jié)果相同的數(shù)字放在同一個(gè)桶里order數(shù)組用于保存每個(gè)桶里有多少個(gè)數(shù)字。具體做法是在while循環(huán)中先取出當(dāng)前位的數(shù)據(jù)放入排序桶中然后將排序桶的數(shù)據(jù)覆蓋到原數(shù)組中用于保存這一位的排序結(jié)果接著從上到下遍歷這個(gè)桶并將數(shù)據(jù)保存到原數(shù)組中這樣便完成了當(dāng)前位的排序。假設(shè)數(shù)組最大有N位則進(jìn)行N1次while循環(huán)便完成了所有位數(shù)個(gè)位、十位、百位……上的排序。9、其他算法9.1、剪枝算法剪枝算法屬于算法優(yōu)化范疇通過剪枝策略提前減少不必要的搜索路徑。在搜索算法的優(yōu)化中剪枝算法通過某種預(yù)判去掉一些不需要的搜索范圍從直觀上理解相當(dāng)于剪去了搜索樹中的某些“枝條”?故稱剪枝。剪枝優(yōu)化的核心是設(shè)計(jì)剪枝預(yù)判方法即哪些“枝條”被剪掉后可以縮小搜索范圍提高搜索效率而又不影響整體搜索的準(zhǔn)確性。如圖所示為在二叉樹的查找過程中提前判斷元素48不可能在左側(cè)樹中將其剪枝以減少搜索范圍。剪枝優(yōu)化有三個(gè)原則正確、準(zhǔn)確、高效。正確剪枝的前提是保證不丟失正確的結(jié)果。準(zhǔn)確在保證正確性的基礎(chǔ)上應(yīng)該根據(jù)具體的問題采用合適的判斷手段使不包含最優(yōu)解的枝條盡可能多地被剪去以達(dá)到程序快速最優(yōu)化的目的。剪枝是否準(zhǔn)確是衡量優(yōu)化算法優(yōu)劣的標(biāo)準(zhǔn)。高效指盡可能減少搜索的次數(shù)使程序運(yùn)行的時(shí)間減少。剪枝算法按照其判斷思路可分為可行性剪枝和最優(yōu)性剪枝?？尚行约糁υ摲椒ㄅ袛嘌刂硞€(gè)路徑能否搜索到數(shù)據(jù)如果不能則直接回溯。最優(yōu)性剪枝又稱上下界剪枝記錄當(dāng)前得到的最優(yōu)值在當(dāng)前節(jié)點(diǎn)無法產(chǎn)生比當(dāng)前最優(yōu)解更優(yōu)的解時(shí)可以提前回溯。9.2、回溯算法回溯算法是一種最優(yōu)選擇搜索算法按選優(yōu)條件向前搜索以達(dá)到目標(biāo)。如果在探索到某一步時(shí)發(fā)現(xiàn)原先的選擇并不是最優(yōu)或達(dá)不到目標(biāo)就退一步重新選擇這種走不通就退回再走的方法叫作回溯法而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)叫作回溯點(diǎn)。如圖所示為經(jīng)歷了[10,4,5,8]的線路后未找到需要的數(shù)據(jù)則回溯到根節(jié)點(diǎn)以另一條線路重新查找。9.3、最短路徑算法最短路徑算法指從某頂點(diǎn)出發(fā)沿著圖的邊到達(dá)另一頂點(diǎn)在途中可選的路徑中各邊上權(quán)值之和最小的一條路徑叫作最短路徑。解決最短路徑問題的方法有Dijkstra算法、Bellman-Ford算法、Floyd算法和SPFA算法等。如圖所示為從起點(diǎn)A到終點(diǎn)F有3條路徑路徑1為?[A, B, D, C]?路徑2為?[A, F]?路徑3為?[A, E, F]?。在各條邊權(quán)重相等的情況下路徑2顯然為最短路徑。最短路徑算法的常見問題如下。確定起點(diǎn)的最短路徑問題即已知起始節(jié)點(diǎn)求最短路徑的問題適合使用Dijkstra算法。確定終點(diǎn)的最短路徑問題已知終節(jié)點(diǎn)求最短路徑的問題。在無向圖中該問題與確定起點(diǎn)的問題等同在有向圖中該問題與將所有路徑方向反轉(zhuǎn)以確定起點(diǎn)的問題等同。確定起點(diǎn)和終點(diǎn)的最短路徑問題已知起點(diǎn)和終點(diǎn)求兩節(jié)點(diǎn)之間的最短路徑。全局最短路徑問題求圖中所有的最短路徑適合使用Floyd-Warshall算法。