排序算法教学反思

排序算法教学反思（精选11篇）

排序算法教学反思 篇1

《选择排序》教学心得

教学内容：

选择排序的算法思想 选择排序的实现过程 选择排序的编码实现

总结和思考：大数据背景下的排序

排序(Sort)是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。排序方法分为两大类：一类是内排序：冒泡排序、选择排序、插入排序、希尔排序、交换排序、快速排序等；另一类是外排序。

从教学理念上看，本节课利用维果斯基的“最近发展区理论”，把学生的现有水平和兴趣点，结合教学的目标，形成最近发展区。教学着眼于学生的最近发展区，提供带有难度的内容，调动学生的积极性，发挥其潜能，超越其最近发展区而达到下一发展阶段的水平，然后在此基础上进行下一个发展区的发展。

从教学方法来看，主要使用案例分析法、讲授法等，从分析当前流行的冒泡排序算法的案例开始，由浅入深的介绍选择排序的基本概念,算法思想以及编码过程。

从教学过程来看，首先从回顾冒泡排序的内容导入，在改进冒泡排序的过程中，提出选择排序的概念和思想。用直观的动画方式展现选择排序思想和过程，总结分析出关键代码，引导学生写出完整代码，最后分析选择排序的关键点，并提出思考，大数据背景下的排序改进方法。

在整个过程中一直都力求让学生在已知的知识结构中推导、归纳出需要掌握的知识点。但是上完课程后感觉案例还不够多，相对于非计算机的学生来说，算法的分析比编码的过程更加重要。所以学生感到有些难，本来已经调动起来的积极性没能保持到整节课。非计算机专业的学生思考计算机问题深度不够，在以后的备课中要更多的挖掘教学案例的广度和深度，给他们更多的思维训练。

排序算法教学反思 篇2

一、排序算法

常用的排序算法有四种, 分别是顺序比较法、冒泡法、插入法及选择法, 它们各有各的特点, 如果没有特别说明, 用顺序比较法较为简单。

二、排序算法的应用

学习程序如果仅仅是局限于排序就没有了意义, 因此常常会涉及有难度和深度的问题。下面笔者通过对两道考题帮助我们加深对排序的了解。

1.有20个在10—99 (含10和99) 之间互不相同的整数11, 21, 22, 32, 23, 43, 34, 44, 56, 65, 77, 57, 82, 27, 95, 48, 68, 64, 90, 81, 按个位数作升序排序, 个位数相同时再按十位数作降序排列, 将排序结果输出。

分析:程序应由下面几个部分组成:定义变量和数组, 数组元素的赋值, 数组元素的处理——排序, 数组元素的输出。在排序程序段, 应将数组元素分解为个位数及十位数, 这是本题重要算法之一。

程序清单

2.下列程序列用数据96, 123, 78, 14, 37实现对M×N矩阵a的赋值, 要求将给定的数据依次赋给数组b, 然后用冒泡法按列自上而下进行升序排列。

分析:程序中b数组的赋值和排序是关键, 但问题是如何利用a数组中的数据给b赋值, 当a数组中的值使用完毕, 再从a数组中的第一个数开始赋值, 利用计数器来判断a数组中元素的个数。因为是二维数组, 所以要用到三重循环为数据排序。

中班数学《按规律排序》教学反思 篇3

中班数学《按规律排序》教学反思篇1

今天我上了《按规律排序》一课我先讲了一个故事激趣导入，说小松鼠在森林里采了一些美丽的红豆子，绿豆子串成了一串美丽的项链，请小朋友找一找藏在项链里的美丽的秘密：一颗红一颗绿，一颗红一颗绿。然后再出示一串项链一颗红两颗绿，一颗红两颗绿。和小朋友一起找其中的规律。然后再请小朋友们用雪花片来按规律排序，自己设计一些规律来排序。然后指导幼儿完成书上的.作业。

课堂上气氛活跃，幼儿兴趣很高。特别是前面说的时候，他们好像都懂了。但让他们自己操作的时候，遇到了难题，有几个幼儿串着串着就多一个或者少一个，我又让他们细心地检查，最后发现问题，再改正过来。

还有一个孩子很会说，但动手时才发现他根本没有懂到，不能完成。我就个别指导他，又让他说，又让他观察别人的作品，我费了好大的劲，可收效甚微。最后，我亲自动手和他一起摆了三遍，第四遍让他自己摆他才摆对了。后来举一反三，触类旁通，后来说了几个规律都没有难倒他，他都摆对了。我体会到在教学过程中，让孩子动手真的非常重要。只有孩子亲手做了，他才能真正领会其中的意思和规律，光凭嘴说，说的再费劲，还不如示范作一遍。这是在我今后的教学中应该特别注意的经验。

中班数学《按规律排序》教学反思篇2

到了中班孩子在操作摆弄物品时，已逐渐认识了一些事物的属性，如：大小、长短、颜色等，能了解不同物体的属性、发现其明显的差异性，也能感受到有关规律的经验。排序指的是将两个以上物体，按某种特征上的差异或一定的规律排列。它是一种连续的比较，建立在对两个物体比较的基础上。通过排序可以促进幼儿分析、比较能力的发展。本次活动以游戏的形式，通过创设情景、教学用具、操作材料的多方位对话，引导幼儿学习、观察、比较，使其体验更深入、规范、条理化，让幼儿进一步感受数学的规律美。

活动开始，我就用情景导入，小红帽去外婆家送点心！”，在背景图中让幼儿发现有序的排列，吸引了幼儿的注意力。他们很快发现去外婆家的路上灯笼是用红黄红黄来排列的，树是大小大小来排列的，接下来的环节是小红帽要在森林中采花，这个环节是让幼儿仔细观察并积极参与，将排序活动融合在幼儿玩之中。营造一种轻松愉快的气氛。这个环节孩子们的情绪一下子调动起来了，都能积极融入其中。从简单的ABAB排序到AABB，然孩子在玩中探索不同的排列方法，然后小红帽要要穿过树林要按路线走要不然会碰到大灰狼，让排序有难度了，一部分幼儿能简单的排列，但是也有一部分的孩子不理解，这时我考虑的不够周到，没有让孩子掌握排列这种多角色的方法，而是在尝试自己的探索，这样就阻碍了孩子的思维。

第三个环节是让幼儿操作，小红帽自己设计礼物给外婆。这里我让幼儿自主选择材料，根据自己的能力选择两种或者三种物体有序的排列。在交代要求时我强调了不能用一种颜色，可以用两种或三种颜色来制作。

从活动情况来看，幼儿完成的还是比较好，很多幼儿能按规律排序，但是对于自己设计还是有一定苦难，特别是画图形时候，画的都不标准，通过这次活动使我更加明白了科学活动中的很多细节问题值得注重。

【中班数学《按规律排序》教学反思】相关文章：

1.中班数学《按规律排序》教学反思范文

2.《按简单规律排序》的教案

3.按规律排序得教案

4.中班数学下册按规律排序教案

5.数学教学计划按规律排序

6.中班数学《学习排序》的教学反思

7.公开课按规律排序教案

排序算法教学反思 篇4

活动目标：

1、通过观察比较区别图案的大、中、小。

2、尝试将物体按一定的规律排序，初步体验按规律排序的美感。

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

4、有兴趣参加数学活动。

5、体验数学集体游戏的快乐。

活动准备：知识准备

教具准备：范作动物新衣样板

学具准备：小羊、小猪、小狗的操作板、大中小图案的纸若干

活动过程：

一、出示小动物操作板，引出活动。

1、今天森林里要开舞会，很多小动物们都要去参加。

2、小羊、小猪、小狗都在发愁？为什么呀？它们有没有漂亮的花衣服？

二、引导幼儿相互讨论，利用桌上的材料来帮小动物按排序规律来设计新衣服。

1、我们小朋友愿不愿意来帮助他们呀？

2、桌上的小碗里有很多漂亮的图案，它们有什么不同？（大、小不同）

3、我们案例尝试一下这个小朋友的方法来给小动物设计的漂亮衣服。按大、中、小的规律来排序。

4、哪么啊有其他的方法来为小动物设计新衣？尝试用小、中、大的规律来给小动物设计新衣。

三、幼儿尝试按照大、中、小或小、中、大的规律来给小动物设计新衣。

1、小朋友的桌上还有许多的小动物在等着大家帮他们设计漂亮的新衣。

2、大家可以尝试用大、中、小的图案来为它们设计，也可用小、中、大的规律来设计。

3、大家一起开动脑筋，为小动物们设计出漂亮的新衣来哦！

四、幼儿相互介绍、展示自己做的新衣。

1、请幼儿来介绍一下，你是按照什么样的规律来为小动物设计新衣的。

2、小动物今天真开心，它们要谢谢大家，设计了这么漂亮的花衣服！他们穿了新衣服去参加舞会喽！

教学反思：

整个活动以孩子们的操作为主，让每个孩子都有自己动手操作的机会，活动过程首先让幼儿找到小动物的排队规律，然后让孩子排一排，说一说身边什么是有规律的，最后让孩子们摆一摆，让孩子们在展示的基础上，老师加以总结。活动的目的基本达到，大部分孩子都能掌握按规律排序。活动的过程能兼顾全体幼儿的需要，注意幼儿的个体差异，让每个幼儿都有成功和进步的体验。我认为本节课的亮点是“摆一摆”，在此环节幼儿可以自己动手把想的规律摆出来，体现了手脑互动，然后说出自己是按照什么规律摆的，在说时注意要说完整话，用“我是按照……规律排序的”句式完成。最后请小伙伴接着自己的作品往下排，小朋友来做小老师检查是否正确。我认为本节课的不足是缺少小组活动，下次设计时加小组活动，让小朋友们有竞争意识，合作意识。

排序算法教学反思 篇5

一、说教材

设计意图：

排序，在我们的生活中到处充满了排序：服装花纹上的排序、皮包上图案的排序、饰品排列上的排序、环境装饰上的排序、物品包装上的排序、公园中花草种植的排序……这些有规律的排序带给我们生活中的美。孩子们在生活中有意或无意识地会发现生活中存在一些排序的现象。如：吃饭的碗和盘子周边的漂亮的花边;裙子袖口和裙边的花边;卫生间瓷砖排列的图案……而我们教师正是孩子发现、运用和创造这种有规律的美的引导者。

幼儿学习排序可以为幼儿建立初浅的数学概念做好准备。幼儿学习排序，可以按物体量的差异排序，也可以按物体的某一特征或者规律排列顺序。大班幼儿已经积累和建立了有关物体在颜色、形体和数量等特征差异排序的数学经验，可以更进一步地学习按照物体量的差异和数量的不同进行10以内正逆排序，初步体验序列之间的传递性、双重性和可逆性的关系。新《纲要》提出“在幼儿的生活中进行数学的学习”，让幼儿在生活中学数学、玩数学、用数学，教师引导幼儿在游戏和玩乐中初步接受和学习有规律的排序，并鼓励幼儿将之应用于生活。

根据大班幼儿的年龄特点和学习能力，并结合《纲要》精神，我为幼儿选择的教学活动为“按物体的特定规律排序”，并设定在大班第二学期进行。

二、说活动目标

(1)鼓励幼儿在动手操作的活动中，比较发现物体排列的传递性、可逆性，并进行大胆自主的排序活动。

(2)增强幼儿对排序操作活动的兴趣，逐步发展幼儿的思维、观察、比较和初步的判断推理能力。

分析：目标(1)为认知目标，重在鼓励幼儿在动手操作的活动中，比较，发现物体排列的传递性、可逆性，并进行大胆自主的排序活动。其中发现和学习物体递增递减的排序规律是本次活动的新知识点，也是难点部分。

目标(2)是能力和情感目标，重在激发幼儿对排序活动的兴趣，掌握排序操作的方法，发展幼儿的排序能力。

三、说重难点

重点：鼓励幼儿在动手操作的活动中，比较发现物体排列的传递性、可逆性，并进行大胆自主的排序活动。

难点：引导幼儿发现递增递减的排序规律，并学习排序。

为了解决重难点，我以布置新家为切入点，准备了各种形象、有趣的教具。通过各种形象有趣的排序活动的操作，让幼儿学习排序并激发幼儿对排序活动的兴趣。大班的幼儿喜欢一些具有挑战性的操作，在活动中借助一些启发性的、具有探索性的问题，让幼儿自主探索排序的方法，从中找到排序的规律。

四、说活动准备

1、知识经验准备：已经有按照物体某一特征规律进行排序的经验：如按照物体的颜色规律的排序、长短规律、宽窄规律、高矮规律的排序等等。

2、物质准备：新家蓝图，幼儿分组操作材料：铺地砖(蓝白泡沫毯)、串彩链(长短宽窄颜色不同的长条手工纸)、围围墙(四种颜色的炮弹玩具)、种树(高矮品种不同的树)递增递减排序示范卡片三张、雪花片、黑白序列的排序图样、黑白方块若干。

五、说活动过程

1、第一环节：教师出示新家的蓝图，提出今天活动的要求。直接引出主题，激发幼儿学习的兴趣。

2、第二环节：教师介绍装修的材料，提出装修的要求。幼儿自主探索物体简单的排序规律，进行分组操作。

⑴铺地砖：按照蓝白颜色变化规律排序。

⑵围围墙：按照炮弹颜色及节数规律排序。

⑶做彩链：根据纸条长短、宽窄、颜色的不同有规律串彩链。

⑷种树：按照树的形状、高矮不同规律排序。

在这一个环节中，可以让幼儿灵活地运用所学知识来解决问题，幼儿可以根据自己的实际情况来选择不同活动材料进行操作，这也便于教师的分层指导及因材施教。;.教.案来自:快思老.师教.案网;在幼儿的自主操作、同伴间的探索交流和师生的共同小结的活动中，重点目标的第一层次得以解决。

3、第三环节：教师出示三张递增、递减规律排序的卡片，(卡片1：蝴蝶不变，小花逐一增多;卡片2：蝴蝶不变，小花逐一减少;卡片3：蝴蝶逐一减少，小花逐一增多)。幼儿通过观察、比较，发现图形递增、递减排序的规律。然后幼儿用不同色彩的雪花片，学习按物体数量的递增和递减的规律排序。在这一个环节中，通过观察、比较、发现、操作等方法解决了重难点目标，这训练了幼儿进行初步判断和推理的能力。

4、第四环节：欣赏黑白序列，教师出示黑白序列，让幼儿观察寻找序列中黑白两色是以几个为一组进行排列，知道黑白两色也可组成许许多多有趣的序列。鼓励幼儿设计运用已有的排序知识设计一条“黑白配”小毛巾。幼儿介绍自己设计的“黑白配”小毛巾，说明排序规律。这一环节通过欣赏、观察分析、和设计表述等方法，使活动的重难点目标得以突破提升。

5、活动延伸：观察家里、大自然中具有规律的排序现象，让幼儿互相交流。让幼儿带着问题观察生活，将所学到的数学知识渗透到生活情景之中并进行再运用，有利于培养幼儿对数学活动的兴趣，促进其创造能力的发展。

六、说教法学法

大班幼儿具有一定的动手操作能力，新旧知识迁移的能力，这些能力为本节

课的学习做好了充分准备。遵循新课程所倡导的基本理念，本节课采用了如下教法和学法：

1、情景引入法：

课堂上通过生动的谈话、演小品等情境，使幼儿提高学习兴趣，产生探索新知的欲望。

2、观察法：

活动中通过安排幼儿观察两种范例图，引导幼儿发现两种简单的排序规律，建构知识系统。

3、自主探索法：

幼儿在认识的基础上，通过提供学习材料，让幼儿进行动手操作，体验和探究按颜色、形状等规律特征进行排序的士制作过程。

说反思

首先，教师为幼儿提供了他们在生活中熟悉的情境。在教学中，教师以布置新家引题，让孩子作为幼儿园的小主人布置新家，因为孩子都有参与装修自己的家的经验，所以孩子的兴趣很快被激发。罗杰斯认为：越是儿童不熟悉、不需要的内容，儿童学习的依赖性、被动性就会越大，只有当儿童觉察到学习内容与他自己有关时，才会全身心投入，意义学习才会发生，才会产生自觉主动的学习行为。

其次，教师注重在引发幼儿已有经验的基础上深入学习新的知识点。在活动中，幼儿的第一次操作，就是引发幼儿的已有经验，幼儿按照颜色、数量、长短、宽窄、高矮等特征进行排序，幼儿在巩固旧知识的基础上更加容易接受新知识。

再次，教师在教学中注重幼儿寻找操作材料的过程，并视之是数学思维的过程。让幼儿在排序操作中，从众多复杂多样的材料中筛选出可供排序的材料，正是体现了数学知识自身的严密性和关系变化的复杂性，并培养了幼儿思维的准确性与变通性。

最后，创设开展多种排序活动，帮助幼儿多角度理解排序活动。在教学活动中，教师综合了颜色规律的排序、长短规律、宽窄规律、高矮规律、数量的递增递减规律的排序，帮助幼儿从多角度建立排序的概念，起到举一反三的教学作用。

数组排序算法浅析 篇6

顺序排序的主要思想是每一轮比较结束后都可以确定某一元素;在一轮的比较过程中, 将要确定的位置上的元素与其后所有的元素进行比较;对于一个长为N的数组, 需进行N-1轮比较。其第一轮的比较过程如下:

该轮中, a[0]与a[1]~a[n-1]的所有元素进行比较, 比较过程中, 如果发现哪个元素比a[0]小, 则与a[0]进行交换。一轮比较之后, 确定a[0]为数组中最小的元素。相同方法, 依次确定a[1]、a[2]、a[3]…a[n-2]。

由上表, 可以写出其实现代码

可以发现当数组原有的顺序是降序, 要实现其升序排序时, 每一轮中的交换的次数将会非常多, 严重影响排序效率。所以对该方法进行改进:先找出数组中最小值, 再与相应位置上的元素进行交换, 这就是选择排序。

选择排序的主要思想是每次从待排序的数据元素中选出最小的一个元素, 放在待排序数列的起始位置, 直到全部待排序列的数据元素全部排列完毕。

第一轮的比较过程如下:

选择排序的实现代码

选择排序相较于顺序排序有更高的执行效率, 而且思想同样利于理解。

冒泡排序的主要思想是“相邻元素”之间的比较, 如果前面的元素大于后面元素就把他们互换。一轮比较之后可以确定最后一个元素为最大, 第二轮比较之后可以确定最后一个元素为第二大的元素……依次类推, 第N-1轮比较, 可以确定倒数第二个元素, 这个时候数组的排序完成。冒泡排序的过程如下:

冒泡排序的实现代码

顺序排序算法, 思想简单易于理解且适于任何的数组, 无论什么情况下都可以使用;但是顺序排序效率较低, 可以采用选择排序法进行改进;即使如此选择排序的效率依然受到比较次数的影响, 所以对于比较元素比较少的数组, 可以采用冒泡排序法。

如果数组中99%的数值已经排序好, 即只有很少的元素需要进行排序, 可以选择冒泡排序法;如果你所要排序的数据数目相对较少并满足100个以下, 你就可以采用选择排序法;如果上述几种情况都不满足, 那么就选普遍适用的排序算法即顺序排序法即可。

以上所述只是三种常见排序, 在众多的排序算法中各有优缺点, 每一种算法只有在某一种情况下才表现的最好, 我们应当合理的根据实际情况选择算法。

参考文献

[1]张巍.基于Page Rank算法的搜索引擎优化策略研究[D].四川大学, 2005.

[2]郭敏杰.基于云计算的海量网络流量数据分析处理及关键算法研究[D].北京邮电大学, 2014.

排序算法教学反思 篇7

设计背景

幼儿对于一些事物，不懂得是有规律的。特设此课，使幼儿进一步了解事物的规律。

活动目标

1、引导幼儿学会按物品的颜色，大小，形状等特点进行有规律的排序。

2、培养幼儿的观察力、判断力及动手操作能力。

3、培养幼儿比较和判断的能力。

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

5、体验数学集体游戏的快乐。

重点难点

学会观察生活中有规律的事物。

活动准备

教学图，不同形状，颜色的卡片若干。

活动过程

一、导入：

请幼儿观察一幅图片，并说一说大家都发现了什么有趣的地方。(塔、树、花朵)，总结规律。

二、内容呈现：

教师分组排列卡片，请幼儿观察本组卡片的规律，并上前面来把剩下的卡片排列完。(大小、形状、颜色、种类)。

三、巩固游戏：

1.给幼儿每人准备一组卡片或玩具，鼓励幼儿自己进行排序。

2.互动：分组请幼儿做游戏，按照老师所画的规律排列。(站蹲、举放、男女。)

结束：

1.请小朋友认真看一看在我们周围还有那些东西也是有规律的、排序的。

2.请幼儿在成排(2男2女)的顺序离开活动场地。

教学反思

本节活动课较为成功，幼儿动手及互动的环节比较多。带动了幼儿的积极性，也活跃了课堂气氛。在活动结束进行自身排序时，幼儿有些不懂自己该站在怎样的位置。

排序算法教学反思 篇8

索引0123456

数值1532899121736，

①取出0位的15作为基准值，然后倒序从后往前找小于15的，将12赋值给0位;

②从前往后找大于15的将32放置到位置4;

③位置1空出来，然后继续倒序找小于15的，正序找大于15的，最后索引到大3的时候重复以上过程。

冒泡排序

冒泡基本上没有什么好说的，直接看代码吧，新建了Sort类处理排序:

//

//Sort.h

//Algorithm

//www.cnblogs.com/xiaofeixiang

//Created by keso on 15/3/15.

//Copyright (c) 2015年 keso. All rights reserved.

//

#import

@interface Sort : NSObject

@property (nonatomic,strong)NSMutableArray *dataSource;

-(void)bubbleSort:(NSMutableArray*)dataSource;

-(void)quickSort:(NSInteger)start endIndex:(NSInteger)end;

@end

Sort.m中的bubbleSort实现:

//冒泡排序

-(void)bubbleSort:(NSMutableArray*)dataSource{

NSUInteger count=[dataSource count];

for(int i=0;i

for (int j=0; j

if ([dataSource[j] intValue]>[dataSource[j+1] intValue]) {

NSString*temp=dataSource[j];

dataSource[j]=dataSource[j+1];

dataSource[j+1]=temp;

}

}

}

for (NSInteger i=0; i<[dataSource count]; i++) {

NSLog(@”排序--%@“,dataSource[i]);

}

}

冒泡排序比较稳定，但是每次只是移动两个数字比较慢，如果是正序的话时间复杂度是O(n)，如果是逆序的需要弄成正序的，那么事件复杂度O(n*n)，会经过n(n-1)/2次比较，平均事件复杂度O(n*n);

快速排序

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)，

基本思路如下:

1.先从数组中取出一个数作为基准数值，也可以理解为中间变量。

2.分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3.再对左右区间重复第二步，直到各区间只有一个数。

快速排序由于排序效率在同为O(n*logn)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用，也算是出门居家必备的算法了，理解比较好理解，具体的实现能写出来基本上算是理解的，至于更深的就要看工作中实际的操作过程啦。

Sort.h中定义了一个QuickSort方法，还有一个NSMutabArray是为了保存最后的结果的,具体实现:

//快速排序

-(void)quickSort:(NSInteger)start endIndex:(NSInteger)end{

if (start

NSInteger standardValue=[_dataSource[start] intValue];

NSInteger left=start,right=end;

while (start

//从后往前找，如果后面的数值大于基准值，递减

while (startstandardValue) {

end--;

}

//小于基准值的时候，给数组中索引为start赋值

if (start

_dataSource[start]=_dataSource[end];

start=start+1;

}

//从前往后找，如果数值小于基准值，递增

while (start

start++;

}

//大于基准值，给数组中索引为end的数据赋值

if (start

_dataSource[end]=_dataSource[start];

end=end-1;

}

}

//退出的时候值start和end相等

_dataSource[start]=[NSString stringWithFormat:@”%ld“,(long)standardValue];

[self quickSort:left endIndex:end-1];//处理左边

[self quickSort:end+1 endIndex:right];//处理右边

}

}

主函数中的调用如下:

NSMutableArray *data=[[NSMutableArray alloc] initWithObjects:@”10“,@”88“,@”97“,@”33“,@”8“,@”73“,@”18“, nil];

[sort bubbleSort:data];

sort.dataSource=data;

[sort quickSort:0 endIndex:[data count]-1];

for (int i=0; i<[data count]; i++) {

NSLog(@”排序:%@",data[i]);

}

return 0;

改进的双向选择排序算法 篇9

为了采用查找效率较高的查找法, 通常希望待处理的数据按关键字大小有序排列, 因而排序是计算机程序设计中的一种基本操作[1]。

本文在介绍简单选择排序算法的基础上, 提出两种双向选择的算法设计方案, 并给出算法的C语言描述。部分参考文献中也有类似的关于该算法设计思路的描述, 但其算法实现中均存在不同程度的疏漏。本文详细分析了双向选择排序算法两种设计方案的具体步骤, 纠正了部分参考文献中存在的问题, 并通过对前后三种算法进行时间复杂度和空间复杂度的对比分析, 总结出双向选择排序算法的两种设计方案的优劣, 从而为简单选择排序算法的优化提供了一定的理论依据。

1 简单选择排序算法

待排序的记录序列所采用的排序方法可根据存储方式不同分为向量排序、 (链) 表排序和地址排序三种[2], 本文采用第一种方式, 即待排序的一组记录存放在地址连续的一组存储单元中。待排记录类型可用C语言定义如下:

以下均假定要求将各记录关键字按非递减有序进行排序。

1.1 算法设计思想

简单选择排序算法的基本设计思想是:第一趟排序从所有待排序记录的关键字中选择一个最小值, 同表头记录进行交换;第二趟排序从除去第一个的其余记录关键字中选择一个最小值, 同第二个记录进行交换;依此类推, 各趟排序均选择无序表部分的最小关键字, 并将其首先定位到最终位置 (无序表表头) , 从而逐步在无序表的表头形成有序表。

理论上讲, 有n个待排序记录需进行n-1趟排序。

算法执行过程中第i趟排序的关键步骤如下:

(1) 首先假定无序表表头记录 (下标为i的记录) 为当前关键字最小记录。

(2) 从第i+1记录开始至第n记录, 依次将各记录关键字同当前最小关键字进行比较, 并记下关键字更小的记录位置, 作为新的当前最小关键字。

(3) 第 (2) 步操作完成即得到第i趟中的最终最小关键字记录, 若该记录不在第i位, 则将其同第i位记录交换, 即完成第i趟排序。

1.2 算法的C语言描述与评价

基于RecordType定义类型的简单选择排序算法可用C语言描述如下 (其中, n为待排序记录个数) :

本算法利用C语言数组下标从0开始的特点, 将r[0]用作交换的中间暂存变量, 算法描述的初始化条件为各待排序记录存放在数组r[] 的1～n号下标单元。

从该算法的C语言描述中可以看出, 函数SelectSort ( ) 的核心语句由双重嵌套循环部分组成, 循环体基本语句 (if语句) 理论上共执行n-1+n-2+…+1=n (n-1) /2次, 此即关键字总的比较次数。将待排序的记录个数n看作问题的规模, 从而算法的平均时间复杂度可以关键字的比较次数来衡量, 即T (n) =O (n2) 。该函数在空间上除了待排序记录元素本身所占的向量空间外, 还引入了三个变量i, j和k的辅助空间, 其空间复杂度为常数阶, 即S (n) =O (1) 。

2 双向选择排序算法

简单选择排序法排序过程中的每一趟循环只能确定一个元素的最终位置, 算法效率不高, 可考虑改进为一趟确定两个元素的位置, 从而减少排序所需的循环次数[4,5,6,7,8,9,10], 称为双向选择排序算法。

双向选择排序算法的基本设计思想如下:

每趟排序均从待排序的无序表区间中选出关键字最小与最大的两个记录, 把最小关键字换到无序表表头, 最大关键字换到无序表表尾, 从而逐渐在无序表的两端形成有序表。这样, 理论上讲有n个待排记录只需进行n/2趟排序。

2.1 算法设计方案一

该方案直接对无序表部分进行双向选择排序。经过一趟排序, 即找到无序表部分的最大和最小关键字记录所在位置, 此时需分以下几种情况进行交换处理:

(1) 若最小关键字记录位于无序表表头, 且最大关键字记录位于无序表表尾, 则此时不需要进行交换即可进行下一趟排序扫描。

(2) 若最小关键字记录和最大关键字记录都不在最终位置, 则分以下几种情况进行交换处理:

①若二者位置刚好相反, 则将二者互换即可。

②若最小关键字记录位于表尾, 而最大关键字记录在除过表头的其它位置, 则按以下步骤处理:

将无序表中的表头记录暂存至r[0]; 将最小关键字记录 (此时即无序表表尾元素) 移至无序表表头位置 (此即其最终位置) ;将最大关键字记录移至无序表表尾 (此即其最终位置) ;将暂存在r[0]中的原表头记录移至最大关键字记录原来所在位置即可完成转换。

③若最大关键字记录位于表头, 而最小关键字记录在除去表尾的其它位置, 则按以下步骤处理:

将无序表中的原表头记录 (最大关键字记录) 暂存至r[0];将最小关键字记录移至无序表表头位置 (此即其最终位置) ;将无序表表尾记录 (下标n-i+1处的记录) 移至最小关键字记录的原位置;将暂存在r[0]中的最大关键字记录移至无序表表尾即可。

④若表头和表尾均不是最大或最小关键字记录, 则按以下步骤处理:

将无序表中的原表头记录暂存至r[0];将最小关键字记录移至无序表表头位置 (此即其最终位置) ;将无序表表尾记录 (下标n-i+1处的记录) 移至最小关键字记录的原位置;将最大关键字记录移至无序表表尾;将暂存在r[0]中的记录移至最大关键字记录空出的原位置即可。

(3) 若最小关键字记录位于表头的最终位置, 但最大关键字记录不在表尾, 则仅将最大关键字记录借助r[0]换到表尾即可。

(4) 若最大关键字记录位于表尾的最终位置, 但最小关键字记录不在表头, 则仅将最小关键字记录借助r[0]换到表头即可。

文献[4]在类似方案一的算法描述中虽然分情况进行了讨论, 但仍有未考虑的情况, 比如当最小关键字记录位于无序表表尾, 而最大关键字记录在除表头之外的其它位置的情况。

文献[5,6,7]关于方案一算法的描述是将选择排序蜕变成交换排序实现的, 相对原算法来说交换次数增多, 从而未能在真正意义上实现对原算法的优化。

文献[8,9,10]中关于该算法的描述均存在没有分情况讨论的问题, 从而排序过程的正确性无法保证。

2.2 方案一算法的C语言描述与评价

该算法的初始化条件同前, 基于RecordType定义类型的C语言描述如下:

从该设计思路的C语言算法描述中可以看出, 函数BiSelectSort_1 ( ) 同样由双重嵌套循环部分组成, 外层循环的循环体由一个循环语句和顺序执行的if语句组成, 因而基本语句为内层循环的循环体, 即两条定位最值的if语句。理论上一趟排序的比较次数为2 (n-2i+1) 次, 从而算法的总比较次数可按如下的公式计算:

${\displaystyle \sum _{i=1}^{n/2}2}(n-2i+1)=\frac{n{}^2}{2}$

可见, 该算法的平均时间复杂度虽仍为T (n) =O (n2) , 但算法中的比较次数略多于简单选择排序算法。另外, 该函数在空间上除了待排序记录元素本身所占的向量空间外, 还引入了四个变量i, j, min和max的辅助空间, 也比函数SelectSort ( ) 多用了一个变量的空间, 但其空间复杂度仍为常数阶, 即S (n) =O (1) 。这样, 该算法虽然同简单选择排序算法具有相同的平均时间复杂度和空间复杂度, 但效率略低于简单选择排序算法;此外又由于分情况讨论, 使得算法的复杂性要高于原算法。

2.3 算法设计方案二

方案一的算法直接对无序表部分进行双向选择, 在经过一趟排序扫描找到最小和最大关键字记录所在位置后, 需要分几种不同情况进行不同的交换处理, 这使得算法描述较为复杂, 可考虑进一步改进。

方案一中的一趟排序选择最值, 是在整个无序表的范围内进行的, 如果一开始先将无序表分割成最小关键字记录只位于表的前半部分, 最大关键字记录只位于表的后半部分, 则定位最小关键字记录只需在表的前半部分进行, 而定位最大关键字记录只需在表的后半部分进行, 从而将最值记录的定位进行了简化。

根据这种设计思想, 该算法第i趟排序的步骤可设计如下:

(1) 首先对无序表区间前后对应位置 (设无序表区间为i～ n-i+1, 则对应记录下标为i和n-i+1, i=1～n/2) 的记录关键字依次进行两两比较, 如有逆序则交换。整个交换过程完成后, 即将无序表中对应位置交换为关键字值较小者在前, 较大者在后。

(2) 在无序表的前半部分定位最小关键字记录, 若非表头记录, 则同表头记录互换。

(3) 在无序表的后半部分定位最大关键字记录, 若非表尾记录, 则同表尾记录互换。

这样共进行n/2趟排序即可完成整个排序过程。

文献[7]中关于方案二算法描述中的一趟排序, 是将前半部分和后半部分分别采用冒泡排序法的思路进行交换排序, 仍然存在比原选择排序算法交换次数增多的问题, 从而算法的执行效率不高。

2.4 方案二算法的C语言描述与评价

该算法的初始化条件同前, 基于RecordType定义类型的C语言描述如下:

从该设计思路的C语言算法描述中可以看出, 函数BiSelectSort_2 ( ) 同样由双重嵌套循环部分组成, 与思路一不同的是, 思路二外层循环的循环体由前后顺序执行的三条for语句组成。一趟排序过程中第一个for循环将无序表中对应位置的记录交换为关键字值较小者在前, 较大者在后, 理论上需进行n/2-i+1次比较;第二、三两个for循环分别在无序表的前半部分定位最小关键字记录, 后半部分定位最大关键字记录, 理论上均需进行n/2-i次比较, 则理论上一趟排序的比较次数为3 (n/2-i) +1次, 从而算法的总比较次数可按以下公式计算如下:

${\displaystyle \sum _{i=1}^{n=2}3}(n/2-i)+1=\frac{3n{}^2}{8}-\frac{n}{4}$

可见, 该算法的比较次数少于简单选择排序算法, 但平均时间复杂度仍为T (n) =O (n2) 。该函数在所占空间上同函数BiSelectSort_1 ( ) 一样, 其空间复杂度也为S (n) =O (1) 。另外, 由于该算法不需分情况讨论, 从而比BiSelectSort_1 ( ) 算法的复杂性大大降低。

3 结束语

双向选择排序算法是基于传统简单选择排序算法提出的一种改进的算法设计思路, 本文介绍的两种算法设计方案的C语言算法描述均已通过在VC++ 6.0环境进行正确性测试。

经过对3种算法进行时间复杂度和空间复杂度的对比分析, 本文最终得出以下结论:

两种设计思路的双向选择排序算法具有和原简单选择排序算法相同的平均时间复杂度和空间复杂度, 但思路一算法总的比较次数略高于原算法, 思路二算法的比较次数低于原算法;两种新算法在辅助空间上都比原算法多用一个变量空间。另外, 两种思路设计的算法就其简单性而言, 第二种优于第一种, 从而第二种思路设计的算法真正实现了对原简单选择排序算法的优化。

本文旨在给出简单选择排序算法的另一种分析设计思路, 纠正部分参考文献中关于该算法的疏漏。经过分析总结两种设计方案的优劣, 为简单选择排序算法的优化提供一定的理论依据, 也对《数据结构》相关章节的教学起到一定的指导作用。

参考文献

[1]耿国华.数据结构—C语言描述[M].西安:西安电子科技大学出版社, 2006.

[2]严蔚敏, 吴伟民.数据结构[M].北京:清华大学出版社, 2000.

[3]Wang Min.Analysis on Bubble Sort Algorithm Optimization[C].2010 International Forum on Information Technology and Applica-tions, July 2010 (待发表) .

[4]梁文忠.一种基于直接选择排序算法的改进[J].广西师范学院学报:自然科学版, 2004, 21 (4) :93-96.

[5]何洪英.两种排序算法的改进[J].绵阳师范学院学报, 2007, 26 (11) :98-99.

[6]江敏.双向选择排序算法[J].泰州职业技术学院学报, 2005, 5 (1) :60-62.

[7]张忆文, 谭霁.简单选择排序算法的改进及分析[J].硅谷, 2009 (18) :77, 94.

[8]葛玮, 刘斌.排序算法的比较、选择及其改进[J].江西广播电视大学学报, 2008 (3) :75-77.

[9]于春霞, 代文征.二路选择排序探讨[J].黄河科技大学学报, 2009, 11 (6) :107-108.

排序算法教学反思 篇10

活动目标：

1、让幼儿能根据图形的排列规律进行排序。

2、培养幼儿初步的观察与比较能力，提高幼儿的判断推理能力。

活动准备：

1、各种图形若干、固体胶

2、幼儿操作纸、双面胶

活动过程：

“小朋友们!今天我收到了图形王国送来的礼物，你们想看吗?”

“好，我们一起来看看，是什么礼物呢?”

1、出示自制头饰，让幼儿自己去发现头饰上图形的排列规律，从而激发他们自制头饰的兴趣。

(1)、老师打开第一个礼物盒：“哇!是一个漂亮的头饰。”(老师戴在头上)

“好看吗?小朋友用你智慧的眼睛观察一下，这个漂亮的头饰是用什么图形做得呢?”

小朋友：红色正方形 黄色圆形 红色正方形 黄色圆形 ……

(2)、小结：图形王国送来的头饰是用图形有规律的排队的。

2、引导幼儿根据图形排队的规律接着排图形。

“奥!小朋友看看，这个大盒子里面么还有一个小盒子呢，我们要不要看看第二个盒子里的礼物呢?”

“呀!有一封信呢!写什么了呢?我给小朋友先读一下：亲爱的小朋友们，你们好!我们图形国王知道大家的本领很大，而且还很乐意帮助别人，现在我们这里有两个头饰没有装饰完，我们图形国王想请你们帮忙把他们装饰完!你们愿意吗?”

(1)、出示第一个头饰：蓝花 红花 黄花 蓝花 红花 黄花……

让幼儿通过观察发现规律，再补充后面的规律，小朋友边说教师边操作。操作完之后，让幼儿说说这一规律。

(2)、出示第二个头饰：黄圆形 绿三角形 绿三角形 黄圆形 绿三角形 绿三角形

请幼儿观察，然后请一位小朋友上来操作，并说说这一规律。

(3)、教师小结：原来图形王国的头饰是用图形有规律的排队来装饰的，所以很漂亮。

3、操作活动：(装饰头饰)幼儿按照规律，运用自己喜欢的方法给图形排序。

“我们看看还有没有盒子了，呀!还有一个呢!我们来看看第三个盒子里面的礼物是什么?(一张请柬)上面写得什么呢?“教案来自：屈;老师教;案网.”我来读一下。小朋友们，你们太聪明了，为了奖赏你们，我们图形国王邀请你们去参加一个舞会，但是你们要打扮一下自己奥，每个小朋友要戴上一个漂亮的头饰，而且头饰上面的图形要按照一定的规律排序，戴上头饰的小朋友才能进去参加舞会。”

4、幼儿操作活动，教师巡视指导。

5、操作评价

(1)、老师展示个别幼儿作品，请幼儿说说，他是怎么做得。

(2)、表扬做得好的幼儿。

6、带幼儿一起去参加舞会，放音乐，师幼舞蹈。(也可让幼儿邀请下面的老师)

活动延伸：

带孩子进教室，在区域活动中，让孩子运用多种材料，用多种方法进行排序。如：按照长短、大小、高矮、形状、用途等等开展丰富多彩的、有难易程度不一的排序活动。

教学反思：

数学来源与现实，存在于现实，并且应用与现实，数学过程应该是帮助幼儿把现实问题转化为数学问题的过程。教育活动的内容选择应既贴近幼儿的生活来选择幼儿感兴趣的事物和问题，有助于拓展幼儿的经验和视野。充分利用幼儿现实生活中的资源，通过作用于幼儿的活动对幼儿发生实质性的影响，让幼儿在生活和游戏中感受事物的数量关系，体验数学的重要和有趣。

排序算法教学反思 篇11

在IT届有一道百算不厌其烦的题，俗称排序，不管是你参加BAT等高端笔试，亦或是藏匿于街头小巷的草根笔试，都会经常见到这样一道百年难得一解的问题。

今天LZ有幸与各位分享一下算法届的草根明星，排序届的领衔大神——插入排序以及归并排序。最后，在头脑风暴下，LZ又有幸认识了一位新朋友，名叫并行归并排序。接下来，咱们就一一认识一下，并且在最后来一次“算林大会”吧。

插入排序简介

插入排序，算林称最亲民的排序算法，插入排序采用最简单的插入方式对一个整数数组进行排序。它循环数组中从第二个开始的所有元素，并且将每一个循环到的元素插入到相应的位置，从而实现排序的目的。

插入排序的代码展示

使用Java代码描述插入排序，可以用以下的代码。

package algorithm;

/**

* @author zuoxiaolong

*

*/

public abstract class InsertSort {

public static void sort(int[] numbers){

for (int i = 1; i < numbers.length; i++) {

int currentNumber = numbers[i];

int j = i - 1;

while (j >= 0 && numbers[j] > currentNumber) {

numbers[j + 1] = numbers[j];

j--;

}

numbers[j + 1] = currentNumber;

}

}

}

复制代码

这个算法从数组的第二个元素开始循环，将选中的元素与之前的元素一一比较，如果选中的元素小于之前的元素，则将之前的元素后移，最后再将选中的元素放在合适的位置。在这个算法执行的过程中，总是保持着索引i之前的数组是升序排列的。

插入排序理解起来比较简单，因此LZ就不过多的解释它的实现原理了，尚未理解的猿友可以自行研究。

插入排序的性能分析

接下来，咱们来简单分析一下插入排序的性能。首先，插入排序当中有两个循环，假设数组的大小为n，则第一个循环是n－1次，第二个while循环在最坏的情况下是1到n－1次。因此插入排序的时间复杂度大约为如下形式。

1+2+3+4+...＋n－1 ＝ n（n－1）/ 2 ＝ O（n2）

时间复杂度为输入规模的2次函数，可见插入排序的时间复杂度是比较高的。这是原理上的简单分析，最后在“算林大会”中，各位可以清楚的看到插入排序随着输入规模的增长，时间会指数倍的上升。

归并排序简介

归并排序，算林届的新秀，引领着分治法的潮流。归并排序将排序问题拆分，比如分成两个较小的数组，然后对拆分后的数组分别进行排序，最后再将排序后的较小数组进行合并。

这种思想是一种算法设计的思想，很多问题都可以采用这种方式解决。映射到编程领域，其实就是递归的思想。因此在归并排序的算法中，将会出现递归调用。

归并排序的代码展示

归并排序主要由两个方法组成，一个是用于合并两个已经排序的数组的方法，一个则是递归方法，用于将问题无限拆分。接下来咱们一起看看归并排序的Java代码展示，如下所示。

package algorithm;

/**

* @author zuoxiaolong

*

*/

public abstract class MergeSort {

public static void sort(int[] numbers){

sort(numbers, 0, numbers.length);

}

public static void sort(int[] numbers,int pos,int end){

if ((end - pos) > 1) {

int ffset = (end + pos) / 2;

sort(numbers, pos, offset);

sort(numbers, offset, end);

merge(numbers, pos, offset, end);

}

}

public static void merge(int[] numbers,int pos,int offset,int end){

int[] array1 = new int[offset - pos];

int[] array2 = new int[end - offset];

System.arraycopy(numbers, pos, array1, 0, array1.length);

System.arraycopy(numbers, offset, array2, 0, array2.length);

for (int i = pos,j=0,k=0; i < end ; i++) {

if (j == array1.length) {

System.arraycopy(array2, k, numbers, i, array2.length - k);

break;

}

if (k == array2.length) {

System.arraycopy(array1, j, numbers, i, array1.length - j);

break;

}

if (array1[j] <= array2[k]) {

numbers[i] = array1[j++];

} else {

numbers[i] = array2[k++];

}

}

}

}

可以看到，归并排序将一个长度为n的数组平均分为两个n/2的数组分别进行处理，因此，在sort方法中又调用了两次sort方法自身。当数组大小为1时，则认为该数组为已经为排好序的数组。因此在sort方法中，需要end与pos相差大于2时，才需要进一步拆分，这也是递归的终止条件。

此外，在代码中，使用了Java提供的arraycory函数进行数组复制，这种直接复制内存区域的方式，将会比循环赋值的方式速度更快。有些算法实现会给merge方法中的两个临时数组设置哨兵，目的是为了防止merge中for循环的前两个if判断。为了方便理解，LZ这里没有设置哨兵，当某一个数组的元素消耗完时，将直接使用arraycopy方法把另外一个数组copy到numbers当中。

归并排序的性能分析

与插入排序一样，咱们来简单分析一下归并排序的时间复杂度。咱们假设数组的大小为n，sort方法的时间复杂度为f（end－pos）。简单的分析merge方法的复杂度，不难发现为（end－pos）＊2，这个结果的前提是咱们认为arraycopy方法的复杂度为length参数。

基于以上的假设，由于end－pos的初始值为n，因此归并排序的复杂度大约为如下形式。

2＊f（n/2） ＋ 2＊n ＝ 2＊（2＊f（n/4）＋2＊（n/2）） ＋ 2＊n＝4＊f（n/4） ＋ 2＊n ＋ 2＊n ＝ n ＊f（1） ＋ 2＊n ＋...＋2＊n

其中f（1）的时间复杂度为常量，假设f（1）＝c，而2＊n将有log2n个。因此咱们得到归并排序的最终时间复杂度为如下形式。

cn ＋ 2n＊log2n ＝ O（n＊log2n）

归并排序的时间复杂度与插入排序相比，已经降低了很多，这一点在数组的输入规模较大时将会非常明显，因为log函数的增加速度将远远低于n的增加速度。

并行归并排序简介

并行归并排序是LZ在学习归并排序时意淫出来的，最近LZ正在研究Java的并发编程，恰好归并排序的子问题有一定的并行度与独立性，因此LZ版的并发归并排序就这样诞生了。事后，LZ也人肉过并行归并排序这个家伙，发现早已众所周知，不过在不知道的情况下自己能够想到是不是也应该窃喜一下呢。

并行归并排序与普通的归并排序没有多大区别，只是利用现在计算机多核的优势，在有可能的情况下，让两个或多个子问题的处理一起进行。这样一来，在效率上，并行归并排序将会比归并排序更胜一筹。

并行归并排序的代码展示

并行归并排序主要对sort方法进行了修改，基础的merge方法与普通的归并排序是一样的。因此在进行并行归并排序时，引用了归并排序的一些方法，具体的代码如下所示。

package algorithm;

import java.util.concurrent.CountDownLatch;

/**

* @author zuoxiaolong

*

*/

public abstract class MergeParallelSort {

private static final int maxAsynDepth = (int)(Math.log(Runtime.getRuntime.availableProcessors())/Math.log(2));

public static void sort(int[] numbers) {

sort(numbers, maxAsynDepth);

}

public static void sort(int[] numbers,Integer asynDepth) {

sortParallel(numbers, 0, numbers.length, asynDepth > maxAsynDepth ? maxAsynDepth : asynDepth, 1);

}

public static void sortParallel(final int[] numbers,final int pos,final int end,final int asynDepth,final int depth){

if ((end - pos) > 1) {

final CountDownLatch mergeSignal = new CountDownLatch(2);

final int ffset = (end + pos) / 2;

Thread thread1 = new SortThread(depth, asynDepth, numbers, mergeSignal, pos, offset);

Thread thread2 = new SortThread(depth, asynDepth, numbers, mergeSignal, offset, end);

thread1.start();

thread2.start();

try {

mergeSignal.await();

} catch (InterruptedException e) {}

MergeSort.merge(numbers, pos, offset, end);

}

}

static class SortThread extends Thread {

private int depth;

private int asynDepth;

private int[] numbers;

private CountDownLatch mergeSignal;

private int pos;

private int end;

/**

* @param depth

* @param asynDepth

* @param numbers

* @param mergeSignal

* @param pos

* @param end

*/

public SortThread(int depth, int asynDepth, int[] numbers, CountDownLatch mergeSignal, int pos, int end) {

super();

this.depth = depth;

this.asynDepth = asynDepth;

this.numbers = numbers;

this.mergeSignal = mergeSignal;

this.pos = pos;

this.end = end;

}

@Override

public void run() {

if (depth < asynDepth) {

sortParallel(numbers,pos,end,asynDepth,(depth + 1));

} else {

MergeSort.sort(numbers, pos, end);

}

mergeSignal.countDown();

}

}

}

在这段代码中，有几点是比较特殊的，LZ简单的说明一下，

1，分解后的问题采用了并行的方式处理，并且咱们设定了一个参数asynDepth去控制并行的深度，通常情况下，深度为(log2CPU核数)即可。

2，当子问题不进行并行处理时，并行归并排序调用了普通归并排序的方法，比如MergeSort.sort和MergeSort.merge。

3，因为合并操作依赖于两个子问题的完成，因此咱们设定了一个合并信号（mergeSignal），当信号发出时，才进行合并操作。

并行归并排序在原理上与普通的归并排序是一样的，只是对于子问题的处理采用了一定程度上的并行，因此如果猿友们理解归并排序，那么并行归并排序并不难理解。

并行归并排序的性能分析

并行归并排序只是将普通归并排序中一些可并行的操作进行了并行处理，因此在总体的时间复杂度上并没有质的变化，都是O（n＊log2n）。

由于并行归并排序将某些排序操作并行操作，因此在性能上一定是快于普通归并排序算法的。不过这也不是一定的，当数组规模太小时，并行带来的性能提高可能会小于线程创建和销毁的开销，此时并行归并排序的性能可能会低于普通归并排序。

算林大会

接下来，就是一周一度的算林大会了，本次算林大会主要由以上三种算法参加，胜者将会成为本周度最受欢迎算法。接下来是算林大会的代码，请各位猿友过目。

package algorithm;

import java.io.File;

import java.lang.reflect.Method;

import java.util.Random;

/**

* @author zuoxiaolong

*

*/

public class SortTests {

public static void main(String[] args) {

testAllSortIsCorrect();

testComputeTime(“MergeParallelSort”, 40000, 5);

testComputeTime(“MergeSort”, 40000, 5);

testComputeTime(“InsertSort”, 400, 5);

}

public static void testAllSortIsCorrect() {

File classpath = new File(SortTests.class.getResource(“”).getFile());

File[] classesFiles = classpath.listFiles();

for (int i = 0; i < classesFiles.length; i++) {

if (classesFiles[i].getName().endsWith(“Sort.class”)) {

System.out.println(“---测试” + classesFiles[i].getName() + “是否有效---”);

testSortIsCorrect(classesFiles[i].getName().split(“.”)[0]);

}

}

}

public static void testSortIsCorrect(String className){

for (int i = 1; i < 50; i++) {

int[] numbers = getRandomIntegerArray(1000 * i);

invoke(numbers, className);

for (int j = 1; j < numbers.length; j++) {

if (numbers[j] < numbers[j-1]) {

throw new RuntimeException(className + “ sort is error because ” + numbers[j] + “<” + numbers[j-1]);

}

}

}

System.out.println(“---” + className + “经测试有效---”);

}

public static void testComputeTime(String className,int initNumber,int times,Object... arguments) {

long[] timeArray = new long[times];

for (int i = initNumber,j = 0; j < times; i = i * 10,j++) {

timeArray[j] = computeTime(i, className, arguments);

}

System.out.print(className + “时间增加比例：”);

for (int i = 1; i < timeArray.length ; i++) {

System.out.print((float)timeArray[i]/timeArray[i - 1]);

if (i < timeArray.length - 1) {

System.out.print(“,”);

}

}

System.out.println();

}

public static long computeTime(int length,String className,Object... arguments){

int[] numbers = getRandomIntegerArray(length);

long start = System.currentTimeMillis();

System.out.print(“开始计算长度为”+numbers.length+“方法为”+className+“参数为[”);

for (int i = 0; i < arguments.length; i++) {

System.out.print(arguments[i]);

if (i < arguments.length - 1) {

System.out.print(“,”);

}

}

System.out.print(“]，时间为”);

invoke(numbers, className, arguments);

long time = System.currentTimeMillis()-start;

System.out.println(time + “ms”);

return time;

}

public static int[] getRandomIntegerArray(int length){

int[] numbers = new int[length];

for (int i = 0; i < numbers.length; i++) {

numbers[i] = new Random().nextInt(length);

}

return numbers;

}

public static void invoke(int[] numbers,String className,Object... arguments){

try {

Class

Class

parameterTypes[0] = int[].class;

for (int i = 0; i < arguments.length; i++) {

parameterTypes[i + 1] = arguments[i].getClass();

}

Method method = clazz.getDeclaredMethod(“sort”, parameterTypes);

Object[] parameters = new Object[parameterTypes.length];

parameters[0] = numbers;

for (int i = 0; i < arguments.length; i++) {

parameters[i + 1] = arguments[i];

}

method.invoke(null, parameters);

} catch (Exception e) {

throw new RuntimeException(e);

}

}

}

以上代码testAllSortIsCorrect方法首先验证了三种算法的正确性，也就是说经过sort方法后，数组是否已经升序排列。需要一提的是，由于插入排序的性能太低，因此插入排序测试的最大规模为400万，而归并排序测试的最大规模为4亿。

接下来，大家就一起看看运行结果吧。以下是在LZ的mac pro上的运行结果，硬件配置为16G内存，4核i7。这种配置下，异步深度（asynDepth）默认为log24=2。

---测试InsertSort.class是否有效---

---InsertSort经测试有效---

---测试MergeParallelSort.class是否有效---

---MergeParallelSort经测试有效---

---测试MergeSort.class是否有效---

---MergeSort经测试有效---

开始计算长度为40000方法为MergeParallelSort参数为[]，时间为6ms

开始计算长度为400000方法为MergeParallelSort参数为[]，时间为44ms

开始计算长度为4000000方法为MergeParallelSort参数为[]，时间为390ms

开始计算长度为40000000方法为MergeParallelSort参数为[]，时间为3872ms

开始计算长度为400000000方法为MergeParallelSort参数为[]，时间为47168ms

MergeParallelSort时间增加比例：7.3333335,8.863636,9.9282055,12.181818

开始计算长度为40000方法为MergeSort参数为[]，时间为7ms

开始计算长度为400000方法为MergeSort参数为[]，时间为81ms

开始计算长度为4000000方法为MergeSort参数为[]，时间为839ms

开始计算长度为40000000方法为MergeSort参数为[]，时间为9517ms

开始计算长度为400000000方法为MergeSort参数为[]，时间为104760ms

MergeSort时间增加比例：11.571428,10.358025,11.343266,11.00767

开始计算长度为400方法为InsertSort参数为[]，时间为0ms

开始计算长度为4000方法为InsertSort参数为[]，时间为3ms

开始计算长度为40000方法为InsertSort参数为[]，时间为245ms

开始计算长度为400000方法为InsertSort参数为[]，时间为23509ms

开始计算长度为4000000方法为InsertSort参数为[]，时间为3309180ms

InsertSort时间增加比例：Infinity,81.666664,95.9551,140.76227

复制代码

首先可以看到，三种算法都是运行正确的。接下来，咱们可以对比一下三种算法的性能。

根据输出结果，规模为400万时的区别是最明显与直观的。并行归并排序仅需要390ms就完成了400万规模的排序，而普通的归并排序则需要839ms才可以，至于插入排序，简直是不可理喻，竟然需要300多万ms，大约50分钟。

咱们再来看三者的时间增长趋势。两种归并排序基本上与规模的增长趋势相似，每当规模增加10倍时，时间也基本上增加10倍，而插入排序则几乎是以100倍的速度在增加，刚好是数组规模增长速度的平方。其中的Infinity是因为当数组规模为400时，毫秒级别的计时为0ms，因此当除数为0时，结果就为Infinity。