1、為什么要研究排序算法為什么要研究排序算法 -結構化數據表查找問題結構化數據表查找問題 Research Center on Intelligent Computing for Enterprises 3. j =i-1; 4. While (j0 and Ajkey) do 5. Aj+1=Aj; 6. j=j-1; 7. Aj+1=key; 8. 基本排序算法基本排序算法I-內排序之插入法排序內排序之插入法排序 (3)插入排序的算法表達插入排序的算法表達? 插入法排序插入法排序 O(N2) 基本排序算法基本排序算法II -內排序之簡單選擇法排序內排序之簡單選擇法排序 Research Cen

2、ter on Intelligent Computing for Enterprises 3for j=i+1 to N 4. if AjAk then k=j; 5. if ki then 6. 7. temp =Ak; 8. Ak=Ai; 9. Ai=temp; 10. 11. O(N2) 簡單選擇法排序簡單選擇法排序 基本排序算法基本排序算法II-內排序之內排序之簡單選擇法排序簡單選擇法排序 (3)簡單選擇簡單選擇排序的算法表達排序的算法表達? 基本排序算法基本排序算法III -內排序之冒泡法排序內排序之冒泡法排序 Research Center on Intelligent Compu

3、ting for Enterprises 3.for j=1 to N-i 4. if AjAj+1 then 5. temp =Aj; 6. Aj=Aj+1; 7. Aj+1=temp; 8. haschange=true; 9. 10. 11. if (haschange =false) then break; 12. 冒泡法排序冒泡法排序 O(N2) 基本排序算法基本排序算法II-內排序之內排序之冒泡法排序冒泡法排序 (3)冒泡冒泡排序的算法表達排序的算法表達? 戰德臣 教授 快速排序快速排序 從待排序列中任取一個元素從待排序列中任取一個元素 (例如取第一個例如取第一個) 作為中心，所有

4、比作為中心，所有比 它小的元素它小的元素放在左側放在左側，所有比它大的元素，所有比它大的元素放在右側放在右側，形成左右，形成左右 兩個子序列；兩個子序列； 然后再對各子序列重新選擇中心元素并依此規則調整，直到每然后再對各子序列重新選擇中心元素并依此規則調整，直到每 個子序列的元素只剩一個，此時便為有序序列了。個子序列的元素只剩一個，此時便為有序序列了。 同學自己能否寫出其算法同學自己能否寫出其算法-這里將用到遞歸這里將用到遞歸(略略) 其他其他排序算法排序算法? 受限資源約束下的受限資源約束下的算法算法 -內排序與外排序問題內排序與外排序問題 Research Center on Intell

5、igent Computing for Enterprises & Services, Harbin Institute of Technology 戰德臣 哈爾濱工業大學 教授.博士生導師 教育部大學計算機課程教學指導委員會委員 戰德臣 教授 l內排序問題內排序問題:待排序的數據可一次性地裝入內存中，即排序者可 以完整地看到和操縱所有數據，使用數組或其他數據結構便可進 行統一的排序處理的排序問題； l外排序問題外排序問題:待排序的數據保存在磁盤上，不能一次性裝入內存， 即排序者不能一次完整地看到和操縱所有數據，需要將數據分批 裝入內存分批處理的排序問題； 問題類比：某教師要對學生按身高排序。

6、教師只能在房間問題類比：某教師要對學生按身高排序。教師只能在房間(相當于內存相當于內存)中對學生進行排序，假設房中對學生進行排序，假設房 間僅能容納間僅能容納100人，那么對于小于人，那么對于小于100人的學生排序便屬于內排序問題。而對于大于人的學生排序便屬于內排序問題。而對于大于100人，如人，如1000 人的學生排序，學生并不能都進入房間，而只能在操場人的學生排序，學生并不能都進入房間，而只能在操場(相當于磁盤相當于磁盤)等候，輪流進入房間，這樣的等候，輪流進入房間，這樣的 排序便屬于外排序問題。排序便屬于外排序問題。 受限資源約束下的受限資源約束下的算法算法-內排序與外排序問題內排序與外

7、排序問題 (1)排序問題的復雜性在哪里排序問題的復雜性在哪里? 戰德臣 教授 受限資源約束下的受限資源約束下的算法算法-內排序與外排序問題內排序與外排序問題 (2)外排序環境與問題示例外排序環境與問題示例? l內存內存: 2GB l待排序數據待排序數據: 7GB, 10GB, 100GB?-大數據集合大數據集合 這種需要使用硬盤等外部存儲設備進行大數據集合排序的過這種需要使用硬盤等外部存儲設備進行大數據集合排序的過 程程/算法稱為外排序算法稱為外排序(External sorting) 。 戰德臣 教授 外排序算法的環境外排序算法的環境/資源資源(僅介紹思想僅介紹思想,忽略一些細節忽略一些細節

8、), 假設假設: l讀寫磁盤塊函數讀寫磁盤塊函數: ReadBlock, WriteBlock l內存大小內存大小: 共共Bmemory =6塊塊, 每塊可裝載每塊可裝載Rblock =5個元素個元素 l待排序數據待排序數據: Rproblem=60個元素個元素, 共占用共占用Bproblem=12塊塊 問題問題: Bproblem塊的數據怎樣利用塊的數據怎樣利用Bmemory塊的內存進行排序塊的內存進行排序? 受限資源約束下的受限資源約束下的算法算法-內排序與外排序問題內排序與外排序問題 (2)外排序環境與問題示例外排序環境與問題示例? 戰德臣 教授 基本排序策略基本排序策略 lBprobl

9、em塊數據可劃分為塊數據可劃分為N個子集合個子集合, 使每個子集合的塊數小使每個子集合的塊數小 于內存可用塊數，即：于內存可用塊數，即：Bproblem/N Bmemory2如何排序呢？如何排序呢？ 算法的應用條件：算法的應用條件： 子集合數子集合數 Bmemory 子集合的塊數子集合的塊數 Bmemory 即大數據集塊數即大數據集塊數Bmemory2 基本排序算法基本排序算法IV-續續-外排序之多路歸并排序外排序之多路歸并排序-討論討論 (2)算法在任何情況下都可以應用嗎算法在任何情況下都可以應用嗎? 戰德臣 教授 歸并排序歸并排序-討論討論 l內存大小內存大小: 共共Bmemory =3塊

10、塊 l待排序數據待排序數據: 共占用共占用Bproblem=30塊塊 基本策略基本策略: l30塊的數據集塊的數據集 10個子集合，每個子集合個子集合，每個子集合3塊，排序并存儲。塊，排序并存儲。 l10個已排序子集合分成個已排序子集合分成5個組：每個組個組：每個組2個子集合個子集合, 分別進行二分別進行二 路歸并，則可得到路歸并，則可得到5個排好序的集合；個排好序的集合； l5個集合再分成個集合再分成3個組：每個組個組：每個組2個子集，剩余一個單獨個子集，剩余一個單獨1組，組， 分別進行二路歸并，可得分別進行二路歸并，可得3個排好序的集合；再分組，再歸并得個排好序的集合；再分組，再歸并得 到

11、到2個排好序的集合；再歸并便可完成最終的排序。個排好序的集合；再歸并便可完成最終的排序。 基本排序算法基本排序算法IV-續續-外排序之多路歸并排序外排序之多路歸并排序-討論討論 (3)當更大規模的數據需要排序時怎么辦當更大規模的數據需要排序時怎么辦? 戰德臣 教授 歸并排序歸并排序-思考思考 假如內存共有假如內存共有8塊，問其如何排序有塊，問其如何排序有70塊的數據集呢？你塊的數據集呢？你 是采用二路歸并、三路歸并、是采用二路歸并、三路歸并、七路歸并？你設計的具、七路歸并？你設計的具 體算法，磁盤讀寫次數是多少呢？磁盤讀寫次數最少的應體算法，磁盤讀寫次數是多少呢？磁盤讀寫次數最少的應 是幾路歸

12、并？是幾路歸并？ 基本排序算法基本排序算法IV-續續-外排序之多路歸并排序外排序之多路歸并排序-討論討論 (4)思考一下下列情況排序，應該怎么辦思考一下下列情況排序，應該怎么辦? PageRank網頁排序算法網頁排序算法I -網頁排序問題及思想網頁排序問題及思想 Research Center on Intelligent Computing for Enterprises & Services, Harbin Institute of Technology 戰德臣 哈爾濱工業大學 教授.博士生導師 教育部大學計算機課程教學指導委員會委員 戰德臣 教授 PageRank網頁排序算法網頁排序算法

13、I-網頁排序問題網頁排序問題及思想及思想 (1)網頁排序問題網頁排序問題? 4,540,000條檢索記錄條檢索記錄1,210,000條檢索記錄條檢索記錄 怎樣把最重要的檢索記錄顯示給用戶怎樣把最重要的檢索記錄顯示給用戶? 問題背景問題背景-搜索引擎搜索引擎 戰德臣 教授 文本文本 Our Product Information Our Product Information 網頁重要嗎網頁重要嗎?-網頁重要度網頁重要度 問題背景問題背景-網頁網頁 lPageRank是計是計 算網頁重要度的算網頁重要度的 一種方法一種方法 PageRank網頁排序算法網頁排序算法I-網頁排序問題網頁排序問題及思

14、想及思想 (2)PageRank是什么是什么? 網頁又是什么網頁又是什么? 戰德臣 教授 網頁重要度問題的抽象網頁重要度問題的抽象 正向鏈接正向鏈接 反向鏈接反向鏈接 一個網頁的正向鏈接是另一個網頁的反向鏈接一個網頁的正向鏈接是另一個網頁的反向鏈接 PageRank網頁排序算法網頁排序算法I-網頁排序問題網頁排序問題及思想及思想 (3)正向鏈接與反向鏈接正向鏈接與反向鏈接? 基于這些信息，基于這些信息， 如何計算網頁如何計算網頁 重要度重要度? ? 戰德臣 教授 關于網頁的基本觀點關于網頁的基本觀點 l網頁的反向鏈接數越多是否越重網頁的反向鏈接數越多是否越重 要呢要呢? l重要度越高的反向鏈接

15、是否越重重要度越高的反向鏈接是否越重 要呢要呢? l正向鏈接數越多，是否其對鏈接正向鏈接數越多，是否其對鏈接 的網頁而言的網頁而言, 重要度會降低呢重要度會降低呢? PageRank網頁排序算法網頁排序算法I-網頁排序問題網頁排序問題及思想及思想 (4)PageRank的基本思想的基本思想? 戰德臣 教授 網頁重要度網頁重要度 l一個網頁的重要度等于其所有反一個網頁的重要度等于其所有反 向鏈接的加權和，即：向鏈接的加權和，即：反向鏈接權反向鏈接權 值值zi, 網頁重要度網頁重要度R, 則則 R = zi (for 所有反向鏈接所有反向鏈接i)。 l一個正向鏈接的權值等于網頁的一個正向鏈接的權值

16、等于網頁的 重要度除以其正向鏈接數重要度除以其正向鏈接數, 即：網即：網 頁重要度頁重要度R, 其正向鏈接數其正向鏈接數m, 則其則其 每一個正向鏈接的權值每一個正向鏈接的權值 z = R/m。 怎樣計算網頁的重要度呢怎樣計算網頁的重要度呢? PageRank網頁排序算法網頁排序算法I-網頁排序問題網頁排序問題及思想及思想 (4)PageRank的基本思想的基本思想? PageRank網頁排序算法網頁排序算法II -網頁排序問題的表達與建模網頁排序問題的表達與建模 Research Center on Intelligent Computing for Enterprises & Servic

17、es, Harbin Institute of Technology 戰德臣 哈爾濱工業大學 教授.博士生導師 教育部大學計算機課程教學指導委員會委員 戰德臣 教授 PageRank網頁排序算法網頁排序算法II-網頁排序問題的表達與建模網頁排序問題的表達與建模 (1)問題的數學建模問題的數學建模? 數學建模數學建模-示例示例 戰德臣 教授 0010000 0010001 0101101 0010110 0000011 0000001 1011110 A 0000001 0010000 1101001 0010001 0011001 0001101 0110110 T A 數學建模數學建模-鄰接

18、矩陣鄰接矩陣 )i(0 i(1 的鏈接沒有指向網頁網頁 的鏈接存在有指向網頁網頁 jif jif aij 行行i，列，列j 均是網頁編號均是網頁編號 正向鏈接正向鏈接 反向鏈接反向鏈接 正向鏈接正向鏈接 反向鏈接反向鏈接 PageRank網頁排序算法網頁排序算法II-網頁排序問題的表達與建模網頁排序問題的表達與建模 (1)問題的數學建模問題的數學建模? 戰德臣 教授 0000001 0010000 1101001 0010001 0011001 0001101 0110110 T A 數學建模數學建模轉移概率轉移概率 反向鏈接反向鏈接 0000005/1 004/10000 12/103/10

19、05/1 004/10005/1 004/13/1005/1 0003/12/105/1 02/14/102/110 M 轉移概率矩陣轉移概率矩陣 反向鏈接的權值反向鏈接的權值 7 6 5 4 3 2 1 R R R R R R R R T 網頁重要度向量網頁重要度向量 鄰接矩陣鄰接矩陣 PageRank網頁排序算法網頁排序算法II-網頁排序問題的表達與建模網頁排序問題的表達與建模 (2)正向鏈接的權值矩陣正向鏈接的權值矩陣-轉移概率轉移概率? 戰德臣 教授 矩陣乘法與反向鏈接的加權和矩陣乘法與反向鏈接的加權和 )( 7 6 5 4 3 2 1 )1( 7 6 5 4 3 2 1 000000

20、5/1 004/10000 12/103/1005/1 004/10005/1 004/13/1005/1 0003/12/105/1 02/14/102/110 nn R R R R R R R R R R R R R R 轉移概率矩陣轉移概率矩陣M 網頁網頁i的重要度為的重要度為Ri，各網頁重要度的向量，各網頁重要度的向量R，記為：，記為： R = (R1, R2 , Rn)T 矩陣乘法矩陣乘法 第第n-1次次 的網頁的網頁 重要度重要度 第第n次次 的網頁的網頁 重要度重要度 = PageRank網頁排序算法網頁排序算法II-網頁排序問題的表達與建模網頁排序問題的表達與建模 (3)矩陣乘

21、法與反向鏈接的加權和矩陣乘法與反向鏈接的加權和? Ri(n)= j (Mij * Rj(n-1) PageRank網頁排序算法網頁排序算法III -網頁重要度的迭代計算方法及討論網頁重要度的迭代計算方法及討論 Research Center on Intelligent Computing for Enterprises & Services, Harbin Institute of Technology 戰德臣 哈爾濱工業大學 教授.博士生導師 教育部大學計算機課程教學指導委員會委員 戰德臣 教授 PageRank網頁排序算法網頁排序算法III-網頁重要度的迭代計算方法及討論網頁重要度的迭代

22、計算方法及討論 (1)網頁重要度的迭代計算方法網頁重要度的迭代計算方法? )( 7 6 5 4 3 2 1 )1( 7 6 5 4 3 2 1 0000005/1 004/10000 12/103/1005/1 004/10005/1 004/13/1005/1 0003/12/105/1 02/14/102/110 nn R R R R R R R R R R R R R R 轉移概率矩陣轉移概率矩陣M 網頁網頁i的重要度為的重要度為Ri，各網頁重要度的向量，各網頁重要度的向量R，記為：，記為： R = (R1, R2 ,Rn)T 迭代計算迭代計算 Ri(1)= j (Mij * Rj(0)

23、 Ri(2)= j (Mij * Rj(1) Ri(n)= j (Mij * Rj(n-1) Ri(n)=Ri(n-1) ? R的初始值是多少呢的初始值是多少呢? 從哪從哪 一個一個Ri開始計算呢開始計算呢? 矩陣乘法矩陣乘法 第第n-1次次 的網頁的網頁 重要度重要度 第第n次次 的網頁的網頁 重要度重要度 = 戰德臣 教授 PageRank計算結果分析計算結果分析 PageRank網頁排序算法網頁排序算法III-網頁重要度的迭代計算方法及討論網頁重要度的迭代計算方法及討論 (2)PageRank的計算結果分析的計算結果分析? 1號號 vs. 5號號 6號號 vs. 7號號 2號號 vs. 3號號 PageRank網頁排序算法網頁排序算法IV -PageRank與數學及算法總結與數學及算法總結 Research Center on Intelligent Computing for Enterprises & Services, Harbin Institute of Technology 戰德臣 哈爾濱工業大學 教授.博士生導師 教育部大學計算機課程教學指導委員會委員 戰德臣 教授 PageRank網頁排序算法網頁排序算法IV-PageRank與數學及算法總與數學及算法總結結 (1)PageRank計算計算 vs. 數學的