4.4排序算法设计（精选6篇）
一、内容分析
【教学目标】
1、理解排序的概念
2、了解常用排序方法
3、理解冒泡排序的基本思路
4、应用冒泡排序法进行排序 【重点难点】
1、冒泡排序法的基本思路
2、应用冒泡排序法进行排序
二、教学内容
（一）常用排序 排序的概念：
排序就是把一组元素（数据或记录）按照元素的值的递增或递减的次序重新排列元素的过程。
如：49 38 76 27 13 常用排序的方法：
1、冒泡排序：冒泡排序是一种简单而饶有趣味的排序方法，它的基本思想是：每次仅进行相邻两个元素的比较，凡为逆序（a(i)>a(i+1)），则将两个元素交换。
2、插入排序：它是一种最简单的排序方法，它的基本思想是依次将每一个元素插入到一个有序的序列中去。这很象玩扑克牌时一边抓牌一边理牌的过程，抓了一张就插到其相应的位置上去。
3、选择排序：这是一种比较简单的排序方法，其基本思想是，每一趟在n-i+1（i=1，2，3，...，n-1）个元素中选择最小的元素。
冒泡排序：
冒泡排序是一种简单而饶有兴趣的排序方法，它的基本思想是：每次进行相邻两个元素的比较，凡为逆序（即a(i)>a(i+1)），则将两个元素交换。
整个的排序过程为：
先将第一个元素和第二个元素进行比较，若为逆序，则交换之；接着比较第二个和第三个元素；依此类推，直到第n-1个元素和第n个元素进行比较、交换为止。如此经过一趟排序，使最大的元素被安置到最后一个元素的位置上。然后，对前n-1个元素进行同样的操作，使次大的元素被安置到第n-1个元素的位置上。重复以上过程，直到没有元素需要交换为止。
例题：对49 38 76 27 13 进行冒泡排序的过程： 初始状态： [49 38 76 27 13 ] 第一趟排序后：[38 49 27 13] 76 第二趟排序后：[38 27 13 ] 49 76 第三趟排序后：[27 13 ] 38 49 76 第四趟排序后：13 27 38 49 76 课堂练习：
用冒泡排序对68 45 35 75 55 17 41进行排序，第二趟排序后的状态为：
A、45 35 68 55 17 41 75 B、35 17 41 45 55 68 75 C、35 45 55 17 41 68 75 D、35 45 17 41 55 68 75 作业：
1、以下两组数据按有小到大排序，请写出每一趟排序后的结果 45 82 12 75 13 89 95 90 87 76 65 54 43 32 21
2、以下两组数据按有大到小排序，请写出每一趟排序后的结果 45 52 12 18 85 46 32 12 23 34 45 56 67 78 89 91 拓展：
随机生成10个不同的整数存于数组a（1 to 10）中，按从小到大的顺序输出。
三、小结 冒泡排序：
冒泡排序是一种简单而饶有兴趣的排序方法，它的基本思想是：每次进行相邻两个元素的比较，凡为逆序（即a(i)>a(i+1)），则将两个元素交换。
整个的排序过程为：
先将第一个元素和第二个元素进行比较，若为逆序，则交换之；接着比较第二个和第三个元素；依此类推，直到第n-1个元素和第n个元素进行比较、交换为止。如此经过一趟排序，使最大的元素被安置到最后一个元素的位置上。然后，对前n-1个元素进行同样的操作，使次大的元素被安置到第n-1个元素的位置上。重复以上过程，直到没有元素需要交换为止。
例题：对49 38 76 27 13 进行冒泡排序的过程： 初始状态： [49 38 76 27 13 ] 第一趟排序后：[38 49 27 13] 76 第二趟排序后：[38 27 13 ] 49 76 第三趟排序后：[27 13 ] 38 49 76 第四趟排序后：13 27 38 49 76 排序算法编程相关知识：
1、数组的定义：
声明数组的一般格式如下：
Dim 数组名（[下界 to ] 上界）As 数据类型
2、数组元素的输入输出：（1）生成随机整数(1-100之间)Randomize for i=1 to n a(i)=int(rnd*100+1)next i（2）输出数组元素 for i=1 to n print a(i);next i
3、冒泡排序的算法实现： 冒泡排序是一种简单而饶有兴趣的排序方法，它的基本思想是：
每次进行相邻两个元素的比较，凡为逆序（即a(i)>a(i+1)），则将两个元素交换。
用两个FOR循环实现： for j=n-1 to 1 step-1 for i=1 to j if a(i)>a(i+1)then t=a(i)a(i)=a(i+1)a(i+1)=t end if next i next j 排序算法的应用：
1、随机生成10个不同的整数存于数组a（1 to 10）中，按从小到大的顺序输出。
2、随机生成20个学生的考试成绩，其中前50%的学生可以参加夏令营。输出这50%的学生的成绩。
通过前面的学习, 学生已经了解了算法设计的基本知识, 学会了利用自然语言和流程图描述解决问题的算法, 对排序中遇到的循环结构流程图、循环语句以及数组变量的使用方法都已有基础。但由于实践较少, 他们对以前知识的遗忘率比较高, 画流程图还不够熟练, 程序设计思想比较弱。
程序设计的基本方法是自顶向下、逐步求精和模块化。依据这一方法, 教师采用讲解法、演示法、讨论合作法、分析归纳法, 引导学生参与思考, 逐步降低学生的理解难度, 化抽象为具体, 有效地将各个难点分解和突破。
一、教学目标
知识目标:掌握冒泡排序的原理, 理解冒泡排序的流程图, 学会编写冒泡排序程序的主要代码。
能力目标:学会使用冒泡排序思想设计解决简单排序问题的算法;进一步理解程序设计的基本方法, 体会程序设计在现实中的作用;培养分析问题、发现规律的能力。
情感目标:提高学习热情, 培养良好的程序书写习惯。
二、教学重点与难点
重点:理解冒泡排序原理及其流程图。
难点:理解冒泡排序中的遍、次等概念 (即对变量使用的理解) 。
三、课前准备
资源准备:冒泡排序的课件。
教学环境的设计与布置:多媒体网络教室、投影机、多媒体教学平台、F l a s h软件。
四、教学过程
1. 导入:创新情景
师:生活中, 我们经常会碰到要排队的情况, 比如排座位、排队做操、排队大合唱等。今天, 我想请4位同学上来表演一下排队。
我按学号顺序点4位学生的名字, 让他们上来, 并让他们按报到的次序排列。
师:他们现在是按什么排的?
生:学号。
师:好, 现在请你们按身高从低到高排列。
不一会儿, 4位学生就排好了。其他学生的注意力也集中了过来。
师 (指着其中一位换到前面去的学生问大家) :他是怎么知道自己矮的。
生:一看就知道了。
师:那请这位学生谈谈你当时的想法。
这时一般学生会提到与别人比一下, 矮的话就换到前面去了 (如果说不出来, 教师可做适当引导) 。
师:对, 肯定要比一下才知道, 而且需要交换。有些学生说一看就知道, 其实也是看了以后经过大脑思维飞快地比较而得出的结论。排队其实是一种排序——通过调整位置, 把杂乱无章的数据变为有序的数据, 如E x c e l中的排序功能。通过本节课的学习, 我们自己也可以设计出类似的小软件。
2. 冒泡排序的基本思想
师:排序的方法很多, 这节课我们来学习其中一种比较典型的排序方法——冒泡排序。
教师先让学生根据字面意思想象一下“冒泡”是一个怎么样的情景——气泡一个一个地由下而上依次冒上来。接下来, 教师一边讲解一边以文字形式给出冒泡排序的基本思想 (教材P 3 1, 略) 。特别要强调怎样算一遍处理, 而且每遍总是从最下面起, 自下而上, 比较相邻的两个数。
教师再让刚才那4位学生仍先按学号排回来, 演示利用冒泡排序法进行从低到高排序的过程。在学生表演时, 教师充当解说员, 在关键处 (如每遍的开始和结束) 进行提示, 并引导学生认识到第几遍处理完后找到的应该是第几矮的同学 (或第几小的数) 。
设计意图:学生的表演比单纯拿出几个数来比较更能吸引学生的注意力, 在这种轻松活跃的气氛中, 学生很快明确了冒泡排序的基本方法。
师:4位学生共进行了几遍查找?为什么?
教师再用一个Flash动画演示规模为4的数组按非减次序进行逐个冒泡排序的过程, 再次强化学生对冒泡排序过程的理解, 也为下面每一遍中两两交换情况的分析做了铺垫。
3. 画流程图 (按非减次序排序)
这一环节是本节课的重点。教师采用自顶向下、逐步求精的方式, 由特殊到一般归纳总结, 各个难点一一突破。
教师以具体的4个数为例, 由最简单的流程图1左侧的图开始, 让学生将冒泡排序过程用形象的语言表示出来:不断冒起一个泡 (最小数) , 转化成右侧流程图。
思考:以4个数为例, 这里的“不断”有没有限定, 到底是几遍呢?为什么?进而带领学生画出流程图2左侧的流程图。
得出流程图2左侧的图之后, 教师让学生思考:这种结构实际上属于什么结构? (循环结构) 但是左图是不规范的, 需要用一个变量来控制循环次数, 从而引出用变量i来记录正在执行的排序的遍数, 它的值应该是从1到3, 每次做完后加1。学生回顾循环结构的流程图模式, 两两讨论, 合作将流程图2左侧的图转换成右侧规范的流程图。
思考:如果参与排序的是n个数呢?
比较遍数与个数关系:遍数=个数-1
为了分解后面的一个难点, 教师让学生用简单的语言描述每次“冒起一个最小数”是怎么冒出来的:不断两两比较交换, 这也是冒泡排序的原理。于是图2右侧流程图又可转化成流程图3的形式。
设计意图:遍数与个数关系运算是本课的一个难点, 但学生还是可以比较容易地得出这个结论的。所以将上面流程图中的“i<=3”改成“i<=n-1”即可得到流程图了。
现在只剩下“不断两两比较交换”还需要进一步细化。教师以4个数为例, 回顾刚才的F l a s h动画。
在程序中有些数据规律不很明显, 教师用表格列出来, 以提高学生分析数据的有效性和准确性, 规律也更易找出来。
教师引导学生发现规律:每次都是从最后一个数开始比较, 最后一个参与比较的数的下标与比较的遍数有关, 即遍数+1。教师让学生思考:n个数的情况如何比较呢?学生讨论共n个数、各遍比较的情况, 特别是第i遍, 完成下表的填写:
这里又需要用一个变量来标识正在参加比较的数组元素的下标, 引进变量j:记录一遍处理过程中, 当前数组元素的下标。
小结论:共n个数, 第i遍处理时, j的值从n到i+1之间递减, 每次d (j) 与它的前一个数d (j-1) 进行比较。
设计意图:本节课最大的难点就是变量j的取值范围, 尤其对“它的终值为什么是i+1”学生更是难以理解, 因为它是在动态变化的。由特殊的4位数开始找出规律, 然后归纳推广到一般的n个数就相对简单。我花了较长的时间让学生自己探讨, 目的是经过充分思考得出的结论才会记忆深刻。
为了加深学生理解, 我一边讲解, 一边手绘了如下的图形, 以更直观地来说明这个问题:当要进行第i遍处理时, 即要找第i个最小数时, 此时前面i-1个最小数已经找到 (阴影部分) , 这部分不需要再参与以后的两两比较, 所以第i遍处理时, 第一次两两比较应该是d (n) 与它的前一个数d (n-1) 。以此类推, 最后要比的是d (i+1) 与它的前一个数d (i) 。至此, 该轮最小数就冒到第i个位置了。所以最后一个的“它”的位置应该是i+1。
“如果下面一个数比上面一个数小, 就交换”。这是一种分支结构。教师用生活中的实例说明 (如果天气好的话就去打球;如果60分以上就显示合格, 否则就显示不合格) , 并简单回顾分支结构的流程示意图。
设计意图:程序实例生活化学生更容易接受。
师生得出不断两两比较交换的流程图, 如流程图4。
至此, 所有问题、难点我们都全部细化, 一一解决了, 现在将流程图4“两两比较交换”纳入流程图3, 即得下面的总流程图。
n:参加排序的数组元素总个数。i:记录正在执行的排序的遍数, 由1变到n-1。j:记录一遍处理过程中, 当前数组元素下标, 由n变到i+1。说明:虚线框部分即为第i遍处理时“不断两两比较交换”的流程图。
当出示这个总流程图时, 学生发出惊叹, 他们不太相信自己的眼睛。
师:不要惊讶, 这的确是我们通过自己的努力一起画出来的。看来设计算法、画出流程图也并不是什么难事。只要我们有信心, 由浅入深还是可以解决的。
教师说明这个总流程图各部分的作用, 并留几分钟让学生自己消化新学知识。
4. 学生体验冒泡排序“算法执行过程”
让学生采用“单步执行”模式观看本书配套辅助软件“运行体验”文件夹中的“冒泡排序.s w f”, 体验冒泡排序的算法执行过程。
5. 流程图→程序语言
可以通过对两个变量和两数互换语句的解决, 最终得到主要参考代码。
(1) i:记录正在执行的排序的遍数, 由1到n-1
for i=1 to n-1
冒起一个最小数 (循环体)
next i
(2) j:记录一遍处理过程中, 当前数组元素下标, 由n变到i+1
for j=n to i+1 step-1
d (j) 与它的前一个数d (j-1) 进行比较
next j
(3) d (j) 与d (j-1) 互换
k=d (j) :d (j) =d (j-1) :d (j-1) =k
教师可以利用酱油和米醋互换来做比喻, 引导学生实现两数互换的方法。
对照总流程图, 自上往下, 写出主要参考代码:
for i=1 to n-1'i记录正在执行的排序的遍数, 由1变到n-1
for j=n to i+1 step-1'j记录一遍处理过程中, 当前数组元素下标, 由n变到i+1
互换
设计意图:因为已学过VB基本知识, 学生对赋值、选择和循环这三种语句都有基础, 所以流程图画出来以后, 转换成程序语言并不太难。教师趁热打铁, 顺理成章地完成了主要代码的编写, 为下节课学生上机实践打下基础。
显示参考代码后, 教师要引导学生养成良好的习惯, 使用规范的代码书写格式, 不仅有利于程序的调试, 还增加了可读性。
6. 拓展:优化冒泡排序
教师让学生到网上搜索冒泡排序的改进方案。
设计意图:为寻找解决问题的最佳方案而产生更好的学习目标。尤其是一些理科比较好, 又对程序设计比较感兴趣的学生, 离开机房的时候还一路在讨论着。
7. 作业设计
设计一个评分系统的流程图:有n个评委, 最后得分为去掉一个最高分与一个最低分后的平均分。
五、问题研讨
1. 如何用人的思维模拟计算机的工作过程
我让学生上来排队演示, 本想让他们用不同方法, 以便引出各种排序方式。但后来发现这太难了。因为人是有眼睛和原有认知能力的, 有些事想当然就可以完成判断。但计算机与人不同, 它看不见、摸不着这些数据, 不可能像人一样来完成任务。解决问题的关键, 就是要把人解决问题的每一步思维过程描述出来。这也是所有学程序的人尤其是初学者感觉最难的地方。并且, 程序设计思想并不是一下子就能培养的, 我们高中阶段只能是慢慢引导学生学着去分析问题, 将问题解决方法步骤化。所以课后我一直在思考, 是否可以在上这部分内容之前给学生布置一个任务:闭上眼睛, 将十根乱排的长短相差不大的小木棍从短到长排起来, 要求每次最多只能比较两根。事后我也请一些人做过实验, 发现每个人都有自己不同的想法, 但都可以从程序设计的各种排序法中找出原型。
2. 细节也不容忽视
电脑资料
我们知道有序数组对于快速算法是致命的，如果不对快速算法做任何优化，那么快速算法将会达到最差运行时间
快速选择算法里面也是一样的，应该避免输入有序数组导致的分组极度不平衡的情况，所以我们就做了下面的优化，在进行快速选择之前，首先从数组的头部，中部，尾部选出三个元素出来，找出这三个元素中第二大的元素，并与数组的最后一个元素进行交换，这样我们就可以避免分组极度不平衡的情况了，但是只是能保证避免分组极度不平衡的情况，还是有可能分组不平衡的,下面我们要讲解的BFPRT选择算法可以很好的做到平衡分组
我们在每次迭代或者递归进行之前加上下面的代码
/** 省略了好多代码 */if(leftBorder >rightBorder) return ; // 这里采用快速排序的思想来完成 // 为了避免最差的情况发生 int mid=(leftBorder+rightBorder)/2; int midPos = rightBorder; // mid元素是第二大的 if((array[leftBorder] >array[mid] && array[mid] >array[rightBorder]) || (array[leftBorder] < array[mid] && array[mid] < array[rightBorder]) ) midPos = mid; // left元素是第二大的 else if((array[mid] >array[leftBorder] && array[leftBorder] >array[rightBorder]) ||(array[mid] < array[leftBorder] && array[leftBorder] < array[rightBorder]) ) midPos = leftBorder; if(midPos != rightBorder) exchange(array , midPos , rightBorder); int i = leftBorder-1; int j = leftBorder; /** 省略了好多代码 */
BFPRT选择算法
上面我们讲过，在快速排序算法里面如果主元选择的不合适，将会导致快速排序算法的分组极度不平衡，这样大大降低了快速选择算法的效率
topSort.h
#ifndef __TOPSORT_H#define __TOPSORT_Hstruct graph;struct listNode;typedef struct graph *Graph;typedef struct listNode *Vertex;struct graph{ int numberOfVertex; Vertex *vertexs;};struct listNode{ int indegree; int vertexnumber; Vertex next;};void topSort(Graph G);Graph initinalizeAdjList(int listSize);Graph insertAdjList(Graph G,int pos,int a[],int N);#endif
topSort.c
#include topSort.h#include queue.hvoid topSort(Graph G){ Queue Q; Vertex V,W; int counter=0; int i; Q=createQueue; for(i=1;i<=G->numberOfVertex;i++)//找到入度为0的点，将它们入队列 { if(G->vertexs[i]->indegree==0) EnQueue(G->vertexs[i],Q);} while(!isEmpty(Q))//删除该点，然后将其相邻的点入度减1，再重新检测入队列 { V=DeQueue(Q); printf( %d ,V->vertexnumber); counter++; for(i=1;i<=G->numberOfVertex;i++) { if(isAdj(G->vertexs[i],V)) { if((--G->vertexs[i]->indegree)==0) EnQueue(G->vertexs[i],Q); } } } if(counter!=G->numberOfVertex) { printf(Graph has a cycle); exit(-1); } deleteQueue(Q);}Graph initinalizeAdjList(int listSize)//初始化一个邻接表，就是创建一个指针数组，每个元素只想一个节点{ Graph G; int i; G=(Graph)malloc(sizeof(struct graph)); if(G==NULL) { printf(out of space); exit(-1); } G->numberOfVertex=listSize; G->vertexs=(Vertex*)malloc(sizeof(Vertex)*(listSize+1)); for(i=1;i<=listSize;i++)//这里简单的直接给出节点编号，实际中可以用哈希的方法来获得 { G->vertexs[i]=(Vertex)malloc(sizeof(struct listNode));//初始化节点 G->vertexs[i]->vertexnumber=i; G->vertexs[i]->next=NULL; } return G;}Graph insertAdjList(Graph G,int pos,int a[],int N)//根据给出的数组来给邻接表插入元素{ int j; Vertex v,w; G->vertexs[pos]->indegree=N; w=G->vertexs[pos]; for(j=0;j
main.c
2008-09-09Python httplib，smtplib使用方法
2014-03-03python fabric实现远程操作和部署示例
2014-02-02python控制台显示时钟的示例
2013-11-11python创建和使用字典实例详解
2012-08-08Python运行的17个时新手常见错误小结
2014-03-03用Python和MD5实现网站挂马检测程序
2013-12-12videocapture库制作python视频高速传输程序
2008-11-11Python GAE、Django导出Excel的方法
2014-04-04python计算圆周长、面积、球体体积并画出圆
★ python选择排序算法实例总结
★ 算法实验体会与总结怎么写
★ 中考语文语句排序方法总结
★ 小班数学教案排序
★ 小论文格式排序
★ 水果排序数学教案
★ 文件数字排序范文
★ amcl定位算法学习个人总结1
★ 原材料计划成本核算法
关键词：枚举,秩,排序,选择算法,并行计算
排序与选择是计算机处理数据的重要工作。经过长期的研究,人们提出了许多排序算法,包括插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序和基数排序等。目前,排序算法是《数据结构与算法设计》课程的重要组成部分。
选择算法包括k-选择和(m,n)-选择。k-选择是指从数据序列中选出第k个最小(或最大)的数据元素;(m,n)-选择是指从n个数据序列中选择出m个最小(或最大)的数据元素[1]。选择算法更适用并行处理,且多采用比较网络实现。
基于枚举的排序称为枚举排序(Enumeration Sorting),也称为秩排序(Rank Sorting)[2]。在串行环境下,枚举排序是不可取的,但是,由于枚举比较本身具有潜在的并行执行的可能性,使得它在并行排序中大放异彩[3]。文献[1] [2][3]介绍了串行枚举排序和基于MIMD-CREW模型上的并行枚举排序。本文介绍多核处理机上Open MP编程环境下的并行枚举排序与并行选择算法。
1 并行枚举排序
所谓的“秩”是指数据集合中比自身小的数据元素的个数,它可以直接反映该数据在排序数据序列中的位置。枚举排序的基本思想是:逐一地计算每个数据的“秩”,然后根据“秩”调整数据的位置,最终实现排序。
并行枚举排序由数据播送、秩计算和数据收集三个过程组成[3]。与MIMD-CREW模型上的并行枚举排序算法相比,多核处理器上的并行枚举算法显得更加简单,其基本思想是将待排序数据进行分组,由多个处理机并行地对各分组进行秩计算,最后根据秩调整数据的位置,得出排序序列。
1.1秩的计算
在待排序数据序列为S[0,…,n-1]中,计算数据元素S[k]的秩就是逐一地统计比S[k]小的数据元素的个数。算法描述如下:
1.2 各分组数据元素秩的计算
并行枚举排序的关键环节就是用多个处理机并行地进行秩计算。每个处理机负责一个或多个分组,逐一地用分组中的数据元素与所有(全局)的待排序数据进行比较,计算分组中各数据元素的秩。对于每一个处理机而言,这一个过程是串行的。为保证处理机能准确地找到自己的分组,需要给出分组的起始位置和长度。排序算法描述如下:
算法中,for循环的时间复杂度为 ,循环内的Index(S,sLen,S[i])时间复杂度为 ,故该算法的时间复杂度为。
1.3 并行枚举排序算法
多核处理器是分布式Cache的共享存储并行计算模型[4]。数据传播过程主要体现为读共享,而写数据时,每个处理机所写的存储单元是明确的、相对独立的,因此不存在冲突问题,计算可以达到最大程度的并发性。为确保处理机的均衡,提高算法效率,必须把处理机数作为分组依据之一。算法用Open MP编程模型上的C++语言描述如下:
假设待处理数据为n个元素,处理器有p个运算核,,则分组计算秩的时间为n2/p,收集过程的时间为n/p。根据n2/p与n2的关系可知,所获得的性能几乎与运算核数目p成正比。
2 并行枚举选择算法
根据(m,n)选择网络的原理[1],只要从每个分组中选择m个最小的数,就可以覆盖n个数据中m个最小的数。因此,(m,n)-枚举选择算法与(m,n)-选择网络的处理方法一样:对n个数据进行分组,然后从每个分组中选择m个最小的数组成新的待选择数据,再分组,再选择,直到找到m个最小的数据为止。不同的是,(m.n)选择网络采用硬件实现,容易实现多路归并选择。对于多核处理器,每个处理机的执行可以视为一个分组上的串行(m,n)-选择,所以,并行枚举(m,n)-选择算法可以建立在串行(m,n)-选择的基础上。
2.1 串行枚举(m,n)-选择算法
为减少计算秩的次数,提高算法效率,先定义left Cmpd和right Cmpd两个参照数,令left Cmpd始终保存秩小于m的最大数,right Cmpd始终保存秩大于m的最小数。初始时,left Cmpd等于一个无穷小量,right Cmpd等于无穷大量。选择处理过程中,任何小于left Cmpd的数据都是所需的m个数据之一,不必再计算它的秩,直接存入输出数组中;任何大于right Cmpd的数都不在所需的数据范围之内,不做任何处理;而介于left Cmpd和right Cmpd之间的数,则可能是所需的数据,需要计算它的秩,如果秩小于m,则是所需的数据,将其存入输出数组中,并调整left Cmpd的值,使之左向逼近m;如果秩大于m,则不是所需的数据,直接调整right Cmpd的值,使之右向逼近m。算法描述如下:
算法中,最好的情形下需要进行1次求秩和m次比较,复杂度为O(n);最坏的情形下需要进行(n-m)次求秩和m次比较,复杂度为O(n2)。
2.2并行枚举(m,n)-选择算法
并行枚举(m,n)-选择算法的基本思想是:将待查找数据进行分组,由p个处理机并发地调用串行枚举(m,n)-选择算法对各分组进行(m,n)-选择,再将各分组选出的m个最小数据重新组成待查找数据,递归地进行并行枚举(m,n)-选择,当待查找数据元素的个数足够小(分组数为1)时,直接进行串行(m.n)-枚举选择。算法描述如下:
串行(m,n)-枚举选择算法的最坏时间复杂度为O(n2),采用并行处理后,相当于每个处理机只需要处理n/p个数据,即加速比为接近p2。
2.3并行枚举k-选择算法
K-选择可以视为特殊的(m,n)-选择算法。因此,并行枚举k-选择可以先进行m=k的并行(m,n)-选择,再对找出的k个数据进行串行k-选择。算法描述如下:
该算法的时间复杂度主要取决于并行枚举(m,n)-选择的时间复杂度。因此,其时间复杂度与并行枚举(m,n)-选择算法的时间复杂度相当。
3 结束语
【4.4排序算法设计】推荐阅读：
c语言排序算法总结06-25
算法教学设计09-15
算法分析及设计大作业07-09
规律排序教案06-17
初中语文排序题06-03
《有趣的排序》教学反思05-24
《按规律排序》教学反思09-07
《数据结构》实验报告——排序05-30
中班数学教案趣味排序06-28
语句排序题练习题07-01
