欢迎来到三一文库! | 帮助中心 三一文库31doc.com 一个上传文档投稿赚钱的网站
三一文库
全部分类
  • 研究报告>
  • 工作总结>
  • 合同范本>
  • 心得体会>
  • 工作报告>
  • 党团相关>
  • 幼儿/小学教育>
  • 高等教育>
  • 经济/贸易/财会>
  • 建筑/环境>
  • 金融/证券>
  • 医学/心理学>
  • ImageVerifierCode 换一换
    首页 三一文库 > 资源分类 > PPT文档下载
     

    第七章内排序.ppt

    • 资源ID:2552010       资源大小:1.20MB        全文页数:156页
    • 资源格式: PPT        下载积分:10
    快捷下载 游客一键下载
    会员登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录 QQ登录   微博登录  
    二维码
    微信扫一扫登录
    下载资源需要10
    邮箱/手机:
    温馨提示:
    用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP免费专享
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    第七章内排序.ppt

    第七章 内排序,任课教员:张 铭 http:/db.pku.edu.cn/mzhang/DS/ mzhangdb.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有,转载或翻印必究,北京大学信息学院 版权所有,转载或翻印必究 Page 2,大纲,7.1 基本概念 7.2 三种(n2)的简单排序 插入排序 直接插入排序 二分法插入排序 冒泡排序 选择排序 7.3 Shell排序,北京大学信息学院 版权所有,转载或翻印必究 Page 3,大纲(续),7.4 基于分治法的排序 快速排序 归并排序 7.5 堆排序 7.6 分配排序和基数排序 7.7 各种排序算法的理论和实验时间代价 7.8 排序问题的下限,北京大学信息学院 版权所有,转载或翻印必究 Page 4,7.1基本概念,记录(Record):结点,进行排序的基本单位 关键码(Key):唯一确定记录的一个或多个域 排序码(Sort Key):作为排序运算依据的一个 或多个域 序列(Sequence):线性表,由记录组成的集合,北京大学信息学院 版权所有,转载或翻印必究 Page 5,7.1基本概念(续),排序(Sorting) 将序列中的记录按照排序码特定的顺序排列起来,即排序码域的值具有不减(或不增)的顺序。,北京大学信息学院 版权所有,转载或翻印必究 Page 6,排序问题,给定一个序列R =r1, r2, ,rn,其排序码分别为k =k1, k2, ,kn 排序的目的就是将R中的记录按照特定的顺序重新排列,形成一个新的有序序列R= r1, r2, ,rn 相应排序码为k =k1, k2, ,kn 其中k1k2kn或k1k2kn ,前者称为不减序,后者称为不增序。,北京大学信息学院 版权所有,转载或翻印必究 Page 7,7.1基本概念(续),内排序(Internal Sorting):整个排序过程中所有的记录都可以直接存放在内存中 外排序(External Sorting):内存无法容纳所有记录,排序过程中还需要访问外存,北京大学信息学院 版权所有,转载或翻印必究 Page 8,7.1基本概念(续),“正序”序列 :待排序序列正好符合排序要求 “逆序” 序列 :把待排序序列逆转过来,正好符合排序要求,北京大学信息学院 版权所有,转载或翻印必究 Page 9,7.1基本概念(续),“稳定的”(stable)排序算法 :如果存在多个具有相同排序码的记录,经过排序后这些记录的相对次序仍然保持不变 。,北京大学信息学院 版权所有,转载或翻印必究 Page 10,排序算法的分类,简单排序 插入排序(Insert sort) 直接选择排序(Selection sort) 冒泡排序(Bubble sort) Shell排序(Shell sort),北京大学信息学院 版权所有,转载或翻印必究 Page 11,排序算法的分类(续),分治排序 快速排序(Quicksort) 归并排序(Mergesort) 堆排序(Heapsort) 分配排序 (Binsort),北京大学信息学院 版权所有,转载或翻印必究 Page 12,排序算法的衡量标准,时间代价:记录的比较和交换次数 空间代价 算法的复杂度,北京大学信息学院 版权所有,转载或翻印必究 Page 13,总的排序类,template class Sorter /总排序类 protected: /交换数组中的两个元素 static void swap(Record Array,int i,int j); public: /对数组Array进行排序 void Sort(Record Array,int n); /输出数组内容 void PrintArray(Record array, int n); ;,北京大学信息学院 版权所有,转载或翻印必究 Page 14,Compare类,Compare类是用来比较记录的排序码,把它单独定义成模板参数,是为了方便针对不同类型的排序码进行比较。为了简便起见, 我们只讨论整数排序的例子。,北京大学信息学院 版权所有,转载或翻印必究 Page 15,int_intCompare 类,class int_intCompare /比较两个整型记录大小 public: static bool lt(int x,int y) return xy; static bool le(int x,int y) return x=y; ;,北京大学信息学院 版权所有,转载或翻印必究 Page 16,swap函数,template void Sorter: swap(Record Array,int i,int j) /交换数组中的两个元素 Record TempRecord = Arrayi; Arrayi = Arrayj; Arrayj = TempRecord; ,北京大学信息学院 版权所有,转载或翻印必究 Page 17,PrintArray函数,template void Sorter: PrintArray(Record Array, int n) /输出数组内容 for(int i=0;in;i+) coutArrayi“ “; coutendl; ,北京大学信息学院 版权所有,转载或翻印必究 Page 18,7.2 三种(n2)的简单排序,插入排序(Insert Sort) 冒泡排序(Bubble Sort) 选择排序 (Selection Sort),北京大学信息学院 版权所有,转载或翻印必究 Page 19,7.2.1插入排序,算法思想: 逐个处理待排序的记录,每个新记录都要与前面那些已排好序的记录进行比较,然后插入到适当的位置。,北京大学信息学院 版权所有,转载或翻印必究 Page 20,北京大学信息学院 版权所有,转载或翻印必究 Page 21,插入排序类,template class InsertSorter:public Sorter;,北京大学信息学院 版权所有,转载或翻印必究 Page 22,直接插入排序,template class StraightInsertSorter:public InsertSorter /直接插入排序类 public: void Sort(Record Array,int n); ;,北京大学信息学院 版权所有,转载或翻印必究 Page 23,template void StraightInsertSorter: Sort(Record Array, int n) /Array为待排序数组,n为数组长度 for (int i=1; i0;j-) if (Compare:lt(Arrayj, Arrayj-1) swap(Array, j, j-1); else break; /此时i前面记录已排序 ,北京大学信息学院 版权所有,转载或翻印必究 Page 24,算法分析,稳定 空间代价:(1) 时间代价: 最佳情况:n-1次比较,0次比较,(n) 最差情况:比较和交换次数为 平均情况:(n2),北京大学信息学院 版权所有,转载或翻印必究 Page 25,优化的插入排序算法,template class ImprovedInsertSorter:public InsertSorter /优化的插入排序类 public: void Sort(Record Array,int n); ;,北京大学信息学院 版权所有,转载或翻印必究 Page 26,template void ImprovedInsertSorter: Sort(Record Array, int n) /Array为待排序数组,n为数组长度 Record TempRecord; / 临时变量 / 依次插入第i个记录 for (int i=1; in; i+) TempRecord=Arrayi; /从i开始往前寻找记录i的正确位置 int j = i-1;,北京大学信息学院 版权所有,转载或翻印必究 Page 27,/将那些大于等于记录i的记录后移 while (j=0) ,北京大学信息学院 版权所有,转载或翻印必究 Page 28,二分法插入排序,算法思想: 在插入第i个记录时,前面的记录已经是有序的了,可以用二分法查找第i个记录的正确位置 。,北京大学信息学院 版权所有,转载或翻印必究 Page 29,template class BinaryInsertSorter:public InsertSorter /二分法插入排序类 public: void Sort(Record Array,int n); ;,北京大学信息学院 版权所有,转载或翻印必究 Page 30,template void BinaryInsertSorter: Sort(Record Array, int n) /Array为待排序数组,n为数组长度 Record TempRecord; /临时变量 /记录已排好序序列的左、右、中位置 int left,right,middle; /依次插入第i个记录 for (int i=1;in;i+) /保存当前待插入记录 TempRecord = Arrayi;,北京大学信息学院 版权所有,转载或翻印必究 Page 31,/记录已排好序序列的左右位置 left = 0; right = i-1; /开始查找待插入记录的正确位置 while(left = right) /中间位置 middle = (left+right)/2; /如果待插入记录比中间记录小, / 就在左一半中查找, / 否则在右一半中查找 if (Compare:lt(TempRecord,Arraymi ddle) right = middle-1;,北京大学信息学院 版权所有,转载或翻印必究 Page 32,else left = middle+1; /将前面所有大于当前待插入记录的记录后移 for(int j = i-1; j = left; j -) Arrayj+1 = Arrayj; /将待插入记录回填到正确位置 Arrayleft = TempRecord; ,北京大学信息学院 版权所有,转载或翻印必究 Page 33,算法分析,稳定 空间代价:(1) 时间代价: 插入每个记录需要(log i)次比较 最多移动i+1次 ,最少2次(移动临时记录) 因此最佳情况下总时间代价为 (nlog n) ,最差和平均情况下仍为(n2),北京大学信息学院 版权所有,转载或翻印必究 Page 34,7.2.2 冒泡排序,算法思想: 不停地比较相邻的记录,如果不满足排序要求,就交换相邻记录,直到所有的记录都已经排好序。,北京大学信息学院 版权所有,转载或翻印必究 Page 35,北京大学信息学院 版权所有,转载或翻印必究 Page 36,冒泡排序类,template class BubbleSorter:public Sorter /冒泡排序类 public: void Sort(Record Array,int n); ;,北京大学信息学院 版权所有,转载或翻印必究 Page 37,冒泡排序算法,template void BubbleSorter: Sort(Record Array, int n) /冒泡排序,Array为待排数组,n为数组长度 /第i个记录冒泡 for (int i=1; i=i; j-) if (Compare:lt(Arrayj, Arrayj-1) swap(Array, j, j-1); ,北京大学信息学院 版权所有,转载或翻印必究 Page 38,算法分析,稳定 空间代价:(1) 时间代价 : 比较次数 : 交换次数最多为(n2),最少为0,平均为(n2)。 最大,最小,平均时间代价均为(n2)。,北京大学信息学院 版权所有,转载或翻印必究 Page 39,优化的冒泡排序,改进:检查每次冒泡过程中是否发生过交换,如果没有,则表明整个数组已经排好序了,排序结束。 避免不必要的比较,北京大学信息学院 版权所有,转载或翻印必究 Page 40,优化的冒泡排序,template class ImprovedBubbleSorter:public Sorter /优化的冒泡排序类 public: void Sort(Record Array,int n); ;,北京大学信息学院 版权所有,转载或翻印必究 Page 41,template void ImprovedBubbleSorter: Sort(Record Array, int n) /Array为待排序数组,n为数组长度 bool NoSwap; / 是否发生交换的标志 for (int i=1; i=i; j-),北京大学信息学院 版权所有,转载或翻印必究 Page 42,if (Compare:lt(Arrayj, Arrayj-1) /如果发生了交换, /标志变为假 swap(Array, j, j-1); NoSwap = false; / 如果没发生过交换, / 表示已排好序,结束算法 if (NoSwap) return; ,北京大学信息学院 版权所有,转载或翻印必究 Page 43,算法分析,稳定 空间代价为(1) 时间代价: 最小时间代价为(n):最佳情况下只运行第一轮循环 其他情况下时间代价仍为(n2),北京大学信息学院 版权所有,转载或翻印必究 Page 44,7.2.3 直接选择排序,算法思想: 找出剩下的未排序记录中的最小记录,然后直接与数组中第i个记录交换 ,比冒泡排序减少了移动次数,北京大学信息学院 版权所有,转载或翻印必究 Page 45,北京大学信息学院 版权所有,转载或翻印必究 Page 46,直接选择排序,template class StraightSelectSorter:public Sorter /直接选择排序类 public: void Sort(Record Array,int n); ;,北京大学信息学院 版权所有,转载或翻印必究 Page 47,template void StraightSelectSorter: Sort(Record Array, int n) /Array为待排序数组,n为数组长度 / 依次选出第i小的记录, / 即剩余记录中最小的那个 for (int i=0; in-1; i+) / 首先假设记录i就是最小的 int Smallest = i; / 开始向后扫描所有剩余记录 for (int j=i+1;jn; j+),北京大学信息学院 版权所有,转载或翻印必究 Page 48,/ 如果发现更小的记录,记录它的位置 if (Compare:lt(Arrayj, ArraySmallest) Smallest = j; /将第i小的记录放在数组中第i个位置 swap(Array, i, Smallest); ,北京大学信息学院 版权所有,转载或翻印必究 Page 49,算法分析,不稳定 空间代价:(1) 时间代价 : 比较次数:(n2),与冒泡排序一样 交换次数:n-1 总时间代价:(n2),北京大学信息学院 版权所有,转载或翻印必究 Page 50,7.2.4 简单排序算法的时间代价对比,北京大学信息学院 版权所有,转载或翻印必究 Page 51,北京大学信息学院 版权所有,转载或翻印必究 Page 52,北京大学信息学院 版权所有,转载或翻印必究 Page 53,7.3 Shell排序,直接插入排序的两个性质: 在最好情况(序列本身已是有序的)下时间代价为(n) 对于短序列,直接插入排序比较有效 Shell排序有效地利用了直接插入排序的这两个性质 。,北京大学信息学院 版权所有,转载或翻印必究 Page 54,Shell排序,算法思想: 先将序列转化为若干小序列,在这些小序列内进行插入排序; 逐渐扩大小序列的规模,而减少小序列个数,使得待排序序列逐渐处于更有序的状态, 最后对整个序列进行扫尾直接插入排序,从而完成排序。,北京大学信息学院 版权所有,转载或翻印必究 Page 55,北京大学信息学院 版权所有,转载或翻印必究 Page 56,“增量每次除以2递减”的Shell排序,template class ShellSorter:public Sorter /Shell排序类 private: / 针对变化的增量而修改的插入排序算法,参数 /delta表示当前的增量 void ModifiedInsertSort(Record Array,int n,int delta); public: void Sort(Record Array,int n); ;,北京大学信息学院 版权所有,转载或翻印必究 Page 57,template Void ShellSorter:Sort (Record Array, int n) /Shell排序,Array为待排序数组, / n为数组长度 / 增量delta每次除以2递减 for (int delta=n/2; delta0; delta/=2) /分别对delta个子序列排序 for (int j=0; jdelta; j+) ModifiedInsertSort( ,北京大学信息学院 版权所有,转载或翻印必究 Page 58,针对变化的增量而修改的插入排序算法,template void ShellSorter: ModifiedInsertSort(Record Array,int n, int delta) / 参数delta表示当前的增量 / 对子序列中第i个记录排序 for (int i=delta; i=delta; j-=delta) if (Compare:lt(Arrayj, Arrayj-delta) swap(Array, j, j-delta); else break; ,北京大学信息学院 版权所有,转载或翻印必究 Page 59,算法分析,不稳定 空间代价:(1) 时间代价:(n2) 选择适当的增量序列,可以使得时间代价接近(n) 。,北京大学信息学院 版权所有,转载或翻印必究 Page 60,增量序列的选择,增量每次除以2递减,时间代价为(n2) 增量序列为2k-1,2k -1 -1,7,3,1 时,时间代价为(n3/2) 选取其他增量序列还可以更进一步减少时间代价,北京大学信息学院 版权所有,转载或翻印必究 Page 61,7.4 基于分治法的排序,将原始数组分为若干个子部分然后分别进行排序 两种算法 快速排序 归并排序,北京大学信息学院 版权所有,转载或翻印必究 Page 62,7.4.1 快速排序,算法思想: 选择轴值(pivot) 将序列划分为两个子序列L和R,使得L中所有记录都小于或等于轴值,R中记录都大于轴值 对子序列L和R递归进行快速排序,北京大学信息学院 版权所有,转载或翻印必究 Page 63,北京大学信息学院 版权所有,转载或翻印必究 Page 64,轴值选择,尽可能使L,R长度相等 选择策略: 选择最左边记录 随机选择 选择平均值,北京大学信息学院 版权所有,转载或翻印必究 Page 65,分割过程(Partition),整个快速排序的关键 分割后使得L中所有记录位于轴值左边,R中记录位于轴值右边,即轴值以位于正确位置,北京大学信息学院 版权所有,转载或翻印必究 Page 66,北京大学信息学院 版权所有,转载或翻印必究 Page 67,北京大学信息学院 版权所有,转载或翻印必究 Page 68,快速排序算法,template class QuickSorter:public Sorter /快速排序类 private: /选择轴值,返回轴值下标 int SelectPivot(int left, int right); /分割,返回轴值位置 int Partition(Record Array, int left, int right); public: void Sort(Record Array,int left,int right); ;,北京大学信息学院 版权所有,转载或翻印必究 Page 69,template void QuickSorter: Sort(Record Array, int left,int right) /Array为待排序数组,i,j分别为数组两端 / 如果子序列中只有0或1个记录,就不需排序 if (right = left) return; /选择轴值 int pivot = SelectPivot(left, right); /分割前先将轴值放到数组末端 swap(Array, pivot, right);,北京大学信息学院 版权所有,转载或翻印必究 Page 70,/ 对剩余的记录进行分割 pivot = Partition(Array, left, right); /对轴值左边的子序列进行递归快速排序 Sort(Array, left, pivot-1); /对轴值右边的子序列进行递归快速排序 Sort(Array, pivot +1, right); ,北京大学信息学院 版权所有,转载或翻印必究 Page 71,轴值选择函数,template int QuickSorter: SelectPivot(int left,int right) /参数left,right分别表示序列的左右端下标 /选择中间纪录作为轴值 return (left+right)/2; ,北京大学信息学院 版权所有,转载或翻印必究 Page 72,分割函数,template int QuickSorter: Partition(Record Array, int left,int right) /分割函数,分割后轴值已到达正确位置 Record TempRecord; /存放轴值的临时变量 int i = left; / i为左指针,j为右指针 int j = right; /将轴值存放在临时变量中 TempRecord = Arrayj; /开始分割,i,j不断向中间移动,直到相遇,北京大学信息学院 版权所有,转载或翻印必究 Page 73,while (i != j) /i指针右移,直到找到一个大于等于轴值的记录 while (Compare:lt(Arrayi, TempRecord) /j指针向左移动一步 ,北京大学信息学院 版权所有,转载或翻印必究 Page 74,/j指针左移,直到找到一个小于等于轴值的记录 while (Compare:gt(Arrayj, TempRecord) /返回分界位置i ,北京大学信息学院 版权所有,转载或翻印必究 Page 75,算法分析,最差情况: 时间代价: (n2) 空间代价: (n) 最佳情况: 时间代价:(nlog n) 空间代价:(log n) 平均情况: 时间代价:(nlog n) 空间代价:(log n),北京大学信息学院 版权所有,转载或翻印必究 Page 76,算法分析(续),不稳定 优化:当快速排序的子数组小于某个长度时,不继续递归,直接进行插入排序。 经验表明,最好的组合方式是当n(子数组的长度)小于等于16时就使用插入排序,北京大学信息学院 版权所有,转载或翻印必究 Page 77,优化的快速排序,#define THRESHOLD 16 template class ImprovedQuickSorter:public Sorter /优化的快速排序类 private: /选择轴值,返回轴值下标 int SelectPivot(int left, int right); /分割,返回轴值位置 int Partition(Record Array, int left, int right); void DoSort(Record Array,int left,int right); public: void Sort(Record Array,int left,int right); ;,北京大学信息学院 版权所有,转载或翻印必究 Page 78,template void ImprovedQuickSorter:Sort(Record Array, int left,int right) /优化的快速排序,Array为待排序数组,i,j分别/为数组两端 /先对序列进行递归排序 DoSort(Array,left,right); /最后对整个序列进行一次直接插入排序 ImprovedInsertSorter insert_sorter; insert_sorter.Sort(Array,right-left+1); ,北京大学信息学院 版权所有,转载或翻印必究 Page 79,template void ImprovedQuickSorter:DoSort(Record Array, int left,int right) /优化的快速排序,Array为待排序数组,i,j分别为数组/两端 / 如果序列中只有0或1个记录,就不用排序 if (right THRESHOLD) ,北京大学信息学院 版权所有,转载或翻印必究 Page 80,/选择轴值 int pivot = SelectPivot(left, right); / 将轴值放在数组末端 swap(Array, pivot, right); / 对剩余的记录进行分割 pivot = Partition(Array, left, right); /对分割出的子序列进行递归快速排序 /对轴值左右分别进行排序 DoSort(Array, left, pivot-1); DoSort(Array, pivot+1, right); ,北京大学信息学院 版权所有,转载或翻印必究 Page 81,7.4.2 归并排序,算法思想 简单地将原始序列划分为两个子序列 分别对每个子序列递归排序 最后将排好序的子序列合并为一个有序序列,即归并过程,北京大学信息学院 版权所有,转载或翻印必究 Page 82,北京大学信息学院 版权所有,转载或翻印必究 Page 83,两路归并排序,template class TwoWayMergeSorter:public Sorter /两路归并排序类 private: /归并过程 void Merge(Record Array, Record TempArray,int left,int right,int middle); public: void Sort(Record Array, Record TempArray,int left, int right); ;,北京大学信息学院 版权所有,转载或翻印必究 Page 84,template void TwoWayMergeSorter: Sort(Record Array, Record TempArray,int left, int right) /Array为待排序数组,left,right分别为数组两端 / 如果序列中只有0或1个记录,就不用排序 if (left right) /从中间划分为两个子序列 int middle=(left+right)/2;,北京大学信息学院 版权所有,转载或翻印必究 Page 85,/对左边一半进行递归 Sort(Array, TempArray,left,middle); /对右边一半进行递归 Sort(Array, TempArray,middle+1,right); / 进行归并 Merge(Array, TempArray,left,right,middle); ,北京大学信息学院 版权所有,转载或翻印必究 Page 86,归并函数,template void TwoWayMergeSorter: Merge(Record Array, Record TempArray,int left,int right,int middle) /归并过程 / 将数组暂存入临时数组 for (int j=left; j=right; j+) TempArrayj = Arrayj;,北京大学信息学院 版权所有,转载或翻印必究 Page 87,int index1=left; /左边子序列的起始位置 int index2=middle+1;/右子序列起始位置 int i=left; /从左开始归并 while (index1 = middle),北京大学信息学院 版权所有,转载或翻印必究 Page 88,else Arrayi+ = TempArrayindex2+; /处理剩余记录 while (index1 = middle) Arrayi+ = TempArrayindex1+; while (index2 = right) Arrayi+ = TempArrayindex2+; ,北京大学信息学院 版权所有,转载或翻印必究 Page 89,算法分析,空间代价:(n) 总时间代价:(nlog n) 不依赖于原始数组的输入

    注意事项

    本文(第七章内排序.ppt)为本站会员(本田雅阁)主动上传,三一文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知三一文库(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    经营许可证编号:宁ICP备18001539号-1

    三一文库
    收起
    展开