排序大班教案

排序大班教案（精选14篇）

篇1：排序大班教案

活动目的

1.能按照物体的高矮、厚薄、宽窄的差异进行10以内物体的正逆排序。

2.初步理解序列中量地相对性、可逆性、传递性。

3.能够与同伴合作完成排序活动，并大胆讲述操作过程和操作结果。

4.初步培养观察、比较和反应能力。

5.引导幼儿对数字产生兴趣。

活动准备

1.长度一样宽窄不同的纸条每人10张

2.记录纸，彩笔每人一套。

活动过程

1.请幼儿按宽窄排序，感知量地可逆性。

(1)请幼儿随意取出4张彩纸，按由窄到宽进行排序，并用与彩纸对应的彩笔将顺序记录下来，说一说自己排序的方法，如目测、重叠。

(2)请幼儿按由宽到窄的顺序排序，并记录结果。比一比，说一说纸条顺序有什么变化。

2.再次排序，感知量地相对性。

(1)请幼儿随意增加2张彩纸，给6张纸条再次按由宽到窄的顺序排序。并记录结果。

(2)请幼儿将记录结果与第二次的记录对比一下，说一说原来的3张纸条排序有什么变化。

3.第三次排序，感知量地传递性。

请幼儿取出最窄和最宽的彩纸，说一说两张纸条跟其他纸条比，按照由窄到宽的顺序排，它们的位置有没有变化。

4.请小朋友比高矮，再次感知量地可逆，相对性。

5.到教室中寻找可以排序的物体，感知物体的高矮、厚薄。

(1)请幼儿到教室里找一种可以比较厚薄、高矮的物体，如图书、积木、桌椅、玩具柜等，看谁比较的数量多。(www.2baobao)也可自由结伴比高矮。

(2)请部分幼儿说一说找的哪种物体，找了几个，按什么顺序排序，是用什么方法进行比较的。

(3)教师根据情况，随机提出不同排列顺序，再一次感知量的不同性质。

活动反思

孩子在做中学，所以本次课程我给幼儿准备了足够的材料，让孩子在操作中感知量的可逆性、相对性和传递性。数学来源于生活又应用与生活，所以在活动最后，布置亲子小作业，找一找生活中能够排序的东西，记录下来，和小朋友互相交流、分享。

篇2：排序大班教案

1、通过操作活动，学习按物体的颜色排序，尝试自设排序规律。

2、培养幼儿的观察力、创造力。

3、激发幼儿对数学活动的兴趣，培养幼儿的爱心。

二、活动准备：

1、动动板，棋子。

2、各式各样的房子图片。

三、活动重点、难点：

能按物体颜色有规律的排序，掌握排序方法。

四、活动过程：

(一)听音乐，取学具。

(二)复习导入。

老师刚接到了小兔的电话，它告诉我：森林里的小动物们都盖了新房子，想修一条漂亮的小路，想请我们班的小朋友们帮助设计一下，你们愿意吗?

出示三角形的房子，让幼儿用两种颜色的棋子按规律设计小路。

1、幼儿操作，教师巡视。

2、引导幼儿说出排序的规律。

○○○○ (abab形)

红绿红绿

○○○○ ○○○○ (aabb形)

红红绿绿红红绿绿

○○○○ (baba形)

绿红绿红

○○○○ ○○○○ (bbaa形)

绿绿红红绿绿红红

○○○○○○(abbabb形)

红绿绿红绿绿

○○○○○○(baabaa形)

绿红红绿红红

3、教师小结：

(三)授新课：学习用三种颜色按一定规律排序。

1、出示平顶房，让幼儿尝试操作;

2、请个别幼儿在演示板上演示铺的路;

3、教师小结;

4、鼓励幼儿大胆创新，设计出不一样的排序规律;

5、幼儿操作，师巡视;

6、鼓励幼儿说出自己的操作方法，师小结。

○○○○○○(abc形)

红绿黄红绿黄

○○○○○○○○○○○○(aabbcc形)

红红绿绿黄黄红红绿绿黄黄

○○○○○○○○ (abbc形)

红绿绿黄红绿绿黄

○○○○○○○○ (abcc形)

红绿黄黄红绿黄黄

○○○○○○○○ (aabc形)

红红绿黄红红绿黄

师：我们班的小朋友太厉害了，帮小动物们设计出这么多有规律漂亮的小路，小动物们很高兴，还说谢谢我们呢?

(四)听音乐收棋子，送学具回家。

(五)延伸游戏《盖房子》

1、引导语：前不久，日本发了很大的地震，把日本小朋友的房子给震倒了，他们没地方住了，我们帮他们盖一座新房子吧。

2、提出要求：可盖楼房，也可盖平房，要按一定规律排。

篇3：大班语言教案:谁咬了我的大饼

1.通过想象、猜测、讲述, 发展语言表达能力和想象力。

2.仔细观察动物的咬痕, 学习角色间的对话。

3.体会故事角色的情感变化, 感受活动的乐趣;感受故事的有趣, 幽默的情节。

【活动准备】

PPT、电子白板、自制大饼、实物饼干若干。

【活动过程】

一、出示课件, 引起幼儿欣赏兴趣

1.出示图片, 观察大饼。

师:小朋友, 这是什么?这是一块怎样的大饼?这块大大的、圆圆的大饼会是谁做的?

2.根据图片提问, 引出问题。

师:小猪做了一块很大的饼, 累得睡着了。当他醒来一看, 发现了什么?

二、观看课件, 欣赏绘本, 了解故事主要内容

1.逐页观察大书, 以“牙印”为线索, 理解故事内容。

(1) 小猪问小鸟:是你咬了我的大饼吗?小鸟说:不是我, 你看, 啊呜。

师:是小鸟咬的第一口大饼吗?为什么?为什么小鸟的咬痕是尖尖的呢?

(2) 小猪又去问谁啦?他会怎么问呢?小兔子会怎么回答?

2.借助图片, 通过对比动物牙印描述不同动物的牙印特征。

(1) 小猪很着急, 他找到了三个动物, 是谁? (出示图片) 想一想小猪会怎么问?小动物又会怎么回答?

(2) 幼儿相互讨论。

(3) 师:小猪问了谁?他是怎么问的?是不是狐狸咬的?为什么?

(4) 师:小猪接下来又去问谁了?鳄鱼的牙齿是什么样子的?那是它咬的吗?

(5) 师:最后小猪去问了谁?河马是怎么做的?我们一起来学学河马的动作。大饼怎么了?为什么大饼会被咬掉一大半?

(6) 这么大的大饼, 只剩下一点点了, 小猪的心情会是怎么样的?它会怎么想?最后小猪饿得肚子咕咕叫, 啊呜, 它也在大饼上咬了一口。“吧唧吧唧”, 它一边嚼着大饼, 一边想:究竟是谁咬了我的大饼?

(7) 小朋友, 你们知道是谁咬了大饼吗?为什么?

三、完整倾听故事, 感受故事幽默的情节

故事的名字是什么?

四、活动延伸:玩游戏, 体验游戏的快乐

篇4：幼儿园大班音乐课教案

关键词：幼儿音乐；音乐教案；《刷牙歌》

在幼儿音乐课教学中，教案设计有很重要的作用。笔者以小袋鼠蒙氏教育音乐教材中《刷牙歌》为例设计教案，基于教学设计意图，明确教学目标、重难点、准备，设计教学活动，进行教学反思，希望可以对幼儿音乐教学有所帮助。

一、教学设计意图

《幼儿园教育指导纲要》中提出：“在支持、鼓励幼儿积极参加各种艺术活动并大胆表现的同时，帮助他们提高表现的技能和活动”。“刷牙歌”一课，要求在教师的指导下，幼儿感受美、表现美，在音乐学习的同时，体验自由表达、创造快乐。《刷牙歌》作为一首幼儿歌曲，节奏轻快，歌词朗朗上口且富有童趣。这节课的教学设计，旨在让幼儿在简单的儿歌学习中，理解歌词内容，熟悉歌曲旋律，编排舞蹈动作，创编刷牙节奏，享受快乐，同时还让幼儿具有清洁卫生，爱干净的基本认知，体验牙齿健康的情感。

二、教学目标、重难点、准备

【教学目标】理解歌词内容，熟悉歌曲旋律，编排舞蹈动作，创编刷牙节奏，享受快乐，同时让幼儿具有清洁卫生，爱干净的基本认知，体验牙齿健康的情感。

【教学重难点】倾听《刷牙歌》，创编刷牙节奏，创编象声词，并能与《刷牙歌》间奏连贯表演；学习《刷牙歌》，表现刷牙美感。

【教学准备】幼儿：具备正确的刷牙习惯，牙齿保护的基本常识；

教师：认真备课；

教具：光盘、多媒体、课件、图片、牙刷实物。

三、教学活动

1.倾听歌曲，学唱歌曲，了解《刷牙歌》内容

教师先出示课件，演示懒洋洋牙疼的表情，提出问题：“小朋友们，大家看懒洋洋怎么了？”幼儿答出牙疼的答案。

【设计意图】通过动画课件演示，选择幼儿熟悉的卡通人物，吸引幼儿眼球，以问题的形式，引出课题。

播放《刷牙歌》：

小牙刷，手中拿

我呀张开小嘴巴

刷左边，刷右边

上下里外都刷刷

早上刷，晚上刷

刷得牙齿没蛀牙

张张口，笑一笑

我的牙齿刷得白花花

在儿歌播放的同时，给幼儿播放歌词内容视频和图片，再次激发幼儿的兴趣，让幼儿熟悉歌词，教师提出问题：“小朋友们，谁能告诉大家歌词里唱了什么内容呀？”

【设计意图】幼儿听着歌曲，看着视频，借助视频熟悉歌词，理解歌词内容，一目了然地学习歌曲，对歌曲产生兴趣。

在幼儿非常熟悉歌词内容的基础上，教师反复给幼儿播放歌曲，一句一句地教给幼儿歌唱，让幼儿记忆歌词内容，学习完整演唱。

2.探索尝试，自编动作，表演刷牙歌律动

让幼儿合唱《刷牙歌》，熟悉歌曲旋律，一边唱歌，一边合着节拍做刷牙动作。在幼儿学习正确刷牙动作后，教师引导幼儿创编动作，向幼儿提问：“小朋友们，在刷牙的时候，除了歌曲中刷左边，刷右边，上下里外都刷刷的动作，还有什么刷牙动作，大家知道吗？谁能做出动作，我们一起学一学。”

同时，教师结合歌曲间奏处，引导幼儿回忆刷牙情境，创编刷牙象声词，如表示快乐的节奏和“啦啦啦啦，嘻嘻嘻嘻”等象声词，“咕噜咕噜噜”“咕噜噜噜”等漱口的水声。

在幼儿创编结束后，教师应集中反馈，让幼儿完整歌唱，注意间奏处的节奏、象声词。

【设计意图】结合《刷牙歌》旋律，引导幼儿创编刷牙动作，创编刷牙象声词，跟随刷牙歌节奏表演律动，引导幼儿发挥想象，提升幼儿创编的动作，丰富歌曲舞蹈美，将创编的动作连贯成完整的律动舞蹈。

3.拓展学习，完整跳舞，体验律动快乐与美感

教师和幼儿一起听《刷牙歌》，做刷牙动作，跟随节拍发出象声词，做律动，探讨舞蹈队形，完整连贯地跳舞，注意跳舞时，刷牙的表情、动作，感受刷牙美，享受快乐情感，一起跳，体验歌曲快乐与跳舞美感。

【设计意图】此环节为总结归纳与拓展应用阶段，在幼儿学习歌曲和创编舞蹈的基础上，获得正确刷牙的基本认知，通过音乐学习，养成正确的生活习惯。

四、教学反思

《刷牙歌》音乐课符合幼儿认知规律，歌曲节奏鲜明，歌词朗朗上口。在整节课中，教师设计“懒洋洋牙疼”“听歌曲”“创编律动”“完整跳舞”四个亮点，能够有效激发幼儿的高昂兴趣，积极引导幼儿参与音乐活动。刷牙歌音乐课的教学相对开放，幼儿能够通过理解歌词内容，结合生活刷牙情境还原，结合自身理解表现律动。教师应顺势而导，紧抓幼儿思路，注意幼儿表现，鼓励幼儿发挥想象力，创编刷牙律动，规范幼儿刷牙动作节奏，给幼儿自由的表现机会，让音乐课活起来。从音乐课教学实践看，整节课幼儿都积极参与，教师和幼儿互动较多，增强了幼儿音乐学习的快乐感。

参考文献：

吴巧云.激发幼儿音乐活动兴趣点滴谈[J].考试周刊，2016（73）：187.

篇5：排序大班教案

学习有规律排序的方法

材料：

彩色串珠数个，或是几何图形的积木数

要点：

方法一，掌握两种物体的排序

（1）同是圆形串珠，一个红色，一个绿色，引导孩子进行红、绿、红、绿……排序；

（2）可以进行相同颜色不同形状的积木的排序。

方法二，掌握3种物体有规律的排序

（1）相同形状不同颜色的排序。

篇6：排序大班教案

我班幼儿在开展叙事性整合课程《西瓜船》主题活动时，喜欢操作水果卡片，在认识了许多水果的同时，幼儿对数学操作活动产生了初步的兴趣。教师通过观察发现，幼儿会进行无意识的分类操作，并尝试给卡片无规律的排序，结合小班幼儿对数的认识和感受，特设计了此活动，目的是让幼儿在主动、愉快的活动中，进一步培养幼儿对数学的兴趣，并学习观察、操作，自然习得按简单规律排序的方法。

二．活动目标：

1.对周围生活中有趣的数学排序现象产生兴趣。

2.在活动中，学习观察、操作，发展思维能力。

3.学习按简单的规律进行两种以上的排序。

三．活动准备：

水果卡片人手一套，黑板、磁铁。

四．活动过程：

1．幼儿，自由探索，尝试排序。

教师请幼儿自由操作水果卡片，摆一摆，排一排，并说说自己是怎样和卡片玩的？教师巡回观察。培养幼儿对物体的观察和操作能力。

2．提升经验，学习排序。

请幼儿上来演示自己是怎样给水果卡片排队的？说一说你是用什么方法排的？学习按简单的排列规律进行排序。

3．加深认识，练习排序。

引导幼儿：你也会这样给水果卡片排队吗？幼儿进行排序操作，练习按简单的规律进行两种以上的排序，教师个别指导。

篇7：排序大班教案

活动目标：

1、能够细致观察并发现排序的规律。

2、能够自创、合作创设另种或两种以上的规律。

活动准备：

1、各色图形卡片若干（幼儿操作用），16张长条白色卡纸（上面画有曲直不同的线）展示板一张。

2、音乐（军民大生产）、课件

3、五彩塑料夹若干、硬纸卡圆形4块、地垫若干

活动流程：

一、初步感知有规律排序（激趣）

1、自身感知：

（1）敲小鼓（XX）孩子拍手转圈、跺脚进入→“刚才小手小脚是怎么做游戏的”？发现规律→小结：原来这是按规律延续的舞蹈动作。

（2）“小手小脚能跳舞，胳膊有没有这个本领呢？我们来试试看”（尝试）“根据孩子的表现（......动作..）宝宝能不能排成一排有规律的把这两个动作做出来呢→（展现）”真厉害！老师奖励你“（拍手：拍手、大拇指、双拍手、大拇指......）

（3）“你看，小手、小脚、胳膊都能有规律地来游戏，我们可不可以学小猫和小狗的叫声来进行有规律地声音排序呢”先和同伴商量一下怎么排？现在小猫和小狗一边叫一边做回小凳子。（喵..汪汪...喵...汪汪.喵...）

小结：刚才小朋友做的游戏，都是一组一组有规律延续下去的，这就是有规律的排序。

2、拓展感知：

“现在老师请你做小小侦查员，四下侦查一下活动室里有没有按规律排序的东西？我给你1分钟的时间，可以边走边找，但是要注意轻声慢步不要影响到别人。（找→坐回→叙述→认同）有规律排序的物体真的在我们活动室有好多啊！

现在你再回忆一下，在家里、在路上、在广场和公园里有没有按规律排序的地方？（想象、回忆→课件：生活中有规律排序的场景）

小结：有规律排序的物品真是无处不在啊，它使我们的生活变得更美丽、更方便！

二、操作感知有规律排序,引导幼儿探索发现不同的排序方法。

“刚才小朋友做了小侦查员和小小观察员，我不知道你的建筑能力怎么样”？文盛家园又新盖了一栋50号楼，就在我们幼儿园的楼后边，物业管理处把设计小花园的任务给了我们班的小朋友，今天我们先设计图纸，设计好了送给他验收，你有信心完成吗”？

“好，现在我们先进行一个小任务，用各种颜色的“石头”设计花园的围墙，围墙必须是按规律排序的，争取设计的和别人不一样，有创造力的人才是最好的建筑师”（设计→师观察发现→展示点评，突出：按形状不同排列、按物体量的差异的特定规律排列、按不同形状物体数量递增规律排列等排序特征）

教师小结：原来同一种的物品可以按不同的规律进行很多不同的排法。

三、验证操作：合作感知多种规律排序的有趣方法。

1、“有了漂亮的花园围墙，我们进行下一个“大工程”铺两条长长的路，铺的路不仅要美观而且要通往花园的各个地方。（1）、现在请自己找8个好朋友一组（2）1分钟商量好设计方案（3）到材料处领好“大理石地面砖”开始铺路。

2、巡视发现有意识引导→评价（孩子叙述地面砖的排列规律）

篇8：单台机器排序问题中工件的预排序

排序问题是组合最优化理论中应用十分广泛的领域。在实际生产中,某些工件的加工必须先于另一些工件的加工。排序就是要寻找一个加工次序,既要满足约束条件,又要使某种指标达到最优。在本文中,J ={J1,J2,…,Jn}是所有的工件构成的集合,其中Jj表示第j个工件。如果要求工件Jj完工后才能开始加工工件Jk,那么称工件Jj是工件Jk的前工件,又称工件Jk是工件Jj的后工件,并称这两个工件之间存在先后约束。工件有先后约束的单台机器排序问题(记为1|prec|∑fi)是对n个工件在满足工件之间先后约束的条件下寻找使目标函数∑fi为最小的排法。Schrage 和Baker[1] 在1978年第一次提出了用动态规划方法解工件有先后约束的单台机器排序问题。同时他们也提出了一个标号算法,对实施动规划和计算机编程是很有帮助的。对于编号为j的工件,L(j)=t(j)-b(j)+1是它的标号,其中b(j)表示所有编号小于j而且是工件j 的前工件的标号之和,t(j)表示所有编号小于j的工件的标号之和。L(J)=${\displaystyle \sum _{j=1}^{n}L}(j)$表示所有工件的标号的和。

陈敏超等[2]提出的编号算法可以判别有向图是否存在回路,并对没有回路的有向图中的点进行编号,使得任何一个工件的编号比它的后工件的编号要小,比它的前工件的编号要大。显然,如果对顶点采用不同的编号,这两种编号都能使得前工件的编号小于后工件的编号,但是这两种编号所对应的L(j)是不同的。因此,如何对工件进行预排序,即如何设计编号算法使得前工件的编号小于后工件的编号,且L(J)最小,是一个值得深入研究的问题。

本文主要研究有先后约束的单台机器排序问题中工件的预排序问题。对于工件先后关系呈链状结构和树形结构的单台机器排序的工件预排序问题,我们将分别给出工件的编号算法,并对这些算法的性能作一些分析。

2 主要结果

对于单台机器排序问题,给定一个工件集J,把工件看作图中顶点,对于任意两个不同的顶点vi和顶点vj,如果vi是vj的前工件,则作一条由vi指向vj的有向边,这样就构成了一个有向图G。

2.1 链状结构的有向图

算法1 对链状结构的有向图,一旦开始对一条链进行编号,只有对这条链的所有的顶点都编完号后,才能对其他的链进行编号。

定理1 对链状结构的有向图按照算法1进行编号,得到的该编号所对应的顶点标号之和L(J) =(1+l1)(1+l2)…(1+ln)-1,跟链的编号的先后顺序无关,其中n是链的条数。

证明 如果链状结构的有向图有n条链,不妨设这n条链分别L1,L2…,Ln,它们的长度分别为l1,l2,…,ln,下面证明L(J)=(1+l1)(1+l2)…(1+ln)-1。

当n=2时

情形1 先对L1的顶点编号,后对L2的顶点编号,得到的编号所对应的顶点标号(见下表)。

L1上顶点的标号:

L2上顶点的标号:

由上可知:

L(J)= l1+l2(l1+1)=(1+l1)(1+l2)-1。

情形2 先对L2的顶点编号,后对L1的顶点编号,类似于情形1可得:

L(J)= l2+l1(l2+1)=(1+l1)(1+l2)-1。

综上所述,按照算法1,无论先对L1编号还是先对L2编号,最终得到的L(J)是相等的,都是l1+l2+l1l2。

假设当n=k时,结论成立,即:

L(J)=(1+l1)(1+l2)…(1+lk)-1。下面证明当n=k+1时结论也成立。

假设最后标号的链是Lp,由前面标号的k条链得到标号的总和为(1+l1)(1+l2)…(1+lp-1)(1+lp+1)…(1+ln)-1。不妨设由前面标号的k条链得到标号的总和为Q,则Q=(1+l1)(1+l2)…(1+lp-1)(1+lp+1)…(1+ln)-1。类似于上面的表格计算,可以得到第k+1条链的标号之和为lp(1+Q)。因此,L(J)=Q+lp(1+Q)= Q(1+lp)+lp,即

L(J)=[(1+l1)(1+l2)…(1+lp-1)(1+lp+1)…

(1+ln)-1](1+lp)+lp=

(1+l1)(1+l2)…(1+ln)-(1+lp)+lp=

(1+l1)(1+l2)…(1+ln)-1。

因此,当n=k+1时结论成立。从而,定理得证。

定理2 对链状结构的有向图,按算法1得到的编号是最优的,即该编号所对应的顶点标号之和最小。

证明 假设图G是使得结论不成立的顶点数最小的具有链状结构的有向图,L*(G)是图G的最优编号所对应的顶点标号之和,L(G)是按算法1得到的编号所对应的顶点标号之和,点v是最优编号中编号最大的顶点,不妨设v的编号为n,则点v是最优编号中最后一个编号的顶点,且它一定是某条链的最后一个顶点。由定理1,L(G)与链的编号先后顺序无关,所以我们最后对v 所在的链进行编号。

根据L*(G)是图G的最优编号所对应的顶点标号之和,可以得到L*(G)≤L(G)。由标号算法公式可以得到:

L*(G)=L*(G-v)+L*(n)=

L*(G-v)+L*(G-v)-b*(n)+1 (1)

L(G)=L(G-v)+L(n)=

L(G-v)+L(G-v)-b(n)+1 (2)

式(2)中L*(G-v)是图G的最优编号去掉编号n所对应的顶点标号之和,和L(G-v)是按算法1得到的编号去掉编号n所对应的顶点标号之和。由标号L的定义可知, L(G-v)-b(n)是除了v所在的那条链以外剩余的链的顶点标号之和。

因为G是使得结论不成立的顶点数最小的有向图,所以,尽管对于图G按照算法1得到的编号所对应的顶点标号之和L(G)不是最优的,但是对于图G-v,按照算法1得到的编号所对应的顶点标号之和L(G-v)是最优的,即

L*(G-v)>L(G-v) (3)

同理可以得到:

L*(G-v)-b*(t)>L(G-v)-b(t) (4)

由公式(1)—式(4),得:L*(G)>L(G),矛盾于L*(G)≤L(G)。因此,对链状结构的有向图,按算法1得到的编号是最优的。

2.2 树状结构的有向图

对于一颗以v1为根的有向树T,如果v1有k个后节点,则把树T的根v1删去得到k个部分,我们把这k个部分称为有向树T的k个分支。有向树T的分支也是有向树。

算法2 对有向树,从树的根开始编号,一旦开始对它的一个分支进行编号,只有对这个分支的所有的顶点都编完号后,才能对其他的分支进行编号。对分支的编号也是按照对有向树的编号原则来编号。

定理3 对于有向树T,设T的根是v1,v1的分支分别记为{V1,V2,…,Vk},按算法2编号,无论先编哪个分支最后得到的L(J)都是相等的,且L(J)=(1+L1)(1+L2)……(1+Lk),其中Li是对分支Vi单独按算法2编号得到的编号所对应的分支Vi的顶点标号之和。

证明 当有向树T 的顶点数≤3时,易证明结论成立。假设当有向树T 的顶点数为n时,结论成立。下面证明当有向树T 的顶点数为n+1时结论也成立。

不妨设有向树T的根是v1,它有k个分支,这些分支分别记为{V1,V2,…,Vk},且最后标号的分支是Vp,则对其余k-1个分支按照算法2编号,得到的编号所对应的顶点标号的总和为(1+L2)(1+L3)……(1+Lp-1)(1+Lp+1)……(1+Lk)。

令Q=(1+L2)(1+L3)……(1+Lp-1)(1+Lp+1)……(1+Lk),按照算法2,先对其余k-1个分支编号,再对分支Vp编号,由标号L的定义,可计算得到分支Vp的编号所对应的标号之和为LpQ。因此,L(J)=Q+LpQ=(1+L2)(1+L3)……(1+Lk)。从而,定理得证。

广义有向星图是一种特殊的有向树,它的根的分支都是有向链。

定理4 对广义有向星图按算法2得到的编号是最优的,即该编号所对应的顶点标号之和L(J)是最小。

证明 假设图G是使得结论不成立的顶点数最小的广义有向星图,L*(G)是图G的最优编号所对应的顶点标号之和,L(G)是按算法2得到的编号所对应的顶点标号之和,点v是最优编号中编号最大的顶点,不妨设v的编号为n,则点v是最优编号中最后一个编号的顶点,且它一定是某个分支的最后一个顶点。由定理1,L(G)与分支的编号先后顺序无关,所以我们最后对v 所在的分支进行编号。

根据L*(G)是图G的最优编号所对应的顶点标号之和,可以得到L*(G)≤L(G)。由标号算法公式可以得到:

L*(G)=L*(G-v)+L*(n)=

L*(G-v)+L*(G-v)-b*(n)+1 (5)

L(G)=L(G-v)+L(n)=

L(G-v)+L(G-v)-b(n)+1 (6)

其中L*(G-v)是图G的最优编号去掉编号n所对应的顶点标号之和,和L(G-v)是按算法2得到的编号去掉编号n所对应的顶点标号之和。由标号L的定义可知, L(G-v)-b(n)是除了v所在的那条分支以外剩余的分支的顶点标号之和。

因为G是使得结论不成立的顶点数最小的有向图,所以,尽管对于图G按照算法2得到的编号所对应的顶点标号之和L(G)不是最优的,但是对于图G-v,按照算法2得到的编号所对应的顶点标号之和L(G-v)是最优的,即

L*(G-v)>L(G-v) (7)

同理可以得到:

L*(G-v)-b*(t)>L(G-v)-b(t) (8)

由公式(5)—式(8),得:L*(G)>L(G),矛盾于L*(G)≤L(G)。因此,对有向星图,按算法2得到的编号是最优的。

算法3 对树形结构的有向图,一旦开始对一棵树进行编号,只有对这棵树的所有的顶点都编完号后,才能对其他的树进行编号。对树的编号按照算法2来编号。

定理5 对树形结构的有向图,假设它有n颗树,这n颗树分别是T1,T2,…,Tn,对它们按照算法2编号,得到的编号所对应的标号之和分别为L1,L2,…,Ln,无论从哪颗树开始编号得到的标号都是相等的, 且L(J)=(1+L1)(1+L2)……(1+Ln) -1。

证明 当n=1时,由定理3可知结论成立。

假设当n=k时,结论成立。下面证明当n=k+1时结论也成立。

不妨设最后标号的有向树是Tp,则对其余k颗有向树按照算法3编号,得到的编号所对应的顶点标号的总和为(1+L1)…(1+Lp-1)(1+Lp+1)…(1+Lk+1)-1。

令Q=(1+L1)…(1+Lp-1)(1+Lp+1)…(1+Ln)-1,按照算法3,先对其余k颗树编号,再对树Tp编号,由标号L的定义,可计算得到树Tp的编号所对应的标号之和为(1+Q)Lp。因此,L(J)=Q+(1+Q)Lp=(1+Lp)Q+Lp,即

L(J)=(1+Lp)[(1+L1)…(1+Lp-1)(1+Lp+1)…

(1+Lk+1)-1]+Lp=(1+Lp)(1+L1)…

(1+Lp-1)(1+Lp+1)…(1+Lk+1)-(1+Lp)+Lp=(1+L1)(1+L2)…(1+Lk+1)-1。

从而,定理得证。

3 结论

在完成多项工作时,如何按时间合理地利用有限的资源,这就是排序理论研究的主题。近年来,由于受到在生产调度和计算机控制系统等领域应用的推动,排序理论已成为组合最优化领域发展最迅速的分支之一。但在实际生产中,某些工件的加工必须先于另一些工件的加工。为此,有时需要对工件进行预排序,即对原来的工件序号进行重新编号,使得先加工的工件的序号小于它的后继工件的序号。本文主要研究有先后约束的单台机器排序问题中工件的预排序,使得工件的编号满足工件之间先后约束的条件,且要使指标L(J)达到尽可能地小。针对工件之间的先后关系呈链式结构的单台机器排序问题,我们设计了一个多项式时间的算法,并证明了这个算法是最优的。针对工件之间的先后关系呈树状结构的单台机器排序问题,我们也给出了一个多项式时间的算法,并证明了这个算法对特殊的树形结构是最优的。另外,结合树形结构的特殊性和标号算法中L的定义,我们猜测我们给出的算法对所有的树形结构的有向图都是最优的。

参考文献

[1] Schrage L,Baker K R.Dynamic programming solution of sequencingproblems with precedence constraints.Opreations Research,1978;26(3):444—449

[2]陈敏超,何荣,唐国春.工件的预排序及其算法的可行性.上海第二工业大学学报,1988;2:82—86

[3] Baker K R,Schrage L.Finding an optimal sequence by dynamic pro-gramming:an extension to precedence-related tasks.Opns Res,1978;26:111—120

篇9：准确排序 语义连贯

高考语文卷常以排序题形式来考查语言的“连贯”，下面就以试题为例，看看如何解答排序题。

一、理顺关系，明确句间条理

一个语段内，句与句之间常常会存在时间顺序、空间顺序或者逻辑顺序，这种顺序不可随意更改。所以，读懂每句话表达的意思，理顺句子间的关系是正确排序的基础。

例1 语意连贯的语段，排序最恰当的一项是______

①使用语言，不仅要用得对，在语法上不出毛病，而且要力求用得好，要有艺术性，有感染力，这就要讲究运用语言的艺术，也就是要讲究一点修辞。

②有意用不符合语法常规的办法取得某种修辞效果是许可的，然而这只是偶一为之，并且要有些特定的条件。

③如果语言不符合语法，说都说不通，就没有什么好的修辞可言。

④语言是用来传递信息、交流思想、表达情感的。

⑤好的修辞，必然是符合语法规律的。

A. ④①⑤③②B. ④③⑤①②

C. ⑤②①④③D. ⑤③④①②

解析： 这五个句子的主要意思分别是：①使用语言要讲究修辞，②特定条件下的修辞，③不好的修辞，④语言的作用，⑤好的修辞。由此可见，这个语段的结构应该是“总分”形式，“总”是指“运用语言要讲究修辞”，“分”即分别论述不同种类的修辞。按照这样的逻辑关系以及上下句的衔接词语，可以判断五个句子的正确顺序为④①⑤③②，答案选A。

二、统揽全局，抓住中心论点

遇到议论性的语段，先抓住中心论点，再分析其他句子是如何围绕论点进行论述的，会使排序变得容易很多。

例2 把下列带序号的句子组合成语意连贯的一段话并填入横线处。（只填序号）

理学家为什么崇古抑律·______古体与律体之辨跟诗歌史联系起来，就是古体的典范——汉魏晋诗与律体的典范——唐诗之辨。

①那么，为什么讲求声律、对偶等形式技巧就是品格低呢·

②他们认为，诗歌的审美方面、形式技巧方面对于人的道德修养没有正面的价值。

③以这种价值观去看诗歌的题材样式，古体诗就高于律诗。

④既然诗歌的审美方面没有价值，本来可以不讲，但是如果要进入到诗歌领域去谈诗的话，那么，在形式方面人为的工巧因素越多，其价值就越低。

⑤抛开诗歌的内容不论，单从形式上看，近体诗要讲求声律、对偶等，这些讲求在理学家看来，是其在品格上低于古体诗的重要原因。

解析：语段开头抛出“理学家为什么崇古抑律”的问题，接下来的句子自然与之有因果联系，我们不难找到⑤，这就构成了语段的中心论点——“理学家崇古抑律，因为从形式上看，古体诗的品格高于律诗”。既然理学家有这样的观点，自然要论证“为什么讲求声律、对偶等形式使近体诗的品格低”，所以⑤后紧跟过渡句①，然后再回答①提出的问题。句子②从“对道德修养的价值”角度出发，说明诗歌的形式技巧价值低，句子④具体分析句子②的观点，句子③得出结论。可见，正确的排序是⑤①②④③。

三、读懂句意，分析陈述角度

在描述某一事物时，语段内前后句子的陈述角度应该一致，首尾相贯。所以，在读懂句意的基础上，可以分析句子的陈述角度，以此为依据进行排序。

例3 依次填入下面一段文字横线处的语句，衔接最恰当的一组是

今天的日子很短，正在自己的脚下悄悄地流逝。______ 。

______，______ 。______ ，______ ，______，经营好每一个今天就等于经营好昨天和明天。

①今天的事应该今天完成，不能推到明天

②脚踏实地，全身心地经营好今天，才会有一个个实在的昨天

③因此，面对今天，我们不要太多地怀念过去

④接力棒交得好，才能走向辉煌的明天

⑤如果总是站在今天望明天，结果明天也会悄悄地溜走

⑥今天是昨天和明天的接力处

A. ⑤①⑥②④③ B. ⑤⑥①④③②

C. ⑥④③②①⑤ D. ⑥②③①④⑤

解析：这是一个议论性语段。句子②⑥讲“今天”与“昨天”及“明天”的关系，句子①③④⑤讲如何处理好“今天”与“昨天”“明天”的关系。语段以“今天”为话题开头，能与之衔接的只能是以“今天”为主语的①或⑥，选项中没有以①开头的，所以可以把答案锁定在C、D之中。我们只需分析句子④②哪一个接在句子⑥后更合适即可。句子④以“接力棒”开头，显然承接了句子⑥最后提出的“接力处”这一概念，所以，应该选C。

四、分析语言，注意整体协调

整体协调指的是句式结构和音韵节奏的协调。句式上，应注意上下文之间整句与散句、长句与短句、主动句与被动句、肯定句与否定句等的对应；音韵上，要关注节奏与押韵。

例4 填入下列句子空白处最恰当的一项是

埋伏和照应需要惨淡经营。埋伏处要能轻轻一笔，若不经意，______。要使读者看不出斧凿痕迹，只觉得

______ ，如一丛花，如一棵菜。虽由人力，却似天成。如果看出来这里是埋伏，那里是照应，______ 。

①照应处要顺理成章，水到渠成

②照应处要水到渠成，顺理成章

③清清爽爽，简简单单

④自自然然，完完整整

⑤便成死症

⑥便太浅显

A. ①④⑤ B. ①③⑥

C. ②③⑤ D. ②④⑥

解析：本题从音韵和谐的角度分析，很容易选择A，因为不难看出句末“成”“整”“症”等字押韵。再结合文段验证一下，首先，从逻辑看，“水到渠成”是“顺理成章”的结果，句子①②中应选择①。其次，语段中把“看不出斧凿痕迹”给人的感觉比做“一丛花”“一棵菜”，意在“天然、自然”，因此，不难选择句子④“自自然然，完完整整”。所以A选项是正确的。

篇10：《排序》大班数学活动教案

1、能够仔细观察，发展观察、比较能力和初步的判断推理能力

2、通过动手操作、比较，发现物体的排列规律。

3、乐于创编新规律。

重点难点

活动重点：学习abcd的排序方式

活动难点：能用替代物排列出aabc的规律

活动准备白板课件幼儿操作材料

活动过程

一、情景导入：

小熊开了一家超市，他批发了好多好多的蔬菜水果。有一些已经摆在了货架上，还有一些还没来得及摆。

（一）出示货架1，让幼儿明白一定的规律。

1、提问：货架上有哪些水果？剩下的水果谁愿意帮小熊来摆一摆？

2、你为什么这样摆？

3、这样摆的货架整齐吗？为什么？

（二）出示货架2，让幼儿明白整齐是因为有一定的规律。

提问：1、这个货架上有哪些水果？

2、剩下的水果谁愿意帮小熊来摆一摆。

3、为什么这样摆？

4、他们整齐吗？为什么？

二、学习aabc的排序方式。

师：昨天，小熊家的超市生意特别好，很多水果都被顾客买走了。所以货架需要重新补货。

（一）出示有规律的相同种类的水果货架

引导幼儿观察货架，提问：

1、这个货架上有哪些水果？

2、顾客有没有从这个货架上买水果呢？

3、买了什么水果？你是怎么知道的？

（二）引导幼儿观察第一层：顾客有没有从第一层买水果？买了什么？你是怎么知道的？

（三）观察货架第二、三层，这一层的水果有没有人买？买了什么？为什么？

提问：1、这个货架的摆放规律和刚刚的货架一样吗？

2、那么这个货架是什么规律呢？

三、出示不同种类水果的货架，引导幼儿发现其规律。

那我们来看一看下面这个货架是不是也是这个规律呢？在发现规律之前，我们首先要将顾客买走的水果补到货架上，看看哪个聪明的小朋友可以查出来缺了那些水果。

1、出示水果货架，引导幼儿观察货架第一层。

师：小熊在货架的第一层都摆了哪些水果？顾客有没有从这一层买水果呢？买了什么水果？你是怎么知道的？

2、引导幼儿观察货架的第二层。

提问：小熊在第二层摆了哪些水果？

顾客有没有买这一层的水果？

买了什么？你是怎样发现的？

3、观察货架第三层，你觉得第三层货架的水果有没有人买？为什么？

4、你们发现了什么？这个规律和上面的水果一样吗？

小结：原来他们都是按照2个一样的和两个不一样的规律排列的。

四、用替代物替代aabc格式。

师：摆完了水果，现在我们来到了蔬菜区，小熊的要求是：必须按照刚刚摆水果的方法来摆，谁来试一试？

五、尝试创编新规律。

（一）幼儿操作，教师巡回指导，发现新的不同的规律。

师：老师在后面给你们准备了很多的图形宝宝，请你们按自己的想法给这些图形宝宝排一排规律，记住是跟我不一样的规律哦。

（二）分享：

挑出规律：例如aabb，aaac，aabcd等不同的规律进行分享。

活动延伸

还有很多有规律的东西，请你们在平常生活中去找一找

活动总结

篇11：排序大班数学教案

大班小朋友特别喜欢帮雪花片积木排队、串珠、穿项链等，结合大班科学领域的活动目标，本次活动使幼儿对有规律的排序有一个正确的认知，引导幼儿联想生活中有规律排序的事物，使幼儿感受到规律排序在生活中是无处不在的。在活动中，可提供给幼儿多种等级的材料，让幼儿进行操作，重点是鼓励幼儿开动脑筋，发现规律，大胆创造，变换不同的排序形式，体验创造的快乐。如在“给小猫铺路”这一环节中，启发幼儿用求异思维设计各种各样的小路;在“为小猫设计项链和彩环”这一环节中，引导幼儿学习按物体数量的递增或递减的规律穿项链、做彩环。通过这些分类排序活动，培养幼儿认真细心、坚持不懈的意志品质，发展幼儿的观察力、想象力及逻辑思维能力。

活动目标：

1.学习按物体数量的递增或递减等规律进行排序。

2.能大胆创新，探索按多种规律排序。

3.在排序中，体验事物重复变化的乐趣。

活动准备：

物质准备：1.雪花片每人l份，自制小猫的家每组1座。2.红、蓝彩色珠子，绳子，彩色纸条，胶水若干。3.教室中悬挂红、绿两色按递增和递减规律交替、重复做成的两条彩旗挂饰。

经验准备：观察生活中有规律的现象。

活动过程：

一、观察小猫新房子中物件的摆放，学习按物体数量的递增或递减等规律进行排序。

1.设置情境：小猫家盖了一座新房子，它准备铺一条小路，引导幼儿讨论：怎样帮助小猫铺一条漂亮的小路?如：可引导幼儿发表自已排序的多种方法，绪合教室里悬挂的彩旗，重点引导幼儿按雪花片数量递增或递减的规律，交替、重复地铺一条小路。

2.幼儿操作：用雪花片在小猫房前铺一条重复、交替、有规律的、有创意的小路。

3.幼儿互相观察，说说自己铺的小路有什么特点。

小结：这些小路铺设得非常漂亮，有的是ABBB、ABBB式，有的足ABCD、ABGD、

ABCD式，有的是AB、AABB、AAABBB式，有的是AAABRB、AABB、AB式，有的是

AB、ABB、ABBB、ABBBB式，有的是AAAAB、AAAB、AAB式……这些排列是有规律的，是重复交替的。

二、分组为小猫设计项链和彩环，能大胆创新，探索按多种规律排序。

1.第1组：穿项链。幼儿用长绳将彩珠穿成项链，比比谁穿得漂亮，引导幼儿求异想象，按交替、重复的规律来穿珠子。如：幼儿可按红珠子的数量不变，蓝珠子逐一增加这个规律穿珠子。如图：红蓝红蓝蓝红蓝蓝蓝。

2.第2组：做彩环。幼儿将彩色长条纸两头粘合成圈，按交替、重复的规律一环套一环做成彩环。教师重点鼓励幼儿变换多种方式排序，如：按黄、蓝、绿纸条间隔，红条逐一减少的规律粘彩环。如图：黄红红红红蓝红红红绿红红黄红红红红

三、展示自己的作品，在寻找作品中的规律体验事物重复变化的乐趣。幼儿相互交流自己制作彩环的创作规律，互相探索小朋友作品中的规律，

篇12：大班数学规律排序教案

1、能通过观察、推理发现物品、图形或数字的排序规律。

2、能按照已有规律继续排序。

3、激发幼儿对数学活动的兴趣，使之愿意并喜欢参加数学活动。

4、喜欢数学活动，乐意参与各种操作游戏，培养思维的逆反性。

5、让幼儿体验数学活动的乐趣。

教学重点、难点：

1、发现并按规律进行排序。

2、自己创造规律进行排序。

活动准备：

1、材料准备：动物图片若干，幼儿操作材料，各种图形卡若干。

2、经验准备：认识几种平面图形。

活动过程：

一、找一找

今天大森林里开联欢会，许多小动物都来参加，我们也去看看吧!

问题：(1)大森林里真热闹，谁来参加联欢会?

(2)它们排队有规律吗?什么规律?

二、排一排

1、有些小动物来晚了，我们来按照规律给它们排好队吧。

2、引导幼儿排列出”ABCABCABC” “AABBAABB” “AABAABAAB”“ AABCAABC”等不同模式。

三、说一说

在我们身边有哪些物品是有规律的?(桌子、椅子、衣服的花纹)

四、摆一摆

1、操作材料练习

问题：(1)你能看出来这些图形(数字)是怎样排列的吗?

(2)你来试试接着往下排吧?

(3)说说你是怎样排的?

2、我们看了许多排列图案，你能不能用手中的材料排出一些图案，然后让自己的伙伴接着往下排?

五、分享自己的创造成果和经验。

篇13：哈希插入排序

直接基数排序算法是另外一种划分-归并排序算法。直接基数排序算法使用2g个桶来划分有序队列。首先使用最高g位 (ib-1ib-2…ib-g) 关键字, 根据这g位关键字将数据放到各个桶中, 这g位关键字具有相同值的数据被放到一个桶中。同样的, 第二趟中, 每个桶中的数据根据接下来的g位 (ib- (g+1) ib- (g+2) …ib-2g) 关键字进行划分, 每个桶中的数据被分到m个新的子桶中, 后面的几趟也是这样进行。这样, 数据一直没有离开它被分配到的桶。一个显著的问题是桶 (子桶) 的数量将会迅速爆炸, 很多桶中只有很少的数据[4]。直接基数排序算法的时间复杂度是O (g (n+mg) ) 。

三路基数快速排序是另外一种基于这一原则的排序算法。同快速排序算法一样, 它将数据分为三部分:大于, 小于和等于给定值。同基数排序相似, 当前输入等于初始的字符, 移到下一位字符。[6]

这些算法都需要许多步来完成把一个大数据集分成许多小数据集的工作。那么是否可以找到一种算法, 使得这一过程可以一步完成?哈希函数可以做到这一点。

在计算机领域中, 排序和哈希是两种完全不同的概念。原因在于, 一个数据在有序表中的位置不仅仅由它的关键字的值决定, 也受这个数据集的上下文环境影响。哈希函数只考虑使用关键字的值来组织哈希表, 所以寻找一个哈希值, 使数据在有序表中位置的哈希函数是几乎不可能的。即使存在, 它也很复杂, 效率很低。然而, 我们发现哈希是一种很好的划分方法。冲突是哈希中的一种重要概念, 降低冲突是设计哈希函数所需要重点考虑的因素。但从另一方面, 两个数据的哈希值冲突, 说明这两个数据被分到一个组中, 这样划分就只需要一步来完成。

在本文中, 我们将给出一种新的排序算法, 它使用哈希的方式, 将大数据集分为许多小数据集。使用插入排序对每个小数据集进行排序。在第1节中给出一些作为该算法基础的定义, 在第2节中给出算法描述, 在第3节中给出算法的性能分析, 在第4节中给出针对冗余编码的关键字的改进。

1 定义

定义1 (完美哈希函数) :一个哈希函数是完美哈希函数, 当且仅当这个哈希函数能够给每一个数据一个唯一的哈希值。[1]

定义2 (超级哈希函数) :一个哈希函数是一个超级哈希函数, 当且仅当它的结果是一个全序关系, 并且是一个完美哈希函数。[1]

William F.Gilreath提出文献[1]一种超级哈希函数, 但这类哈希函数比较复杂, 而且不容易找到。这是由于数据在有序线性表中的位置不仅仅由它的关键字的值决定, 还取决于其他数据的关键字的值, 即它所处的上下文环境。但这里可以找到一种弱化要求的哈希函数, 这就是下面定义的划分哈希函数。

定义3 (划分哈希函数)

划分哈希函数的结果是一个偏序关系, 即, 将具有相同哈希值的数据视为一个集合, 那么一个集合中的数据将都大于或者等于 (小于或者等于) 另一个集合中的数据。

最简单的划分哈希函数就是使用前k位关键字的值作为哈希值, 将所有数据分到2k个子线性表中。进行这次划分操作只需要对每个数据进行一次操作, 这大大优于快速排序算法。

2 数据结构和算法

下面考虑哈希插入排序算法, 首先考虑非冗余关键字。该算法首先是使用使划分哈希函数将整个线性表分为许多小的线性表。这里我们采用最简单的划分哈希函数, 即使用关键字的前k位的值作为哈希值, 将数据分到2k个子线性表中。这些子线性表的顺序由划分哈希函数确定。即, 子线性表A在子线性表B之前, 当且仅当子线性表A中的所有数据的关键字的值都大于子线性表B中所有数据的关键字的值。在将一个数据放到一个子线性表中时, 按照插入排序的插入操作的方式进行。由于同一个字线性表中所有数据的开头k个字符的值都相同, 所以当一个数据的关键字长度小于或者等于k时, 直接将其放在队列的开头。最后根据这些子线性表的顺序将它们连成有序的线性表。

顺序存储结构不适合哈希插入排序。因为将数据分到许多子线性表中, 并最终合并成一个有序线性表, 这一过程中有大量移动操作, 所以链式结构更适合实现哈希插入排序。

下面是哈希插入排序的过程:

1) 设A是要被排序的线性表。

2) 构建一个线性表的数组Φ, 他的大小L (L=2k) , k是哈希函数使用的关键字位数。

3) 计算每个数据的关键字的哈希值。根据哈希值, 将每个数据使用插入排序的插入方式插入数组Φ中对应的线性表。如果这个数据的关键字的长度小于或者等于k, 那么直接放到对应线性表的开头。

4) 按照数组Φ中的线性表的顺序, 将数组Φ中的线性表合并成为有序线性表。

下面我们证明哈希插入排序算法的正确性。任取两个数据:数据A和数据B。如果它们有相同的哈希值, 将被放到在同一个线性表中, 因为在将一个数据放到一个线性表中时, 按照插入排序的方式执行了插入操作, 所以他们之间必然是有序的。如果它们的哈希值不同, 那么它们将被放到不同的线性表中, 由于线性表之间是有序的, 所以这两个数据之间也是有序的。所以这个算法运行结束后, 整个线性表将是有序的。

3 性能分析

现在分析哈希插入排序的效率。同时需要最合适和k值, 使得排序的时间最短。从算法描述可以看出, 哈希插入排序算法所花费的时间包括三部分:哈希函数计算时间, 插入子线性表的时间和连接子线性表的时间。哈希计算对于每个数据而言, 都进行一次操作。然后将这个数据按照插入排序的方式, 执行插入操作。一般情况下, 每个子线性表的长度遵守二项式分布, 。其中n是数据的数量, L是子线性表的数量。对于每个子线性表, 比较操作的数量是, 其中t是这个子线性表的长度。所以所有插入操作所执行的比较操作的数量之和为。这里用S表示。下面是当数据量 (n) 为10000, 1000000和100000000时的比较操作的数量图。图中横坐标L为子线性表的数量, 纵坐标为比较次数。

下面我们需要一个合适的L值, 来平衡内存和时间的要求。我们发现, L=n, 即2k=n时, 进行插入操作所需要的总的比较次数是。这是一个可以接受的值。选择一个L, 使得dN/dL=-1时, 这个L是一个更好的结果。经过计算, 这个L大概是0.7n。所需要的移动操作和比较操作的数据基本相等。所以我没可以选择k=log2n或者k=log20.7n。

将子线性表连接在一起的时间是固定的, 为2k次移动操作。当k=log2n时, 需要n次移动操作、所以对于哈希插入排序, 取k=log2n时, 共需要次比较操作 (包括计算哈希值) , 次移动操作。这是一个线性时间。

4 冗余编码关键字的扩展

我们在前面考虑的都是非冗余码。然而很多关键字采用的是冗余编码, 如字符串关键字。需要对定义的划分哈希函数进行修改。下面是一种针对冗余编码的划分哈希函数。

我们假设关键字是一串取自字符表α的符号串。符号表α中有k种不同符号。每个符号有相同的划分能力。每个符号有m位编码。这样我们就需要使用「logk1骎×m位关键字将数据分到k「logk1骎个小数据集中。l是我们需要的小数据集的数量。每m位关键字可以把数据分到k个不同的小数据集中。可以使用映射方式来完成这一划分函数。

5 结束语

对于大数据集, 哈希插入排序是一种很好的排序方法, 特别是数据的关键字长度较大时。它只需要线性时间来完成排序。对于划分-归并排序而言, 哈希插入排序只需要一步来完成划分过程。其他这类排序往往需要对一个数据进行多次操作来完成划分步骤, 如基数排序, 快速排序和归并排序。

哈希插入排序依然有一些问题。特别是我们假设字母表中的每个符号都有相同的划分能力。但这种假设在有些情况下不成立。如英文字母, 不同字母出现的频率会有不同, 划分能力就不相同。字母的出现频率越高, 划分能力越差。在今后的研究中将在这方面寻找改进方式。

摘要：排序是软件领域的基本问题, 常用排序算法中, 快速排序算法最快, 时间复杂度为O (n*lnn) 。基数排序算法的时间复杂度可以达到O (g (n+mg) ) 。并且只适合于像整数、字符串这类有明显结构特征的数据。我们在本文中提出一种新型的排序算法——哈希插入排序。它将哈希算法用于排序中。通过概率统计分析, 证明它的时间复杂度为O (3 ( (3/2) n) , 大大优于基数排序。

关键词：排序,哈希,字符串数据结构,文本数据库

参考文献

[1]William F.Gilreath.Hash sort:A linear time complexity multiple-dimensional sort algorithm[J].Proceedings of First Southern Sympo-sium on Computing, 2004.

[2]Steffen HEIN, Justin ZOBEL, Hugh E.WILLIAMS.Burst Tries:A Fast, Effcient Data Structure for String Keys[J].ACM Transactionson Information Systems, 2002, 20 (2) :92-223.

[3]Ranjan SINHA, Justin ZOBELl.Efficient Trie-based Sorting of large set of String[J].Australian Computer Society, Inc, 2003.

[4]Shin-Jae LEE, Minsoo Jeon, Andrew SOHN, and Dongseung KIM[C].Partitioned Parallel Radix Sort, ISHPC.2000, LNCS 1940:160-171.

[5]BENTLEY J, SEDGEWICK R.Fast algorithms for sorting and searching strings, In Proc.Annual ACM-SIAM Symp[C].on Discrete Al-gorithms.New Orleans, Louisiana, 1997:360-369.

篇14：练就排序的慧眼

【关键词】做题规律 中心句 关联词 逻辑顺序

语言排序题是高考命题中的老面孔，全国18套高考试卷中往往有8套左右有此题型，2010年全国卷更是无论一套、二套或课改卷，每套试卷都有它的踪迹，2011年情形相类似。排序题应该引起我们的高度重视。它属于語言应用类题型，主要考查学生对特定语境中句子衔接的能力及逻辑思维能力，对考生的综合能力要求较高。

笔者曾就此类题的做题感受在较优秀的学生（重点中学的实验班学生）中做过调查，50%的学生认为这种题各类高考资料介绍的方法也较为繁琐难记，具体做时感觉防不胜防，较难应对；另有近20%的学生认为这样怎么想都有道理，最后瞎蒙了事。其实我们不妨从例题入手，归纳出几种最简单易记的规律。

请看下例：

1.把下列句子组合成语意连贯的一段话。

①在南坡，带状分布的原始云杉林海连绵不断，棵棵巨杉像一把把利剑，直插云天。②在北坡五花甸草原上，你可以看见新疆细毛羊群和奔驰的伊犁马群。③在遮天蔽日的杉林下，马鹿、狍鹿、棕熊、雪豹等野生动物出没其间。④吃完早饭后，继续南下，就进入喀什河和巩乃斯河的草原带和森林带。⑤各种森林鸟类，鸣声不断。

【解题思路】

这段话中④句中“就进入……的草原带和森林带”是本段具有总述性的句子，所以②句应排在前一层次，①③⑤句应排在后一层次。至于①③⑤句的内部排序，①句中“在南坡”与②句中“在北坡”相照应，自然应排在前；第③句中“在遮天蔽日的杉林下”，既“勾前”——紧扣①句中的“原始云杉林海”、“棵棵巨杉”，又“连后”——引用下文“野生动物”和“森林鸟类”在其间的活动，所以应排在中，剩下的⑤句应排在后。综观上述分析，几个句子排列的先后顺序应为④②①③⑤。

（一）规律的简要总结：找出中心句，确定首或尾。再简洁些可表述为：中心句，定首尾。先找中心句，在很多例题中都能看到，学生也易理解，故只举一例进行说明

再看下例：

2.依次填入下面一段文字横线处的语句的序号使之衔接最恰当：

在21世纪的今天，正确对待任何大自然的关系比以往任何时候都重要。____，____，____，____；____，结果也受到了大自然的报复。

①有的国家希望做到“天人合一”

②人类衣食住行所需的一切资料都取自大自然

③有的国家对待大自然的基本态度是“征服自然”

④然而，大自然的容忍是有限度的，它是会报复的

⑤他们把大自然看做伙伴，可惜他们的行动没能跟上

⑥从表面看，大自然真的被他们征服了

解析：本题中注意④中的“然而”表转折，③⑥和①⑤应该形成转折意，⑥在③后，⑤紧跟①，依据后文的“也”表明①⑤应该在④的后面，③⑥在④之前，②最适宜谓语句首，故选②③⑥④①⑤。

（二）规律的简要总结：代词连词是指引，上钩下连紧相随。也可以再表述为：代词连词定上下。在这里，要学会找各句中的起钩连作用的关键词。找代词连词对许多学生来说并不困难，故也只举一例进行说明

最后再看两例：

3.把下列句子组成前后衔接、意思完整的一段话。（只写句子的序号）

①出现在我们面前的是一座美丽的小城。

②城中有一条小河流过，河水清澈见底。

③到了札兰屯，原始森林的气氛就消失了。

④白砖绿瓦的屋舍悠然地到映在水中。

⑤走出小城，郊外风景幽美，绿色的丘陵上长满了柞树。

⑥丛生的柳树散布在山丘脚下。

【解题思路】

本题属描写语段，要看句子之间的关系，以及词语之间的呼应。②④写小城“中”，⑤⑥写小城“外”；③句中有“消失”，①句中有“出现”，内容关联，相互照应。②句和①句相连，④句呼应②句，⑤句从城“中”走向城“外”，连着④句。故答案为③①②④⑤⑥。

4.依次填入下面一段文字横线处的语句的序号使之衔接最恰当：

玉树藏族自治州____， ___，____，

____，____，____，玉树既是“三江源头”，也是“藏獒之乡”和“虫草之乡”。

①东南与四川省甘孜藏族自治州毗连

②是长江落差最大的标志点

③与海西蒙古族藏族自治州、果洛藏族自治州等地相通

④平均海拔4000米以上，最高点6621米

⑤位于青藏高原腹地，青海省南部

⑥气候高寒

解题思路：做此题可先分组，把相同内容的句子分为一组，然后再确定语序。①③⑤都是说玉树的位置，可为一组；④②都是说高度，可为一组。⑥是说气候。然后确定整体语序，“位置—海拔—气候”是合乎叙述事理的，最后确定内部语序，⑤主说玉树的位置，③①是对⑤的补充，故⑤应是首句。答案为⑤③①④②⑥。

（三）规律的简要归纳：时空逻辑帮大忙，群内顺序自然成。或再简缩为：看逻辑定层次

这是三条最常用的规律，简单易记。其中第三条的“逻辑”的概念要让学生理解清楚，对常见的逻辑顺序也应该有一个大致的把握，应对这类题就不至于烦恼重重了。