《第13周内排序第8讲-本周小结.pdf》由会员分享，可在线阅读，更多相关《第13周内排序第8讲-本周小结.pdf（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1插入排序 直接插入排序直接插入排序 折半插入排序折半插入排序 希尔排序希尔排序 1/21 思路：思路： R0 R1 Ri-1Ri Rn-1 将将Ri有序插入到有序区有序插入到有序区R0.i-1中中 趟数：趟数：i=1n-1，共共n-1趟趟 有序区：有序区：局部有序区（最后一趟前，所有数据不一定有序）局部有序区（最后一趟前，所有数据不一定有序） 性能：性能：最好（正序）：最好（正序）：O(n)；最坏（反序）：；最坏（反序）：O(n2)；平均：；平均：O(n2) 稳定性：稳定性：稳定稳定 2/21 思路：思路： R0 R1 Ri-1Ri Rn-1 在有序区在有序区R0.i-1折半查找插入位置折半
2、查找插入位置 趟数：趟数：i=1n-1，共共n-1趟趟 有序区：有序区：局部有序区（最后一趟前，所有数据不一定有序）局部有序区（最后一趟前，所有数据不一定有序） 性能：性能：最好（正序）：最好（正序）：O(n)；最坏（反序）：；最坏（反序）：O(n2)；平均：；平均：O(n2) 稳定性：稳定性：稳定稳定 3/21 思路：思路： 趟数：趟数： log2n 趟趟 有序区：有序区：不产生有序区（最后一趟前，所有数据不一定有不产生有序区（最后一趟前，所有数据不一定有 序）序） 性能：性能：平均：平均：O(n1.3) d=n/2 while (d0) 将将R0.n-1分为到分为到d个组（相距个组（相距d
3、个位置的元素为一组）个位置的元素为一组） 每组进行直接插入排序每组进行直接插入排序 d=d/2; 稳定性：稳定性：不稳定不稳定 4/21 对同一待排序序列分别进行折半插入排序和直接插入排序，对同一待排序序列分别进行折半插入排序和直接插入排序， 两者之间可能的不同之处是两者之间可能的不同之处是 （）。）。 A.排序的总趟数排序的总趟数B.元素的移动次数元素的移动次数 C.使用辅助空间的数量使用辅助空间的数量D.元素之间的比较次数元素之间的比较次数 在有序区查找插入在有序区查找插入Ri的位置：的位置： 直接插入排序采用逐个比较直接插入排序采用逐个比较 折半插入排序采用折半查找方法折半插入排序采用折
4、半查找方法 元素之间的比较次数不同元素之间的比较次数不同 5/21 2交换排序 冒泡排序冒泡排序 快速排序快速排序 6/21 思路：思路： R0 R1 Ri-1Ri Rn-1 通过交换将通过交换将Ri放在无序区开头放在无序区开头 趟数：趟数：i=0n-2，共共n-1趟趟 有序区：有序区：全局有序区全局有序区 性能：性能：最好（正序）：最好（正序）：O(n)；最坏（反序）：；最坏（反序）：O(n2)；平均：；平均：O(n2) 稳定性：稳定性：稳定稳定 7/21 思路：思路： Rs Rt 递归树高度：递归树高度：log2nn 有序区：有序区：每次划分归位一个元素每次划分归位一个元素 性能：性能：最
5、好（随机）：最好（随机）：O(nlog2n)；最坏（正反序）：；最坏（正反序）：O(n2)； 平均：平均： O(nlog2n) 稳定性：稳定性：不稳定不稳定 Rs Ri-1Ri+1 RtRi 划分划分 空间：空间：O(log2n) 8/21 对数据序列（对数据序列（8，9，10，4，5，6，20，1，2）进行）进行 递增排序，采用每趟冒出一个最小元素的递增排序，采用每趟冒出一个最小元素的冒泡排序冒泡排序算算 法，需要进行的趟数至少是（法，需要进行的趟数至少是（ ）。）。 A.3B.4C.5D.8 i=0: 1 8 9 10 4 5 6 20 2 i=1: 1 2 8 9 10 4 5 6 20
6、 i=2: 1 2 4 8 9 10 5 6 20 i=3: 1 2 4 5 8 9 10 6 20 i=4: 1 2 4 5 6 8 9 10 20 9/21 以下关于以下关于快速排序快速排序的叙述中正确的是（的叙述中正确的是（ ）。）。 A.快速排序在所有排序方法中最快，而且所需辅助空间也最少快速排序在所有排序方法中最快，而且所需辅助空间也最少 B.在快速排序中，不可以用队列替代栈在快速排序中，不可以用队列替代栈 C.快速排序的空间复杂度为快速排序的空间复杂度为O(n) D.快速排序在待排序的数据随机分布时效率最高快速排序在待排序的数据随机分布时效率最高 10/21 3选择排序 简单选择排
7、序简单选择排序 堆排序堆排序 11/21 思路：思路： R0 R1 Ri-1Ri Rn-1 通过简单比较将通过简单比较将Ri放在无序区开头放在无序区开头 趟数：趟数：i=0n-2，共共n-1趟趟 有序区：有序区：全局有序区全局有序区 性能：性能：最好、最坏、平均：最好、最坏、平均：O(n2) 稳定性：稳定性：不稳定不稳定 12/21 思路：思路： R1 R2 RiRi+1 Rn 借助堆将借助堆将Ri放在无序区末尾放在无序区末尾 趟数：趟数：i=n2，共共n-1趟趟 有序区：有序区：全局有序区全局有序区 性能：性能：最好、最坏、平均：最好、最坏、平均：O(nlog2n) 稳定性：稳定性：不稳定不
8、稳定 13/21 有一个关键字序列有一个关键字序列(22，86，19，49，12， 30，65，35，18)，在进行一趟排序后得到的结果，在进行一趟排序后得到的结果 为为(18，12，19，22，49，30，65，35，86)，则采，则采 用的排序方法可能是（用的排序方法可能是（ ）。）。 A.简单选择排序简单选择排序B.冒泡排序冒泡排序 C.快速排序快速排序D.堆排序堆排序 选项选项A、B、D每一趟产生的有序区是全局有序区每一趟产生的有序区是全局有序区 14/21 一个有一个有n个整数的数组个整数的数组R1.n，其中所有元素是有，其中所有元素是有 序的，将其看成是一棵完全二叉树，该树构成一个
9、堆吗？序的，将其看成是一棵完全二叉树，该树构成一个堆吗？ 若不是，请给一个反例，若是，请说明理由。若不是，请给一个反例，若是，请说明理由。 该数组一定构成一个堆，该数组一定构成一个堆，递增有序数组构成一个小根递增有序数组构成一个小根 堆，递减有序数组构成一个大根堆堆，递减有序数组构成一个大根堆。 以递增有序数组为例，假设数组元素为以递增有序数组为例，假设数组元素为k1、k2、kn 是递增有序的，从中看出下标越大的元素值也越大，对于是递增有序的，从中看出下标越大的元素值也越大，对于 任一元素任一元素ki，有：，有： ki k2i，ki k2i+1（in/2） 这正好满足小根堆的特性，所以构成一个
10、这正好满足小根堆的特性，所以构成一个小根堆小根堆。 15/21 4归并排序 思路：思路： 16/21 趟数：趟数：共共 log2n 趟趟 有序区：有序区：局部有序区局部有序区 稳定性：稳定性：稳定稳定 性能：性能：最好、最坏、平均：最好、最坏、平均：O(nlog2n) 空间：空间：O(n) 二路归并排序 17/21 两个各含有两个各含有n个元素的有序序列归并成一个有序序个元素的有序序列归并成一个有序序 列时，关键字比较次数为列时，关键字比较次数为n-12n-1，也就是说关键字比，也就是说关键字比 较次数与初始序列有关。为什么通常说二路归并排序与较次数与初始序列有关。为什么通常说二路归并排序与
11、初始序列无关呢？初始序列无关呢？ 二路归并排序中使用了辅助空间二路归并排序中使用了辅助空间R1： R R1 R1 R 每趟移动元素的次数每趟移动元素的次数2n，总的移，总的移 动次数总是动次数总是O(nlog2n) 尽管待排序的初始序列对关键字的比较有一定的影响，但尽管待排序的初始序列对关键字的比较有一定的影响，但 不改变算法的总体时间性能，所以通常说二路归并排序与初始不改变算法的总体时间性能，所以通常说二路归并排序与初始 序列无关。序列无关。 18/21 5基数排序 思路：思路： 将关键字分离出将关键字分离出位位，对每一位进行排序（共，对每一位进行排序（共d 位）位） 多关键字排序多关键字排
12、序 所有位的取值所有位的取值 基数基数r 数据特性数据特性 按最高位优先，按最低位优先按最高位优先，按最低位优先 每一位进行排序：分配、收集（每一位进行排序：分配、收集（不需要关键字比不需要关键字比 较较） 19/21 趟数：趟数：共共d趟趟 稳定性：稳定性：稳定稳定 性能：性能：最好、最坏、平均：最好、最坏、平均：O(d(n+r) 空间：空间：O(r) 20/21 基数排序 有有n个不同的英文单词（均为小写字母），它们的个不同的英文单词（均为小写字母），它们的 长度相等，均为长度相等，均为m。若。若n=500，m5，试问采用什么排，试问采用什么排 序方法时其时间复杂度最小？为什么？序方法时其时间复杂度最小？为什么？ 采用基数排序方法时，采用基数排序方法时，r=26，时间复杂度为，时间复杂度为O(m(n+26m)。 其他排序方法的时间复杂度最小为其他排序方法的时间复杂度最小为O(nlog2n)。 当当n=500，m5时，时，m(n+26m)nlog2n。 采用基数排序方法最好。采用基数排序方法最好。 21/21