索引技術(shù)簡介分治思想以及排序算法

1、1索引技術(shù)簡介、分治思想索引技術(shù)簡介、分治思想以及排序算法以及排序算法2010/05/132內(nèi)容內(nèi)容 作業(yè)講解 分治思想 分治排序算法 倒排索引技術(shù) 中文信息處理與數(shù)據(jù)分析3456能否實現(xiàn)冒泡排序？7科學(xué)網(wǎng)廣度優(yōu)先有回路中文內(nèi)容科學(xué)網(wǎng)廣度優(yōu)先有回路中文內(nèi)容 2000網(wǎng)頁詞頻統(tǒng)計結(jié)果 高頻詞 低頻詞8 Google + 百度 私家爬蟲 網(wǎng)上智能代理爬蟲，還是爬蟲爬蟲，還是爬蟲9中文信息處理中文信息處理 分詞 詞典分詞 新詞發(fā)現(xiàn) 統(tǒng)計分詞 序列標注 語義標識與信息提取10排序算法：排序算法： 為什么要排序？有序表的優(yōu)點？缺點？ 構(gòu)造關(guān)系。 按照什么原則排序？ 比較？ 如何進行排序？11基本概念基本

2、概念 排序排序（Sorting）： 簡單地說，排序就是把一組記錄一組記錄按照某個（或某幾個）字段的值以遞增（由小到大）或遞減（由大到?。┑拇涡蛑匦屡帕械倪^程。（如按年齡從小到大排序）學(xué)號姓名年齡性別2004001張佳18男2004002王鵬19男2004003劉寧17女2004004李娟18女2004005陳濤19男2004006李小燕18女12作為比較基礎(chǔ)的一個(或多個)字段，稱為排序碼排序碼。排序碼可以是數(shù)值、符號或符號串。排序碼排序碼不一定是關(guān)鍵碼，是關(guān)鍵碼，關(guān)鍵碼可以作為排序碼。關(guān)鍵碼是唯一的，但排序碼不一定唯一。排序碼不唯一時，排序的結(jié)果可能不唯一。參與排序的對象，稱為記錄。一個記錄

3、可以包含多個字段。如果記錄集合中存在多個排序碼排序碼相同的記錄，經(jīng)過排序后，排序碼排序碼相同的記錄的前后次序保持不變，則這種排序方法稱為是穩(wěn)定穩(wěn)定的，否則是不穩(wěn)定不穩(wěn)定的。排序碼 與 關(guān)鍵碼（primary key）13 排序方法可以分為五種 插入插入排序、選擇選擇排序、交換交換排序、分配分配排序和歸并歸并排序。 在排序過程中，全部記錄存放在內(nèi)存，則稱為內(nèi)排序內(nèi)排序，如果排序過程中需要使用外存，則稱為外排序。外排序。 本章側(cè)重討論內(nèi)排序的方法，但有些方法(特別是歸并排序的思想)也可以用于外排序。排序的類型14排序算法的評價排序算法的評價 評價排序算法好壞的標準執(zhí)行算法所需的時間執(zhí)行算法所需要的

4、附加空間算法本身的復(fù)雜程度也是考慮的一個因素 排序的時間開銷時間開銷是算法好壞的最重要的標志 排序的時間開銷衡量標準:算法執(zhí)行中的比較次數(shù)（必須）。算法執(zhí)行中的移動次數(shù)（有可能避免）。 通常會關(guān)注最壞情況和平均情況的開銷。15插入排序選擇排序：直接選擇排序交換排序歸并排序直接插入排序二分插入排序起泡排序快速排序表插入排序Shell 排序堆排序排序算法排序算法16插入排序插入排序 基本思想：每步將一個待排序的記錄，按其排序碼大小插到前面已經(jīng)排序的字序列的合適位置，直到全部插入排序完為止。02111(, ., | ,)kkknaaabbbx 順次選取一個元素順次選取一個元素插入到合適位置插入到合適

5、位置17插入排序的細分類插入排序的細分類n如何插入到已排好序的序列中？v直接插入（從后向前找位置后插入） O(n2)v 二分法插入（按二分法找位置后插入） O(nlog2n)v 表插入排序（按鏈表查找位置后插入） O(n2)18直接插入排序直接插入排序 基本思想： 假定前面m 個元素已經(jīng)排序； 取第(m+1) 個元素，插入到前面的適當(dāng)位置； 一直重復(fù)，到m=n 為止。 （初始情況下，m = 1）19 第一趟：第一趟： 2323， 起始只有一個記錄起始只有一個記錄 1111, 23 , 23 11 第二趟：第二趟： 1111，2323， 11 11，2323，5555 55 第三趟：第三趟： 1

6、111，2323，5555， 11 11，2323，5555，9797 97 第四趟：第四趟： 1111，2323，5555，9797， 11 11，1919，2323，5555，97 97 19 第五趟：第五趟： 1111，1919，2323，5555，9797， 11 11，1919，2323，5555，8080，97 97 80示例示例：23，11，55，97，19，8020直接插入排序的算法中記錄的數(shù)據(jù)結(jié)構(gòu)直接插入排序的算法中記錄的數(shù)據(jù)結(jié)構(gòu)typedef int KeyType;typedef int DataType;typedef struct KeyType key; /* 排序

7、碼字段 */ DataType info; /* 記錄的其他字段 */ RecordNode;typedef struct int n; /* n為文件中的記錄個數(shù)，nkey key保證穩(wěn)定的排序。2)1(11nnini33選擇排序選擇排序 思想：每趟從待排序的記錄序列中選擇關(guān)鍵字最小的記錄放置到已排序表的最前位置，直到全部排完。 關(guān)鍵問題：在剩余的待排序記錄序列中找到最小關(guān)鍵碼記錄。 方法： 直接選擇排序 堆排序。34直接選擇排序直接選擇排序方法是首先在所有記錄中選出排序碼最小的記錄，與第一個記錄交換然后在其余的記錄中再選出排序碼最小的記錄與第二個記錄交換以此類推，直到所有記錄排好序35直接

8、選擇排序性能分析直接選擇排序性能分析選擇排序的比較次數(shù)與記錄的初始狀態(tài)無關(guān)。第i趟排序：從第i個記錄開始，順序比較選擇最小關(guān)鍵碼記錄需要n-i次比較?？偟谋容^次數(shù)：移動次數(shù)： Mmin = 0 (初始為正序時）最多移動次數(shù)：Mmax = 3(n-1) (初始為逆序時，每趟1次交換，3次移動完成） 時間復(fù)雜度：T(n)=O(n2)，輔助空間1個記錄單位：Temp，穩(wěn)定性： 不穩(wěn)定的排序。 2)1()(11nninni36時間效率評價時間效率評價 建初始堆比較次數(shù)C1：O(n) 重新建堆比較次數(shù)C2：O(nlog2n) 總比較次數(shù)=C1+C2 移動次數(shù)小于比較次數(shù) 因此， 時間復(fù)雜度：O（nlog

9、2n） 空間復(fù)雜度：O（1） 適用于n值較大的情況。 算法穩(wěn)定性：不穩(wěn)定3737交換排序交換排序 交換排序的基本方法 兩兩比較待排序記錄的排序碼，交換不滿足順序要求的偶對，直到全部滿足為止 交換排序的分類 起泡排序 快速排序3838起泡排序起泡排序 方法先將序列中的第一個記錄R0與第二個記錄R1比較，若前者大于后者，則兩個記錄交換位置，否則不交換然后對新的第二個記錄R1與第三個記錄R2作同樣的處理依次類推，直到處理完第n-1個記錄和第n個記錄從(R0，R1)到(Rn-2，Rn-1)的n-1次比較和交換過程稱為一次起泡 經(jīng)過這次起泡，n個記錄中最大者被安置在第n個位置上3939l此后，再對前n-

10、1個記錄進行同樣處理，使n-1個記錄的最大者被安置在整個序列的第n-1個位置上。l然后再對前n-2個記錄重復(fù)上述過程，這樣最多做n-1次起泡就能完成排序可以設(shè)置一個標志noswap表示本次起泡是否有記錄交換，如果沒有交換則表示整個排序過程完成起泡排序是通過相鄰記錄之間的比較與交換，使值較大的記錄逐步從前(上)向后(下)移，值較小的記錄逐步從后(下)向前(上)移，就像水底的氣泡一樣向上冒，故稱為起泡排序起泡排序方法起泡排序方法40若文件初狀為正序，則一趟起泡就可完成排序，排序碼的比較次數(shù)為n-1，且沒有記錄移動，時間復(fù)雜度是O(n)若文件初態(tài)為逆序，則需要n-1趟起泡，每趟進行n-i次排序碼的比

11、較，且每次比較都移動三次，比較和移動次數(shù)均達到最大值起泡排序的算法評價起泡排序的算法評價)(2/ ) 1(3)( 3)(2/ ) 1()(211max211maxnOnninMnOnninCnini41起泡排序的算法評價起泡排序的算法評價(續(xù)續(xù)) 起泡排序最好時間復(fù)雜度是O(n) 起泡排序最壞時間復(fù)雜度為O(n2) 起泡排序平均時間復(fù)雜度為O(n2) 起泡排序算法中增加一個輔助空間temp，輔助空間為S(n)=O(1) 起泡排序是穩(wěn)定的42分治法分治法 int DC(x) if (x) 夠簡單 return C(x); else 將 x 分解為 x1 - xn for( i=0; in;+i)

12、 DC(xi); 重組 DC(xi) 得到 C(x); 43Quick Sort142530233188986279 52 14,23,25,30,31Get one friend to sort the first half. 62,79,98,88Get one friend to sort the second half. 44Quick Sort14,23,25,30,3162,79,98,8852Glue pieces together. (No real work)14,23,25,30,31,52,62,79,88,9845Quick Sort881498256252793023

13、31Let pivot be the first element in the list?1425302388986279 31 5246Quick Sort 14 14,23,25,30,31,52,62,79,88,9823,25,30,31,52,62,79,88,98If the list is already sorted, then the slit is worst case unbalanced.47l設(shè)置變量i指向參加排序的序列中第一個位置0，變量j指向參加排序的序列中最后位置n-1l首先保存記錄R0，R0為空出的位置，空位在前一區(qū)l令j向前掃描，尋找小于R0的記錄，找到小于

14、R0的記錄Rj，將記錄Rj移到當(dāng)前空位中，這時空位在后一區(qū)l這時令i自i+1起向后掃描，尋找大于R0的記錄，找到大于R0的記錄Ri，將記錄Ri移到當(dāng)前空位中，空位又到了前一區(qū)，l然后再令j自j-1起向前掃描，此交替改變掃描方向，從兩端向中間靠攏，直到i=j，這時i所指的位置為R0的最終位置快速排序基本步驟48 初始序列為49, 38, 65, 97, 76, 13, 27, 49，例:(1)一次分區(qū)過程如下一次分區(qū)過程如下 j向左掃描向左掃描49 38 65 97 76 1327 49 ij第一次交換后第一次交換后27 38 65 97 76 13 49 iji向右掃描向右掃描27 38659

15、77613 49ij49第二次交換后27 38 97 76 13 65 49i jj向左掃描，位置不變，第三次交換后27 38 13 97 76 65 49 i ji向右掃描，位置不變，第四次交換后27 38 13 76 97 65 49 i jj向左掃描27 38 13 49 76 97 65 49 ij例（續(xù)）:50 13 27 38 49 49 65 76 9713 27 38 4949 65 76 9713 27 38 4949 65 76 97 最后的排序結(jié)果13 27 38 4949 65 76 97例（續(xù)）:51快速排序算法初始化初始化申明申明temp為記錄結(jié)點類型為記錄結(jié)點類型

16、l r？i,j分別賦值為分別賦值為l,r;temp賦為以賦為以i為下標的值為下標的值i!=j?比較、交換找到以比較、交換找到以i 為下標元素為下標元素的排序位置的排序位置對對i值的前面部分繼續(xù)快速排序值的前面部分繼續(xù)快速排序endNYYN將找到的位置賦值將找到的位置賦值(以以i為下標的記錄為下標的記錄)對對i值的前面部分繼續(xù)快速排序值的前面部分繼續(xù)快速排序?qū)φ麄€文件排序，只需調(diào)用對整個文件排序，只需調(diào)用quickSort (pvector, 0,n-1)即可即可l,r為待比較記錄序列的頭位置和尾位置為待比較記錄序列的頭位置和尾位置52快速排序算法快速排序算法53 當(dāng)待排序記錄已經(jīng)排序時，算法的

17、執(zhí)行時間最長 第一趟經(jīng)過n-1次比較，將第一個記錄定位在原來的位置上，并得到一個包括n-1個記錄的子文件 第二趟經(jīng)過n-2次比較，將第二個記錄定位在原來的位置上，并得到一個包括n-2個記錄的子文件； 這樣最壞情況總比較次數(shù)為快速排序算法評價2) 1(2)(211maxnnninCni5454u最好情況下，每次劃分使兩個子區(qū)的長度大致相等uC(n) n+2C(n/2) n+2n/2+2C(n/22)=2n+4c(n/22)uukn+2kC(n/2k)= nlog2n+nC(1)= O(nlog2n)u快速排序的平均時間復(fù)雜度是T(n)=O(nlog2n)u快速排序是不穩(wěn)定的快速排序算法評價(續(xù))55 如何用快速排序算法實現(xiàn)序列中第i大的元素的查找？思考：思考：56作業(yè)：作