算法設計實例教程 課件 第3、4章 排序算法-算法設計實例教程、查找-算法設計實例教程

算法設計實例教程教學分析目錄CONCENTS123456789第3章排序算法第1章數據結構基礎第2章基礎算法第4章查找第5章字符串和高精度運算第6章圖論算法第7章動態(tài)規(guī)劃算法第8章計算幾何基礎第9章高級算法排序算法是算法設計中最基本的算法之一。排序算法可以分為內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。第3章排序算法排序算法的穩(wěn)定性：如果兩個數值相等的數，在排序前和排序后能保持兩個數在序列中前后位置順序不變的排序算法稱為穩(wěn)定排序，否則為不穩(wěn)定排序。例如，有Ai=Aj，排序前Ai在Aj的前面，排序后Ai仍然還在Aj的前面，這時候就稱為穩(wěn)定排序，否則，就稱為不穩(wěn)定排序。時間復雜度：對排序數據的總操作次數。反映當n變化時，操作次數呈現什么規(guī)律?？臻g復雜度：指算法在計算機內執(zhí)行時所需存儲空間的度量，它也是數據規(guī)模n的函數。3.1排序的相關概念冒泡排序（BubbleSort）是一種簡單實用的排序算法。它是從隊列首部開始，依次比較兩個相鄰的數據，如果順序錯誤就把它們進行交換，直至沒有數據可以交換為止。在這個過程中，待排序的元素會經由交換慢慢“浮”到數列的頂端，就如同水池中的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。3.2冒泡排序在使用冒泡排序時，首先應該確定是進行升序排序還是降序排序。升序排序就是將待排列的數據按照從小到大的順序排序，當升序排序時，需要較大的數向后“沉”，而將較小的數向前“冒”。降序排序則正好相反，它是將待排列得數據按照從大到小的順序排序，它需要較小的數向后“沉”，而將較大的數向前“冒”。第1步：比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。第2步：對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。這步做完后，最后的元素會是最大的數。第3步：針對所有的元素重復以上的步驟，除了最后一個。第4步：持續(xù)每次對越來越少的元素重復步驟1~3，直到沒有任何一對數字需要比較。3.2.1冒泡排序算法描述例如，將序列“5，4，3，2，1”變成升序“1，2，3，4，5”的“冒泡排序”的示意圖如圖3.1。從圖中可以看出隨著“5”逐漸“沉”下去，“1”逐漸“冒”了上來。重復沉“4”“3”“2”“1”會冒到最頂上。3.2.1冒泡排序算法描述圖3.1冒泡原理示意【例3.1】冒泡排序時間限制：1000ms內存限制：32MB問題描述編寫一個程序：從鍵盤上輸入整數個數n（n<255），按照冒泡排序的思想，對n個整數進行升序排序，最后輸出排序結果。輸入說明輸入的數據之間空一格，最后一個回車。輸出說明打印輸出的時候空一格。輸入樣例9876543210輸出樣例01234567893.2.2冒泡排序程序實現舉例問題分析：首先需要建立一個int類型的數組arr存儲待排序數據，然后利用冒泡排序對數組中的數據進行排序。如果是n個數排序，共需要n-1輪排序。這就需要建立一個循環(huán)結構。設置一個循環(huán)控制變量i，通過控制變量i實現n-1輪排序。令i=1作為循環(huán)的初始條件，用“i<=n-1”作為循環(huán)控制表達式，用“i++”作為循環(huán)控制變量的改變。循環(huán)體完成數組的每輪排序比較。循環(huán)語句如下：for(i=1;i<=n-1;i++){//每輪比較的程序代碼}冒泡排序使用了兩層循環(huán)嵌套，外層循環(huán)稱為遍歷。例如，第一輪遍歷就是外層循環(huán)的第一次迭代。在每次內層循環(huán)的迭代過程中，對列表中剩余的未排序元素進行排序，直到最高值冒泡到最后為止。第一輪遍歷將進行N-1次比較，第二輪遍歷將進行N-2次比較，而每輪后續(xù)遍歷將比前一輪減少一次比較操作。當待排序序列是有序的時候（最好情況），比較次數為n-1次，沒有數據交換，此時時間復雜度為O(n)；當待排序序列是逆序的時候（最壞的情況），當初始序列從大到小逆序時，需要進行n-1趟排序，進行n(n-1)/2次比較和交換，此時的時間復雜度為O(n2)?？臻g復雜度：冒泡排序只需要一個臨時變量來交換數據，所以為O(1)。3.2.3冒泡排序算法分析選擇排序(SelectionSort)是一種簡單直觀的排序算法。它的基本思想：首先在待排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

3.3選擇排序（SelectionSort）n個記錄的選擇排序可經過n-1輪選擇排序得到有序結果。具體算法描述如下：3.3.1選擇排序算法描述第1步：待排序序列為R[1..n]，有序序列為空；第2步：第i趟排序(i=1,2,3…,n-1)開始時，當前有序序列和無序序列（待排序列）分別為R[1..i-1]和R(i..n）。該趟排序從當前無序序列中選出關鍵字最小的記錄R[k]，將它與無序序列的第1個記錄R交換，使R[1..i]和R(i+1..n)分別變?yōu)橛涗泜€數增加1個的新有序序列和記錄個數減少1個的新無序序列；第3步：n-1趟結束，數組有序了。

例如，將序列“53，64，28，72，1”變成升序“1，28，53，64，72”的“選擇排序”的第一輪操作如圖3.3所示。從圖中可以看出隨著待排序序列中的元素“1”首先被“選擇”出來與數組下標為0的元素“53”交換位置，然后在待排序序列“64，28，72，53”中繼續(xù)“選擇”最小的元素“28”與數組下標為1的元素“64”交換位置，重復相同的操作，直至待排序序列完全有序。

圖3-3第一輪選擇排序示意圖3.3.1選擇排序算法描述【例3.2】選擇排序時間限制：1000ms內存限制：32MB問題描述編寫一個算法實現選擇排序思想，并將亂序數列變成升序數列。輸入說明第一行輸入數據元素的個數，第二行為待排序的數據元素，輸入的數據之間空一格，最后一個回車。輸出說明打印輸出的時候空一格，尾數后沒有空格。輸入樣例1071468952310輸出樣例12345678910

3.3.2選擇排序算法實現舉例3.3.2選擇排序算法實現舉例問題分析根據題意和選擇排序的基本思想，可以定義變量n存儲待排序的元素個數，然后根據第一行輸入的數值n動態(tài)分配存儲空間大小arr=(int*)malloc(sizeof(int)*n)，而在選擇排序的過程中，在每一輪排序中找到數值最小的元素，并臨時存儲在minIdx中，直到本輪循環(huán)結束for(inti=0;i<n-1;i++){intminIdx=i;for(intj=i+1;j<n;j++){if(arr[minIdx]>arr[j]){minIdx=j;}}后把值最小元素“放”到arr[i]的位置。temp=arr[minIdx];arr[minIdx]=arr[i];arr[i]=temp;選擇排序是一種簡單直觀的排序算法，無論待排序序列是正序還是逆序，每?輪的最?（最大）值都需要?較到最后才能確定，那么，最壞情況和最好情況下都需要?較n-1次，再加上遍歷整個序列的O(n)，總的復雜度為O(n2)，平均復雜度也是O(n2)。所以，選擇排序比較適合數據規(guī)模不大的情形?？臻g復雜度方面，選擇排序只需要?個額外用來存放“臨時最?值”的空間，除此之外，不占用額外的內存，所以空間復雜度為O(1)，同時，選擇排序是不穩(wěn)定排序。。

3.3.3選擇排序算法分析插入排序（Insertion-Sort）是一種簡單直觀的排序算法。它的工作原理是將未排好序的元素?個個地插?到已排好序（開始時為空）的序列中，插?時，需要與已排好序的元素進?多次?較，直到找到合適（比前一個元素大，比后一個元素小或者比前一個元素小，比后一個元素大）的位置插?，?原來已排好序的部分元素可能需要進?后移操作，最后形成有序序列。

3.4插入排序（InsertionSort）第4步：重復步驟3，直到找到已排序的元素小于或者等于新元素的位置；第6步：重復步驟2~5，直到序列有序。

第5步：將新元素插入到該位置后；第2步：取出下一個元素，在已經排序的元素序列中從后向前掃描；第1步：從第一個元素開始，此時，只有一個元素，該元素可以看作已排序；第3步：如果該元素（已排序）大于新元素，將該元素移到下（后移）一位置；一般來說，插入排序一般都采用in-place在數組上實現。具體算法描述如下：3.4.1插入排序算法描述例如，將序列“5，4，3，2，1”變成升序“1，2，3，4，5”的“插入排序”的操作如圖3.4所示。3.4.1插入排序算法描述圖3-4插入排序示意圖【例3.4】插入排序時間限制：1000ms內存限制：32MB問題描述實現插入排序算法，并將亂序數列變成升序數列。輸入說明第一行輸入數據元素的個數，第二行為待排序的數據元素，輸入的數據之間空一格，最后一個回車。輸出說明打印輸出的時候空一格，尾數后沒有空格。輸入樣例1023846815473271450輸出樣例234152347685071843.4.2插入排序算法實現舉例3.4.2插入排序算法實現舉例算法分析定義兩個變量i和j分別的控制外層循環(huán)和內層循環(huán)，然后依次取出待排序序列中的各個元素存儲在val中，用val與未排序序列中元素arr[j]比較，直到找到val的“位置”，經過n1輪排序即可得到有序序列，核心參考代碼如下：1voidsort_array(int*arr,intn)

2{

3for(inti=1;i<n;i++){

4intval=arr[i];

5for(intj=i-1;j>=0;j--){

6if(val<arr[j]){//待插入的元素小于當前元素的值，7arr[j+1]=arr[j];//當前元素向后移動一個位置8arr[j]=val;

9}

10else{

11break;

12}

13}

14}

15}空間復雜度：插入排序在實現上，一般采用in-place在數組上實現，即只需用到O(1)的額外空間，因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。時間復雜度：最壞情況：當待排序序列正好為逆序狀態(tài)，?先遍歷整個序列，然后?個個地將待插?元素放在已排序的序列最前?，之后的所有元素都需向后移動?位，所以?較和移動的時間復雜度都是O(n)，再加上遍歷整個序列的復雜度，總復雜度為O(n2)。最好情況：當待排序序列正好為正序狀態(tài)，則遍歷完整個序列，當插?元素時，只?較?次就夠了，所以時間復雜度為O(n)。平均情況：當被插?的元素放在已排序的序列中間位置時，為平均情況，?較和移動的時間復雜度為O(n2)，所以總的時間復雜度依然為O(n2)。穩(wěn)定性：插?排序的?較是從有序序列的末尾開始，也就是想要插?的元素和已經有序的最?者開始?起，如果?它?則直接插?在其后?，否則?直往前找直到找到它該插?的位置。如果遇見?個和插?元素值相等的，那么插?元素把想插?的元素放在相等元素的后?。值相等元素的前后順序沒有改變，所以插?排序是穩(wěn)定的。3.4.3插入排序算法分析歸并排序是建立在歸并操作上的一種有效的排序算法。其基本思想是將已有序的子序列合并，得到完全有序的序列，即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并。歸并排序算法是基于分治策略而設計的。在被稱為劃分的第一階段中，算法將數據遞歸地分成兩部分，直到數據的規(guī)模小于定義的閾值。在被稱為歸并的第二階段中，算法不斷地進行歸并和處理，直到得到最終的結果。3.5歸并排序（MergeSort）3.5.1歸并排序算法描述01第1步：把長度為n的輸入序列分成兩個長度為n/2的子序列；02第2步：對這兩個子序列分別采用歸并排序；03第3步：將兩個排序好的子序列合并成一個最終的排序序列。例如：將待排序序列[25,6,93,17,41,86,32,79,58]排成升序序列[6,17,25,32,41,58,79,86,93]的歸并操作如圖3.5所示。3.5.1歸并排序算法描述圖3-5歸并排序示意圖【例3.6】合并兩個序列時間限制：1000ms內存限制：32MB問題描述輸入兩個遞增的序列，輸出合并這兩個序列后的遞增序列。輸入說明每個測試案例包括3行：第一行為1個整數n（1<=n<=1000000）表示這兩個遞增序列的長度。第二行包含n個整數，表示第一個遞增序列。第三行包含n個整數，表示第二個遞增序列。輸出說明對應每個測試案例，輸出合并這兩個序列后的遞增序列。輸入樣例413572468輸出樣例12345678。3.5.2歸并排序算法實現舉例：算法分析將兩個遞增序列合并成為一個遞增序列，常規(guī)的操作是將第二個遞增追加到第一個遞增序列的后面，然后進行冒泡排序就可以得到一個遞增序列。但是，當問題規(guī)模增大時，時間復雜度急劇增加，本題嘗試用歸并排序思想來解決。因歸并的方法采用了分治的策略，性能大大提升，歸并排序和選擇排序一樣，性能不受輸入數據的影響，但其性能比選擇排序大大提升，因為其時間復雜度一直為O(nlogn），不過，帶來的代價是需要額外的內存空間。時間復雜度：歸并排序的時間主要消耗在劃分序列和合并序列上，由于采?遞歸?式進?合并，如果集合長度為n，那么劃分的層數就是logn，每一層進行歸并操作的運算量是n。所以，歸并排序的時間復雜度等于每一層的運算量×層級數，即O(nlogn)，?且不管元素是否基本有序都需要進行類似操作，所以該算法的最優(yōu)時間復雜度和最差時間復雜度及平均時間復雜度都相同?？臻g復雜度：歸并排序是需要用到額外空間的，但是每次歸并所創(chuàng)建的額外空間都會隨著方法結束而釋放，因此單次歸并操作開辟的最大空間是n。所以，歸并排序的空間復雜度是O(n)。歸并排序是穩(wěn)定排序算法。3.5.3歸并排序算法分析快速排序和冒泡排序一樣，也是交換類排序?法。其基本思想是通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。3.6快速排序（QuickSort）快速排序使用分治法來把一個序列分為兩個子序列。具體算法描述如下：3.6.1快速排序算法描述第1步：從數列中挑出一個元素，稱為“基準”（pivot）；第2步：將所有元素比基準值小的集中在基準左邊（或者右邊），所有元素比基準值大的集中在基準的右邊（或者左邊，相同的數可以到任一邊）。在這個分區(qū)退出之后，該基準就處于數列的中間位置，這個稱為分區(qū)（partition）操作；第3步：采用遞歸（recursive）思想把小于基準值元素的子數列和大于基準值元素的子數列排序再一次進行快速排序。第4步：重復以上過程，直到序列有序。例如：將待排序序列[59,16,83,97,21,45,3,74,68]排成升序序列[3,16,21,45,59,68,74,83,97]的快速排序的第一輪操作如圖3.6所示?？焖倥判虮闅v開始的時候是從后面j往前遍歷，當元素值大于pivot時j--；元素值小于pivot時，j保持不變，并且將j指向的值替換i指向的值，i++；這時，i從前往后遍歷，小于pivot的值就i++；遇到大于pivot的元素時，i不變，并且將i指向的值替換j指向的值，j--，這樣交替進行，直到i和j指向同一位置。3.6.1快速排序算法描述圖3-6快速排序的第一輪操作示意圖【例3.7】快速排序時間限制：1000ms內存限制：32MB問題描述用遞歸法實現快速排序算法，并將亂序數列變成升序。輸入說明第一行輸入數據元素的個數，第二行為待排序的數據元素，輸入的數據之間空一格，最后一個回車。輸出說明打印輸出的時候空一格，尾數后沒有空格。輸入樣例108536236729641195078輸出樣例21923364150677885963.6.2快速排序算法實現舉例算法分析定義兩個變量i和j為數組的下標，最開始時i=0，j=n-1，取出待排序序列中的第一個元素a[0]作為“基準”，即pivot=a[0]，然后從數組的最后一個元素開始依次與pivot比較，直到找到比pivot小的元素并且交換位置，同時i++，這時從數組元素a[i]開始依次與pivot依次比較，直到找到比pivot大的元素并且交換位置，如此交替進行直到i==j。第一輪快速排序結束，得到序列是以pivot為基準，左邊的元素都比pivot小，右邊的元素都比pivot大的序列。以此為基礎，進一步對pivot的左右兩側的子序列進行重復的操作直至整個序列保持有序。時間復雜度：最壞情況時，每?次選取的基準元素都是最?或最?的，復雜度為O(n2)，最好情況時，每?次選取的基準元素都能平分整個序列，由于快排涉及到遞歸調?，所以時間復雜度為O(nlog2n)。平均情況下復雜度也是O(nlog2n)?？臻g復雜度：快速排序使?的輔助空間是O(1)，?消耗空間較大的是在遞歸調?的時候了，因為每次遞歸就要保留?些數據，每?次都平分數組的情況下空間復雜度為O(logn)，最差的情況下空間復雜度為O(n)，快速排序是不穩(wěn)定排序。3.6.3快速排序算法分析排序算法通常可以分為比較類排序和非比較類排序，冒泡排序、快速排序、插入排序、希爾排序、選擇排序、堆排序、歸并排序都屬于比較類排序，而計數排序、基數排序和桶排序都屬于非比較類排序。每一種排序算法都有特定的使用情形，一般來說，選擇合適的排序算法既取決于當前輸入數據的規(guī)模，也取決于當前輸入數據的狀態(tài)。對于基本有序且規(guī)模較小的輸入列表，使用高級算法會給代碼帶來不必要的復雜度，而性能的提升可以忽略不計。例如，對于較小的數據集，一般不使用歸并排序，冒泡排序更容易理解和實現。如果數據已經被部分排好序了，則可以使用插入排序。對于較大的數據集，歸并排序算法是最好的選擇。表3-1為常見排序算法的時間復雜度和空間復雜度以及穩(wěn)定性情況。3.7排序算法的性能比較3.7排序算法的性能比較排序方法時間復雜度（平均）時間復雜度（最壞）時間復雜度（最好）空間復雜度穩(wěn)定性冒泡排序O(n2)O(n2)O(n)O(1)穩(wěn)定選擇排序O(n2)O(n2)O(n2)O(1)不穩(wěn)定插入排序O(n2)O(n2)O(n)O(1)穩(wěn)定歸并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)穩(wěn)定快速排序O(nlog2n)O(n2)O(nlog2n)O(nlog2n)不穩(wěn)定基數排序O(n*k)O(n*k)O(n*k)O(n+k)穩(wěn)定希爾排序O(n1.3-2)O(n2)O(n)O(1)不穩(wěn)定堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不穩(wěn)定計數排序O(n+k)O(n+k)O(n+k)O(n+k)穩(wěn)定桶排序O(n+k)O(n2)O(n)O(n+k)穩(wěn)定表3-1常見排序算法性能情況3.8本章小結排序是算法設計中一種重要的操作，其主要功能就是對一個待排序序列進行重新排列成按照數據元素某個屬性值有序的序列。實現排序的兩個基本操作：（1）比較。“比較”待排序序列中兩個關鍵字的大??；（2）移動?！耙苿印庇涗洝Ｕ绫菊鹿?jié)開始所介紹的常見的排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。每種排序算法都有自己特點和適用場景，那么如何選擇一種排序算法呢？一般來說：當待排序列中元素很少的時候，適合選用插入排序；當待排序列中所有的元素幾乎有序，也比較適合選用插入排序；而如果著重考慮排序算法最壞情況，適合選用堆排序；當希望排序算法的平均性能比較好時，選用快速排序比較合適；當待排序列中元素從一個密集幾何中抽取出的時候，適合選用桶排序；如果期望編寫的代碼盡可能簡練，選擇插入排序比較合適3.8本章小結算法設計實例教程教學分析目錄CONCENTS123456789第4章查找第1章數據結構基礎第2章基礎算法第3章排序算法第5章字符串和高精度運算第6章圖論算法第7章動態(tài)規(guī)劃算法第8章計算幾何基礎第9章高級算法查找也稱搜索，搜索算法是利用計算機的高性能來有目的的窮舉一個問題解空間的部分或所有的可能情況，從而求出問題的解的一種方法。現階段一般有枚舉算法、深度優(yōu)先搜索、廣度優(yōu)先搜索、A*算法、回溯算法、蒙特卡洛樹搜索、散列函數等算法。在大規(guī)模實驗環(huán)境中，通常通過在搜索前，根據條件降低搜索規(guī)模；根據問題的約束條件進行剪枝；利用搜索過程中的中間解，避免重復計算這幾種方法進行優(yōu)化。第4章查找4.1.1順序查找的基本概念

順序查找算法又稱順序搜索算法或者線性搜索算法，是所有查找算法中最基本、最簡單的，對應的時間復雜度為O(n)。順序查找算法適用于絕大多數場景，既可以在有序序列中查找目標元素，也可以在無序序列中查找目標元素。其基本思想是從線性表的第1個元素開始，通過逐個比較表中的關鍵字，直到找到符合要求的關鍵字，完成查找，或搜索整個表，沒有找到符合要求的關鍵字，則表示查找失敗。但是這種查找方法的效率較低，主要針對數量較少，無規(guī)則的數據。如果查找表中的數據已經按順序排列，則可以使用一種稱為二分查找的方法。。4.1順序查找時間限制：1000ms內存限制：65535KB問題描述輸入10個數，要求輸出其中的最大值。輸入說明測試數據有多組，每組10個數。輸出說明對于每組輸入,請輸出其最大值（有回車）。輸入樣例102223152657985963240輸出樣例max=1524.1.2順序查找的應用舉例1：找最大值

算法分析創(chuàng)建一個數組以及創(chuàng)建一個變量max，給變量max賦初值為然后跟數組中每個元素一一進行判斷，如果數組中的數比max大那么把這個數賦給max，以此類推，直到查找完數組中的所有元素即可完成查找，停止運算。實現的代碼如下：intmain(){intd[10],i,max;for(i=0;i<10;i++)scanf("%d",&d[i]);max=d[0];for(i=1;i<10;i++){if(max<d[i])max=d[i];}printf("max=%d\n",max);return0;}時間限制：1000ms內存限制：32MB問題描述輸入一行字符串，計算其中A-Z大寫字母出現的次數。輸入說明案例可能有多組，每個案例輸入為一行字符串。輸出說明對每個案例按A-Z的順序輸出其中大寫字母出現的次數。輸入樣例DFJEIWFNQLEF0395823048+_+JDLSFJDLSJFKK4.1.3順序查找的應用舉例2：字母統(tǒng)計

輸出樣例A:0B:0C:0D:3E:2F:5G:0H:0I:1J:4K:2L:3M:0N:1O:0P:0Q:1R:0S:2T:0U:0V:0W:1X:0Y:0Z:04.1.3順序查找的應用舉例2：字母統(tǒng)計

算法分析該問題的策略就是建立一個長度為26的整型數組用來統(tǒng)計每個字母的出現次數，然后依次遍歷字符串中的每一個字符，對字符進行判斷，如果該字符是某個字母，就將該字母對應的統(tǒng)計數據加1。代碼如下：intmain(){charstr[10000]={0};intcount[26]={0};inti;while(scanf("%s",str)!=EOF){for(i=0;i<strlen(str);i++){if('A'<=str[i]&&str[i]<='Z'){count[str[i]-'A']++;}}for(i=0;i<26;i++){printf("%c:%d\n",'A'+i,count[i]);}}return0;}4.2.1二分查找的基本概念二分查找又稱折半查找、二分搜索、折半搜索等，是一種采用了分治策略的查找算法。二分查找只能用于有序線性表的查找。假設在一個長度為n的有序數組中查找一個數字，如果使用順序查找的方式逐一檢查數組中的每個數字，那么需要O（n）的時間復雜度，而如果使用二分查找，時間復雜度可以優(yōu)化到O（logn）。隨著線性表的規(guī)模n越大，二分查找在時間性能上的優(yōu)越性就會越明顯。4.2二分查找

4.2.1二分查找的基本概念二分查找的查找策略是：每次將位于線性表中間的數字和目標數字比較。如果中間數字正好等于目標數字，那么就找到了目標數字。如果中間數字大于目標數字，那么下一次查找的時候只需要在線性表的前半部分找，這是因為線性表是排序的，后半部分的數字都大于或等于中間數字，所以一定都大于目標數字，也就沒有必要再在后半部分查找。如果中間數字小于目標數字，那么接下來只需要查找線性表的后半部分，這是因為排序數組的前半部分的數字都小于或等于中間數字，所以一定都小于目標數字，也就沒有必要再在前半部分查找。從查找的過程可以看出，二分查找是一種遞歸的過程。由于二分查找算法每次都將查找范圍減少一半，對于包含n個元素的列表，用二分查找最多需要log2n步。但是由于二分查找要求待查找的數據必須是線性有序的，對于沒有經過排序的數據，可以通過排序算法進行預排序，然后進行二分查找的操作。4.2二分查找

時間限制：1000ms內存限制：65535KB問題描述有n個已經從小到大排序好的數據（不重復），從鍵盤輸入一個數，用二分查找方法，判斷target是否在這n個數中。輸入說明第1行，數組的長度length第2行，n個整數（int范圍內，不重復），中間用空格分隔；第3行，整數target。輸出說明如果找到target，輸出其位置；否則輸出-1。4.2.2二分查找的應用舉例1：查找元素x

輸入樣例10102030405060708090100906-10359122輸出樣例8-1算法分析使用二分查找算法在一個已排序（升序）的數組中查找一個指定的元素，首先將這個待查找元素與數列中位于中間位置的元素進行比較，如果比中間位置的元素大，則繼續(xù)在后半部分的數列中進行二分查找；如果比中間位置的元素小，則在數列的前半部分進行比較；如果相等，則找到了元素的位置。每次比較的數列長度都會是之前數列的一半，直到找到相等元素的位置或者最終沒有找到要找的元素。1.循環(huán)方式intsearch_loop(inta[],intsize,inttarget){intleft=0,mid;intright=size-1;while(left<=right){mid=left+(right-left)/2;//定位查找區(qū)間的中間元素if(a[mid]>target)right=mid-1;//待查元素在mid元素的左邊區(qū)域elseif(a[mid]<target)left=mid+1;//待查找元素在mid元素的右邊區(qū)域else//a[mid]就是要查找的元素returnmid;}return-1;//沒有找到目標值}4.2.2二分查找的應用舉例1：查找元素x

在上面的函數定義中，分別使用了left和right兩個變量記住查找的范圍。初始情況下left為0，right為數組長度-1，分別指向數組的起始和結束位置。隨著查找的推進，每次都根據判斷的結果，更新left或者right的值，直到left>right就結束循環(huán)。如果直到循環(huán)結束都沒有找到目標值，則輸出-1。2.遞歸方式由于每次查找的方法是一樣的，不一樣的僅僅是查找的數組的范圍，因此遞歸是一種很直觀的實現方式。用一對整數變量表示目標元素的查找區(qū)間的起始和結束位置，并作為參數傳遞給遞歸函數。隨著查找范圍的不斷縮小，直到查找區(qū)間包含的元素個數少于或等于1個，查找就停止了。實現代碼如下：intsearch_recur(inta[],intleft,intright,inttarget){intmid;if(left>right)return-1;//沒有找到目標值mid=left+(right-left)/2;//定位查找區(qū)間的中間元素if(a[mid]>target)search_recur(a,left,mid-1,target);//遞歸地查找mid左邊區(qū)域elseif(a[mid]<target)search_recur(a,mid+1,right,target);//遞歸地查找mid右邊區(qū)域else//a[mid]就是要查找的元素returnmid;}4.2.2二分查找的應用舉例1：查找元素x

4.2.2二分查找的應用舉例1：查找元素

遞歸的優(yōu)勢就是代碼簡潔，且能夠直觀的對應解決問題的思路，但存在的問題是內存消耗太大。main函數實現如下：intmain(){intlength,target,i;while(scanf("%d",&length)!=EOF){for(i=0;i<length;i++)scanf("%d",&a[i]);scanf("%d",&target);printf("%d\n",search_recur(a,0,length-1,target));}return0;}時間限制：1000ms內存限制：65535KB問題描述統(tǒng)計一個數字在一個有序數組中出現的次數。比如輸入一個有序數組{1,2,2,2,3,3,3,4,5}和數字2，由于2在數組中出現了3次，因此程序的輸出結果為3。輸入說明第1行，數組的長度第2行，一個有序數組{1,2,2,2,3,3,3,4,5}第3行，1個待查找的整數target。輸出說明如果數組中包含target，則輸出其在數組中出現的次數位置；否則輸出0。輸入樣例1012223334552輸出樣例34.2.3二分查找的應用舉例2：統(tǒng)計數字在有序數組中出現的次數

4.2.3二分查找的應用舉例2：統(tǒng)計數字在有序數組中出現的次數

算法分析一種直觀的方式是使用順序查找的方式遍歷整個數組，只要找到某個元素目標元素target相等，則統(tǒng)計值加1。由于對數組的n個元素都進行了一次檢查，所以該算法的時間復雜度為O(n)。使用二分查找在數組中查找元素target在數組中的位置，由于數組是有序的，因此所有相等的值在數組中的位置是連續(xù)的，因此可以繼續(xù)在該位置的前后查找與target相等的元素。前面已經分析過，二分查找能夠快速的縮小查找的范圍，將算法的時間復雜度降低到O(logn)。使用二分查找法進行數字統(tǒng)計的函數實現如下：intnum(inta[],intsize,inttarget){intleft=0,right=size-1,mid,sum=0;inti;while(left<=right){mid=left+(right-left)/2;//定位查找區(qū)間的中間元素if(a[mid]>target)right=mid-1;//待查元素在mid元素的左邊區(qū)域elseif(a[mid]<target)left=mid+1;//待查找元素在mid元素的右邊區(qū)域else//a[mid]就是要查找的元素{sum=1;//找到了一個目標元素break;}}for(i=mid+1;i<size&&a[i]==target;i++)//向左統(tǒng)計sum++;for(i=mid-1;i>0&&a[i]==target;i--)//向右統(tǒng)計sum++;returnsum;4.2.3二分查找的應用舉例2：統(tǒng)計數字在有序數組中出現的次數

在順序查找和二分查找中，算法要處理的數據以線性表的形式表示。在線性表中，數據元素之間是線性關系，每個數據元素只有一個直接前驅和一個直接后繼。但是在圖中，任意兩個數據元素之間都可能存在直接的關系，通常用節(jié)點表示數據元素，用連接兩個節(jié)點的邊表示數據元素之間的關系。圖的搜索算法通常用來解決基于狀態(tài)空間的搜索問題。所謂狀態(tài)就是為了區(qū)分不同事物而引入的一組數據元組，如X=[x1,x2,x3...xn]，其中每一個元素xi被稱為狀態(tài)分量。首先把問題表示轉化為一個由多個狀態(tài)組成的集合，如果可以通過一些定義好的運算使得某個狀態(tài)跳轉到下一個狀態(tài)，那么這兩個狀態(tài)之間就形成了一個關聯關系。所有的狀態(tài)，以及狀態(tài)之間的關聯關系就形成了一個拓撲圖。解題的過程就是對圖的搜索。對一個圖進行搜索意味著從圖中的一個節(jié)點開始，按照某種特定的順序依次遍歷圖中的邊，從而找到一條從起始節(jié)點到目標節(jié)點的路徑，或是遍歷圖中所有的節(jié)點，找到符合檢索要求的節(jié)點。按照搜索順序的不同，可以將搜索算法分為廣度優(yōu)先算法和深度優(yōu)先搜索。4.3圖的搜索

DFS（DepthFirstSearch），即深度優(yōu)先搜索。其搜索策略是：從圖中某節(jié)點v出發(fā)，沿著一條路徑一直搜索下去，當無法搜索時，回退到剛剛訪問過的節(jié)點。具體說來包括以下幾個步驟：4.3.1DFS的基本概念

（1）初始化圖中的所有節(jié)點，將它們都標記為未被訪問。（2）從圖中的某個節(jié)點v出發(fā)，訪問v并標記其已被訪問。（3）依次檢查v的所有鄰接點w，如果w未被訪問，則從w出發(fā)進行深度優(yōu)先遍歷（遞歸調用，重復步驟2～3），這一過程一直進行到已發(fā)現從出發(fā)節(jié)點可達的所有節(jié)點為止。（4）如果當前已經沒有未被訪問的鄰接節(jié)點時，則回退到上一步剛剛訪問過的節(jié)點，繼續(xù)重復步驟2~3。按照深度優(yōu)先搜索，當搜索到某一步時，發(fā)現原先的選擇并不是最優(yōu)或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術被稱為回溯法，而滿足回溯條件的某個狀態(tài)被稱為“回溯點”。4.3.1DFS的基本概念

按照深度優(yōu)先搜索算法遍歷圖中的節(jié)點，我們會發(fā)現后被訪問的節(jié)點，其鄰接點先被訪問，這是典型的后來者先服務，可以借助于棧的結構來實現。由于遞歸本身就是使用棧實現的，因此使用遞歸的方法更方便。深度優(yōu)先搜索算法可以用以下偽代碼來表示：voidDFS(GraphG,nodev){nodew;visit(v);visited[v]=True;for(w=FirstNeighbor(G,v);w!=null;w=NextNeighbor(G,v))if(!visited[w])DFS(G,w);}從圖G中的某一個節(jié)點v開始，首先訪問節(jié)點v，并將v的狀態(tài)設置為已訪問。隨后依次對v的所有鄰接節(jié)點w進行遍歷，如果w是一個未被訪問過的節(jié)點，則繼續(xù)使用深度優(yōu)先搜索算法以w為出發(fā)節(jié)點進行搜索。由于算法是遞歸調用的，當v的某個鄰接節(jié)點w訪問不下去的時候，函數返回到v，繼續(xù)對v的下一個鄰接節(jié)點使用DFS展開搜索。。4.3.1DFS的基本概念

下面以下圖為例模擬深度優(yōu)先搜索算法的搜索路線。4.3.1DFS的基本概念

圖4-1二叉樹樹是圖的一種特殊形式，是連通且沒有回路的圖。圖中所示的是一棵二叉樹，即每個父節(jié)點最多只有兩個子節(jié)點，其中一個是左子節(jié)點，一個是右子節(jié)點?，F在我們要使用深度優(yōu)先算法遍歷樹中的每一個節(jié)點，那么節(jié)點編號所組成的序列就是遍歷的順序。假設我們規(guī)定對每一個節(jié)點來說，先訪問其左子節(jié)點，后訪問其右子節(jié)點。按照深度優(yōu)先搜索算法：（1）從根節(jié)點1開始（2）先訪問1的左子節(jié)點2，然后以遞歸的方式遍歷以2為根節(jié)點的子樹，以此類推，得到1→2→4→7遍歷序列。（3）到達節(jié)點7后，發(fā)現其沒有左子節(jié)點，也沒有右子節(jié)點，于是返回到節(jié)點4，節(jié)點4的也沒有右子節(jié)點，于是繼續(xù)向上返回到節(jié)點2，節(jié)點2有右子節(jié)點，于是訪問節(jié)點5，更新遍歷序列為1→2→4→7→5。（4）節(jié)點5既沒有左子節(jié)點，也沒有右子節(jié)點，于是返回到其父節(jié)點2。此時節(jié)點2完成了其所有子節(jié)點的遍歷，于是繼續(xù)向上返回到節(jié)點1。（5）此時節(jié)點1已完成了左節(jié)點的遍歷，繼續(xù)訪問其右節(jié)點3，更新遍歷序列為1→2→4→7→5→3。節(jié)點3沒有左子節(jié)點，于是訪問其右節(jié)點6，更新遍歷序列為1→2→4→7→5→3→6。（6）節(jié)點6先訪問左子節(jié)點8，由于節(jié)點8沒有子節(jié)點，于是完成訪問后返回節(jié)點6，然后訪問節(jié)點6的右子節(jié)點9，更新遍歷序列為1→2→4→7→5→3→6→8→9。同樣，由于節(jié)點9也沒有子節(jié)點，于是完成訪問后返回節(jié)點6。（7）節(jié)點6已完成其所有子節(jié)點的訪問，于是返回節(jié)點3，同樣，節(jié)點3也完成了所有子節(jié)點的訪問，于是返回節(jié)點1，完成所有節(jié)點的遍歷和遞歸訪問。得到結論，基于深度優(yōu)先搜索算法遍歷該樹的所有節(jié)點時，訪問序列為：1→2→4→7→5→3→6→8→9。4.3.1DFS的基本概念

BFS（BreadthFirstSearch），即廣度優(yōu)先搜索。其搜索策略是：從起點開始，對與其鄰接的所有節(jié)點都訪問一邊，然后依次從這些已經訪問過的鄰接點出發(fā)，再對它們的鄰接點進行訪問。具體說來包括以下幾個步驟：4.3.2BFS的基本概念

（1）初始化所有節(jié)點均未被訪問，并初始化一個空隊列。（2）從圖中的某個節(jié)點v出發(fā)，訪問v并標記其已被訪問，將v入隊列。（3）如果隊列非空，則繼續(xù)執(zhí)行，否則算法結束。（4）將隊頭元素v移出隊列，依次訪問v的所有未被訪問的鄰接點，標記已被訪問并將它們加入隊的尾部。轉向步驟3。按照廣度優(yōu)先搜索算法遍歷圖中的節(jié)點，我們會發(fā)現每次都是從隊列的頭部拿出一個節(jié)點進行擴展，而新擴展出的節(jié)點都是加到隊列的尾部，因此所有的節(jié)點按照先進先出的順序被訪問，可以借助于隊列的結構來實現。隊列是一種先進先出的數據結構，你不能隨機地訪問隊列中的元素。隊列只支持兩種操作：入隊和出隊。4.3.2BFS的基本概念

廣度優(yōu)先搜索算法可以用以下偽代碼來表示：voidBFS(GraphG,nodev){初始化一個空隊列queue;將nodev加入queue頭部；while(queue不為空){nodev=queue_front();visited[v]=True；pop_front(queue);for(w=FirstNeighbor(G,v);w!=null;w=NextNeighbor(G,v))if(!visited[w])將節(jié)點w加入queue尾部；}}下面依然以圖4-1為例模擬廣度優(yōu)先搜索算法的搜索路線。按照廣度優(yōu)先搜索算法：（1）隊列初始條件下為空queue={}；（2）從根節(jié)點1開始，將節(jié)點1放入隊列，得到隊列為{1}。（3）將隊列中的第一個元素1取出來，將其標記為已訪問，并將1的所有未訪問的鄰接節(jié)點放入隊列的尾部，隊列更新為{2，3}，訪問序列為1。（4）將隊列中的第一個元素2取出來，將其標記為已訪問，并將2的所有未訪問的鄰接節(jié)點放入隊列的尾部，隊列更新為{3，4，5}，訪問序列為1→2。（5）將隊列中的第一個元素3取出來，將其標記為已訪問，并將3的所有未訪問的鄰接節(jié)點放入隊列的尾部，隊列更新為{4，5，6}，訪問序列為1→2→3。（6）將隊列中的第一個元素4取出來，將其標記為已訪問，并將4的所有未訪問的鄰接節(jié)點放入隊列的尾部，隊列更新為{5，6，7}，訪問序列為1→2→3→4。4.3.2BFS的基本概念

（7）將隊列中的第一個元素5取出來，將其標記為已訪問，由于5沒有未訪問的鄰接節(jié)點，于是隊列更新為{6，7}，訪問序列為1→2→3→4→5。（8）將隊列中的第一個元素6取出來，將其標記為已訪問，并將6的所有未訪問的鄰接節(jié)點放入隊列的尾部，隊列更新為{7，8，9}，訪問序列為1→2→3→4→5→6。（9）將隊列中的第一個元素7取出來，將其標記為已訪問，由于7沒有未訪問的鄰接節(jié)點，隊列更新為{8，9}，訪問序列為1→2→3→4→5→6→7。（10）將隊列中的第一個元素8取出來，將其標記為已訪問，由于8沒有未訪問的鄰接節(jié)點，隊列更新為{9}，訪問序列為1→2→3→4→5→6→7→8。（11）將隊列中的第一個元素9取出來，將其標記為已訪問，由于9沒有未訪問的鄰接節(jié)點，隊列更新為{}，訪問序列為1→2→3→4→5→6→7→8→9。（12）由于隊列為空，結束循環(huán)，搜索結束，最終得到的樹的廣度優(yōu)先搜索序列為1→2→3→4→5→6→7→8→94.3.2BFS的基本概念

時間限制：1000ms內存限制：32MB問題描述輸入一個包含n個節(jié)點的樹，節(jié)點編號依次為0、1...n-1，以及一個包含n-1條無向邊的edges列表，其中edges[i]=[a,b]表示節(jié)點a和節(jié)點b中存在一條無向邊。當選擇其中任何一個節(jié)點作為根節(jié)點時，都可形成一棵高度為h的樹。在所有可能的樹中，具有最小高度的樹被稱為最小高度樹。要求找到所有的最小高度樹，并依次輸出它們的根節(jié)點編號。輸入說明一個整數n，代表樹的節(jié)點數。一個二維矩陣edges，表示樹的邊輸出說明所有最小高度樹的根節(jié)點編號。輸入樣例n=4edges=[[1,0],[1,2],[1,3]]輸出樣例[1]4.3.3DFS與BFS的應用舉例1：最小高度樹

算法分析以樣例輸入為例，該樹包括4個節(jié)點，3條邊，當我們選擇其中任何一個節(jié)點作為樹根時，都可以相應構造出一棵樹，樹的結構如下：4.3.3DFS與BFS的應用舉例1：最小高度樹

圖4-2不同高度的樹其中最小高度樹是以節(jié)點1為根的樹，樹高為1。由于樹的連通性且沒有環(huán)，任何一個節(jié)點都可以作為樹根，從而形成一棵樹。直觀的解決辦法是依次對每一個可能形成的樹使用DFS算法，然后計算樹中每個節(jié)點的高度，并將其中最大值作為樹的高度。但是這種算法的時