[工學]第12章_縮小規(guī)模算法-文庫吧資料
2024-10-25 00:16本頁面
【正文】 length=2?length。 length=1。 //歸并最后兩個子表 // 若 i≤n 且 i+length1≥n 時，子表個數為奇數，無須歸并 } 電子工程學院 ?上一頁 ?下一頁 ?回主目錄 2021/11/10 17 ?二路歸并算法 二路歸并排序須調用 “ 一趟歸并 ” 對 R[1..n]進行 ?log2n?趟歸并，每趟歸并后，有序子表的長度均擴大一倍（最后一個可能例外）。 i=i+2?length。 // i指向第一對子表的起始點 while (i+2?length?1=n)。 電子工程學院 ?上一頁 ?下一頁 ?回主目錄 2021/11/10 16 ?一趟歸并算法 void MERGEPASS(rectype R[ ], int length) // 對 R[1..n]做一趟歸并， length是本趟歸并的有序子表的長度 { int i,j。 電子工程學院 ?上一頁 ?下一頁 ?回主目錄 2021/11/10 14 歸并排序過程 21 25 25* 25* 93 62 72 08 37 16 54 49 21 25 49 62 93 08 72 16 37 54 21 25 25* 49 08 62 72 93 16 37 54 08 08 21 16 25 21 25* 25 49 25* 62 37 72 49 93 54 16 37 54 62 72 93 len=1 len=2 len=4 len=8 len=16 電子工程學院 ?上一頁 ?下一頁 ?回主目錄 2021/11/10 15 ?一趟歸并 在給出二路歸并排序算法之前，必須先解決一趟歸并問題。k++,i++) R[i]=R1[k]。 //復制第二個子表的剩余記錄 for(k=0,i=low。 // 取小者復制到 R1[k] while(i=mid) R1[k++]=R[i++]。 (j=high)) if(R[i].key=R[j].key) R1[k++]=R[i++]。 } while ((i=mid) amp。 if(!R1){ printf(“申請空間不成功 ” )。 電子工程學院 ?上一頁 ?下一頁 ?回主目錄 2021/11/10 12 ?歸并算法 void MERGE(rectype R[],int low,int mid,int high) /* R[low..mid]與 R[mid+1..high]是兩個有序子表，結果為一個有序子表R[low..high] */ { int i=low,j=mid+1,k=0。如圖所示： 電子工程學院 ?上一頁 ?下一頁 ?回主目錄 2021/11/10 10 ? 設兩個有序子表（相當于輸入堆）放在同一向量中相鄰的位置上： R[low..mid],R[mid+1..high]，先將它們合并到一個局部的暫存變量 R1（相當于輸出堆）中，待合并完成后將 R1復制回 R[low..high]中。基本步驟是比較兩輸入堆頂上的兩張牌，取出較小的那張牌將它面朝下放到輸出堆中。 電子工程學院 ?上一頁 ?下一頁 ?回主目錄 2021/11/10 9 歸并排序 ?算法思想 假設初始表含有 n個記錄，則可看成是 n個有序的子表，每個子表的長度為 1，然后兩兩歸并，得到 ?n/2?個長度為 2或 1的有序子表，再兩兩歸并， …… 如此重復，直至得到一個長度為 n的有序子表為止。時間復雜度為 O(log2n) 電子工程學院 ?上一頁 ?下一頁 ?回主目錄 2021/11/10 8 ?對于有序序列： 0、 12，描述折半查找過程的判定樹及查找 6和 5的過程： 查找成功的情形 查找不成功的情形 ?查找成功的過程就是走了一條 從根結點到該結點的路徑 ，經歷 比較關鍵字的次數恰為該結點在樹中的層數 。 ? 第 1層結點有 1個，查找第 1層結點要比較 1次；第 2層結點有 2個，查找第 2層結點要比較 2次； … 。 2h = n+1, h = log2(n+1)。 ?用當前查找區(qū)間的中間位置上的記錄作為根，左區(qū)間和右區(qū)間中的記錄分別作為根的左、右子樹。 //查找失敗 } 電子工程學院 ?上一頁 ?下一頁 ?回主目錄 2021/11/10 7 ?對于有序序列： 0、 12，折半查找判定樹： ?樹中每個圓形結點表示一個記錄， 結點的位序是該記錄在表中的位置 。 //在左區(qū)間查找 else low = mid+1。 //取當前查找區(qū)間的中點 if (x==R[mid].key) return mid。 high = n1。 電子工程學院 ?上一頁 ?下一頁 ?回主目錄 2021/11/10 5 查找
教學課件相關推薦
鄂ICP備17016276號-1