战德臣《大学计算机-计算思维导论》大学计算机第8讲-怎样研究算法-排序算法研究示例

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. 数学的