七章节内排序.ppt
《七章节内排序.ppt》由会员分享,可在线阅读,更多相关《七章节内排序.ppt(156页珍藏版)》请在三一文库上搜索。
1、第七章 内排序,任课教员:张 铭 http:/ 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有,转载或翻印必究,北京大学信息学院 版权所有,转载或翻印必究 Page 2,大纲,7.1 基本概念 7.2 三种(n2)的简单排序 插入排序 直接插入排序 二分法插入排序 冒泡排序 选择排序 7.3 Shell排序,北京大学信息学院 版权所有,转载或翻印必究 Page 3,大纲(续),7.4 基于分治法的排序 快速排序 归并排序 7.5 堆排序 7.6 分配排序和基数排序 7.7 各种排序算法的理论和实验时间代价 7.8 排序问题的下限,北京大学信息学院 版权所有,转载或翻印必究 Pag
2、e 4,7.1基本概念,记录(Record):结点,进行排序的基本单位 关键码(Key):唯一确定记录的一个或多个域 排序码(Sort Key):作为排序运算依据的一个 或多个域 序列(Sequence):线性表,由记录组成的集合,北京大学信息学院 版权所有,转载或翻印必究 Page 5,7.1基本概念(续),排序(Sorting) 将序列中的记录按照排序码特定的顺序排列起来,即排序码域的值具有不减(或不增)的顺序。,北京大学信息学院 版权所有,转载或翻印必究 Page 6,排序问题,给定一个序列R =r1, r2, ,rn,其排序码分别为k =k1, k2, ,kn 排序的目的就是将R中的记
3、录按照特定的顺序重新排列,形成一个新的有序序列R= r1, r2, ,rn 相应排序码为k =k1, k2, ,kn 其中k1k2kn或k1k2kn ,前者称为不减序,后者称为不增序。,北京大学信息学院 版权所有,转载或翻印必究 Page 7,7.1基本概念(续),内排序(Internal Sorting):整个排序过程中所有的记录都可以直接存放在内存中 外排序(External Sorting):内存无法容纳所有记录,排序过程中还需要访问外存,北京大学信息学院 版权所有,转载或翻印必究 Page 8,7.1基本概念(续),“正序”序列 :待排序序列正好符合排序要求 “逆序” 序列 :把待排序
4、序列逆转过来,正好符合排序要求,北京大学信息学院 版权所有,转载或翻印必究 Page 9,7.1基本概念(续),“稳定的”(stable)排序算法 :如果存在多个具有相同排序码的记录,经过排序后这些记录的相对次序仍然保持不变 。,北京大学信息学院 版权所有,转载或翻印必究 Page 10,排序算法的分类,简单排序 插入排序(Insert sort) 直接选择排序(Selection sort) 冒泡排序(Bubble sort) Shell排序(Shell sort),北京大学信息学院 版权所有,转载或翻印必究 Page 11,排序算法的分类(续),分治排序 快速排序(Quicksort) 归
5、并排序(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); /输出数
6、组内容 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(i
7、nt 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) /输出数组内容
8、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 2
9、1,插入排序类,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
10、为数组长度 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
11、/优化的插入排序类 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
12、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
13、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) /
14、中间位置 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; ,北京大学信息学院
15、 版权所有,转载或翻印必究 Page 33,算法分析,稳定 空间代价:(1) 时间代价: 插入每个记录需要(log i)次比较 最多移动i+1次 ,最少2次(移动临时记录) 因此最佳情况下总时间代价为 (nlog n) ,最差和平均情况下仍为(n2),北京大学信息学院 版权所有,转载或翻印必究 Page 34,7.2.2 冒泡排序,算法思想: 不停地比较相邻的记录,如果不满足排序要求,就交换相邻记录,直到所有的记录都已经排好序。,北京大学信息学院 版权所有,转载或翻印必究 Page 35,北京大学信息学院 版权所有,转载或翻印必究 Page 36,冒泡排序类,template class Bu
16、bbleSorter: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); ,北京大学信息学院 版权所有,转载或翻印必究 Pag
17、e 38,算法分析,稳定 空间代价:(1) 时间代价 : 比较次数 : 交换次数最多为(n2),最少为0,平均为(n2)。 最大,最小,平均时间代价均为(n2)。,北京大学信息学院 版权所有,转载或翻印必究 Page 39,优化的冒泡排序,改进:检查每次冒泡过程中是否发生过交换,如果没有,则表明整个数组已经排好序了,排序结束。 避免不必要的比较,北京大学信息学院 版权所有,转载或翻印必究 Page 40,优化的冒泡排序,template class ImprovedBubbleSorter:public Sorter /优化的冒泡排序类 public: void Sort(Record Arr
18、ay,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; / 如果没发生过交换
19、, / 表示已排好序,结束算法 if (NoSwap) return; ,北京大学信息学院 版权所有,转载或翻印必究 Page 43,算法分析,稳定 空间代价为(1) 时间代价: 最小时间代价为(n):最佳情况下只运行第一轮循环 其他情况下时间代价仍为(n2),北京大学信息学院 版权所有,转载或翻印必究 Page 44,7.2.3 直接选择排序,算法思想: 找出剩下的未排序记录中的最小记录,然后直接与数组中第i个记录交换 ,比冒泡排序减少了移动次数,北京大学信息学院 版权所有,转载或翻印必究 Page 45,北京大学信息学院 版权所有,转载或翻印必究 Page 46,直接选择排序,templa
20、te 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; / 开始向后扫描所
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 章节 排序
链接地址:https://www.31doc.com/p-2582810.html