排序算法课程设计（精选12篇）
排序算法课程设计 篇1
一、内容分析
【教学目标】
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%的学生的成绩。
排序算法课程设计 篇2
关键词：静态排序,算法复杂度,记录比较,记录移动
0 引 言
随着各行各业的飞速发展,计算机需要存储与处理的数据也在以惊人的速度增加。在如此庞大的数据群中,人们为了便于检索,通常希望能在计算机中保存的数据是按关键字值大小排列的有序表。在现今的计算机系统中,有相当大的一部分CPU时间开销是用于对数据的排序整理上的,而在这一部分CPU时间开销中,记录移动所引起的CPU时间开销又占据了相当大的一部分,并且如果待排序的记录相当大(即每个记录所占空间较多)时,记录移动所引起的CPU时间开销将对整个数据排序的CPU时间开销起到决定性的作用。因此,学习和研究各种排序算法,分析并设计出高效适用的排序算法,是摆在计算机科学工作者面前的重要课题之一。为了解决大量的记录移动而引起的CPU时间开销问题,本文提出了静态排序算法。这是一种记录移动次数(2n)恒定的稳定的内部排序算法。
1 算法的定义与核心思想
1.1 定 义
静态排序算法是一种通过对数组Value[1…n]中任意两个记录比较来计算出每个记录在已排序数组中的索引值并把其储存在数组Index[1…n]中,进而由Result[Index [i]]=Value[i]直接得到已排序数组Result[1…n]以达到对数据排序的目的稳定的内部排序算法。
1.2 核心思想
每个记录在已排序数组中的索引值与其所在的数组中比它本身大(小)的记录的个数有关。具体而言,若在一个数组中小于记录A的记录有k(0<=k<n-1)个,则当对该数组排序后所得到的数组中记录A的索引值一定为k(规定:若Value[i]== Value[j]且i<j则Value[i]< Value[j])。由原数组记录值及各个记录在已排序数组中的索引值直接构成有序数组。
2 算法的实现
2.1 排序实现
静态排序算法的实现过程主要分为三步。
第一步 通过记录值比较来求得各个记录在已排序数组中的索引值。求索引值的过程中有两种不同的情况。情况一:数组中任意两个记录的值大小都不相同,此时在数组中比记录A的值小的记录的个数则为记录A在已排序数组中的索引值。情况二:数组中至少存在两个记录的值相同,假设这两个值相同的记录分别为记录C和记录D,此时比记录C和记录D的值(假设记录D比记录C在原数组中的索引值大)小的记录的个数则不可能同时是记录C和记录D在已排序数组中的索引值。为了保持静态排序是稳定排序的特性,假设记录D的值要比记录C的值大。综合上述两种情况所述,若记录X的值小于比其索引值大的记录Y的值则记录Y在已排序数组中的索引值加1,否则记录X在已排序数组中的索引值加1。当对数组中任意两个记录进行比较后,就可以得到所有记录在已排序数组中的索引值。
第二步 由数组Value[1…n]与数组Index[1…n]直接构成有序数组。其中巧妙地应用了两个数组相同位置的对应关系,即Index[i]中存储的索引值恰巧是Value[i]在已排序数组中的索引值。因此,可以得出Result[Index[i]]=Value[i]。这是一个有序有目的地插入记录的过程。当遍历了整个数组Index[1…n]后,所有的记录就有序地插入到了结果数组中,最终得到有序数组Result [1…n]。
第三步 把结果数组Result [1…n]中的所有记录拷贝到原数组Value[1…n]中,最终实现原数组的排序目的。下面是用算法语言描述静态排序的过程。静态算法如算法1所示[1,2,3]。
2.2 测试结果
如图1所示:原先数组是一个无序数组,调用静态排序算法排序后得到一个有序的数组,从而验证了静态排序算法的正确性。
3 算法及测试结果的分析
表1是在测试静态排序算法过程中各变量值及存储值的变化情况(表中CC是记录的比较次数)。
从表1可得每一趟比较都会得出在数组中比该记录小的记录的个数,这个数值也正好是该记录在已排序数组中的索引值。分析静态排序的效率:
时间复杂度:
需进行n(n-1)/2次比较,且移动记录2n次。因此,总的时间复杂度为Ο(n2)。
空间复杂度:
需要借助一个长度为n的整型数组空间和一个原数组相同的数组空间。所以空间复杂度为О(n)。
4 各种算法的比较与分析
4.1 各种算法的平均复杂度
如表2所示,从时间复杂度上看,静态排序、起泡排序、插入排序、选择排序的平均时间复杂度均为Ο(n2),而希尔排序、快速排序和归并排序的平均时间复杂度均为Ο(nlog2n)。从空间复杂度上来看,起泡排序、插入排序、希尔排序、选择排序仅需一个存储空间,空间复杂度为О(1)。静态排序与归并排序都需要与n同级别的空间,空间复杂度为О(n)。而快速排序需要的空间与原数组中记录的顺序有关,需要(log2n,n)个存储空间,空间复杂度为О(n)。
4.2 各种算法的记录的比较次数与移动次数
4.2.1 根据记录比较与移动次数的理论值分析比较算法
各种算法的记录比较次数的理论值如表3所示。
各种算法的记录移动次数的理论值如表4所示。
4.2.2 根据记录比较与移动次数的实验值分析比较算法
以下四张图是根据1000次实验得到的数据绘制而成的。为了真实地模拟实际中的排序问题,每次的测试数据都由随机数构造而成。
图2是各种排序算法中记录移动次数的总体比较,从图中可以看出起泡排序的记录移动次数是最多的,且比其它的排序方法的移动次数要多很多,插入排序的移动次数次之。其余五种排序方法的移动次序要少很多。
图3是图2中其余五种排序算法的记录移动次数的详细比较图,从图中可以得出静态排序的移动次数是最少的,快速排序次之,接着是选择排序,然后是希尔排序,最后是归并排序。所以只从记录的移动次数来看,静态排序是最优的。
图4是各种算法中记录比较次数的总体比较图,从图中可以直观地发现静态排序、起泡排序、静态排序的比较次数是最多的,大约是n2/2,插入排序的移动次数次之,大约是n2/4。
图5是图4中其余三种排序算法中记录比较次数的详细比较图,从图中可以看出归并排序的比较次数是最小的,快速排序次之,再次是希尔排序。同时根据各种排序算法的比较次数曲线变化幅度可以得出快速排序和希尔排序的比较次数受记录初始顺序的影响较大,而归并排序的比较次数受到记录初始顺序的影响却很小。
4.3 各种算法的稳定性
根据排序算法稳定性的定义以及各种算法的核心思想及实现可得静态排序、插入排序、起泡排序、选择排序和归并排序是稳定的,而希尔排序与归并排序是不稳定的。
4.4 各种算法的简单性
从算法简单性看,静态排序、插入排序、选择排序和起泡排序是简单算法,而希尔排序、快速排序和归并排序是经过改进后的算法,因此是复杂算法。
5 结 语
数据排序所引起CPU时间开销主要由排序过程中的记录比较次数和移动次数决定。从待排序的记录个数n的大小看,n越小,采用简单排序方法越合适,n越大,采用改进的排序方法越合适。因为n越小,Ο(n2)同Ο(nlog2n)的差距越小,并且输入和调试简单算法比输入和调试改进算法要少用许多时间。 从记录本身信息量看,若记录本身信息量越大,则移动记录所花费的时间就越多,所以对记录的移动次数较多的算法不利。在这种情况下,移动次数越小的算法将越有优势,本文提出的静态排序算法也就是为了更好地适应这种情况而提出的。
起泡排序是最简单的排序算法,在各个算法中平均效率是最低的,但便于理解,适用于记录个数n较小的排序中。
选择排序是一种简单排序算法,它的比较次数非常大,但是移动次数相对较小,所以适用于记录个数n较小而记录本身信息量较大的排序中[5]。
插入排序也是一种简单排序算法,它的比较次数和移动次数都比较大,约为n2/4,适用于记录个数n较小的排序中[6]。
希尔排序中当n在某个特定的范围内时,所需的比较次数约为n1.3,移动次数约为3n1.3,适用于记录个数较大而记录本身信息量较小的排序中[7]。
快速排序的平均时间为klog2n,从平均时间性能而言,快速排序最佳[4],适用于记录个数n较大的排序中[8]。
归并排序的平均时间复杂度为Ο(nlog2n),空间复杂度为О(n),适用于记录个数n较大而记录信息量也较大的排序中[9]。
静态排序是一种稳定的简单排序算法,它的记录比较次数非常大,但移动次数却是所有算法中最小的,并且记录的比较次数和移动次数仅与记录个数n有关而与记录的初始顺序无关,因此适应于记录个数n较小而记录信息量非常大的排序中。
参考文献
[1]阿霍,霍普克劳夫特,乌尔曼.计算机算法的设计与分析[M].黄林鹏,王德俊,张仕,译.机械工业出版社,2007.
[2]科曼,等.算法导论[M].潘金贵,等译.机械工业出版社,2006.
[3]郑宗汉,郑晓明.算法设计与分析[M].电子工业出版社,2010.
[4]严蔚敏,吴伟民.数据结构[M].清华大学出版社,2010.
[5]张明亮,李兴良.选择排序的一种改进及分析[J].苏州科技学院学报,2007,24(2).
[6]李宝艳,马英红.排序算法研究[J].电脑知识与技术,2007,2(8).
[7]杨智明.希尔排序算法实现与分析[J].电脑编程技术与维护,2010(2).
[8]杨锋英,刘会超.改进的快速排序算法[J].科技广场,2010(1).
选择排序算法总结 篇3
/** * 找到最小的元素 * @param array 输入的数组 * @param arraySize 数组大小 * @param minNumber 输出最小值 * @return 最小值在数组里面的位置 */MinMaxPair findMinMax(int array[] , int arraySize , int * minNumber , int * maxNumber){ /** 省略了一些代码 */ for (int i = 0; i < arraySize; ++i) { if(array[i] < minNumberTemp) {minNumberTemp=array[i];minPos = i; } if(array[i] >maxNumberTemp) {maxNumberTemp = array[i];maxPos = i; } } /** 省略了一些代码 */}
这里在一个循环里面要进行两次比较，于是运行时间为
排序算法（一） 篇4
首先参考大话数据结构定义一个链表类：
#include
冒泡排序法：
/** *冒泡排序即相邻的两者相互比较，根据需求把较大的或较小的前移或后移 *记住，两两相邻的比较是冒泡排序的特点之一 */void BubbleSort1(SqList* list){//每次遍历时把较大者后移 int length=list->length; while(length>0) { for(int i=0;i
选择排序法：
/** *选取排序即每次在未排序队列当中选取一个最小值，然后与第i个值进行交换，直至i为length为止； *当然，也可以选取最大值把到后面，根据需求而定 */void selectSort(SqList* list){ for (int i = 0; i < list->length; ++i) { int min = list->data[i]; int pos = i; for (int j = i+1; j < list->length; ++j) { if (list->data[j] < min) { min = list->data[j]; pos = j; } } if (pos != i) { swap(list->data[i], list->data[pos]); } }}
简单插入排序法：
/** *遍历链表，把每个元素插入到正确位置 */void InsertSort1(SqList *list){ for (int i = 1; i < list->length; ++i) { int j = i - 1; for (; j >=0; j--) { if (list->data[i] >list->data[j]) break; } int tmp = list->data[i]; for (int k = i; k >j+1; --k) { list->data[k] = list->data[k - 1]; } list->data[j + 1] = tmp; }}void InsertSort2(SqList *list){ for (int i = 1; i < list->length; ++i) { if (list->data[i] < list->data[i - 1]) { int tmp = list->data[i]; int j = i-1; for (; j >= 0 && list->data[j] >tmp; --j) {//查找的同时，进行后移操作 list->data[j + 1] = list->data[j]; } list->data[j + 1] = tmp; } }}
希尔排序法（简单插入排序的改进）：
python实现排序算法 篇5
2014-02-02python发布模块的步骤分享
2014-03-03Python 列表(List)操作方法详解
2014-02-02go和python调用其它程序并得到程序输出
2014-04-04python中的实例方法、静态方法、类方法、类变量和实例变量浅析
2014-05-05Python random模块（获取随机数）常用方法和使用例子
2012-12-12python cookielib 登录人人网的实现代码
2008-09-09Python httplib，smtplib使用方法
2013-11-11pyramid配置session的方法教程
2014-03-03python实现k均值算法示例(k均值聚类算法)
★ 排序算法总结
★ python关键字and和or用法实例
★ Python 随机生成中文验证码的实例代码
★ python中的实例方法、静态方法、类方法、类变量和实例变量浅析
★ python使用sorted函数对列表进行排序的方法
★ 在Python中使用sort方法进行排序的简单教程
★ 算法实验体会与总结怎么写
★ 中考语文语句排序方法总结
★ Python struct模块解析
JAVA泛型排序算法设计思想 篇6
关键词：java泛型排序,局部排序,spring框架
0引言
众所周知，排序是程序设计中经常用到的功能，非常讲究时间效率。常用的排序有3种类型：全局排序、局部排序、求第nth元素。JAVA语言中全局排序是由固有函数sort来完成的，没有固有的局部排序及求第nth元素函数。但是在实际中这两种排序是经常存在的。例如：求一个班成绩最好的3名同学信息，按成绩由高到低排列。其实，只需要通过某算法保证前3位同学有序且符合条件，后面所有同学没有必要是有序的，这就是局部排序。如果利用sort函数进行全排序，前3位即所求，当然是可以的。但无形中提高了时间开销。再如：求一个班成绩第5名同学信息。其实，只要保证第5名同学成绩低于前4名，高于其后同学成绩即可，没有必要保证除第5名之外的所有同学成绩都是有序排列的，这就是求第nth元素功能。因此，局部排序及求第nth元素功能是对JAVA固有sort函数的有益补充，是本文讨论的中心所在。
1局部排序及求第nth元素设计思想
1.1总体设计思想
关键是设计好两种排序算法。可以借鉴c++标准模板库中的partial_sort算法及nth_element算法。这两种算法都是专家级的，因此只要把它们移植到java中，就能实现专家级的相应排序功能，这即是本文所论述排序功能总体设计思想。
1.1.1局部排序算法
VC6.0中局部排序关键源码如下所示。
可以看出，局部排序主要是堆排序的灵活应用，执行后[_F,_M)指向元素是有序的，是所求结果，而[_M,_L)指向元素未必是有序的，按表意形式该算法描述如下所示。
按图1算法后[_F,_M)中指向任意元素与[_M,_L)相比，均满足函数_P关系。
1.1.2求第nth元素算法
VC6.0中该函数关键源码如下所示。
可以看出，该算法主要是3点中值划分算法的灵活运用。执行后，_Nth指向元素是所求结果，[_F,_M)及(M,_L]指向的序列元素未必是有序的按表意形式该算法描述如下所示。
总之，该算法以首、尾、中央三点中值划分，将整个序列分割为左、右子序列。若nth指向元素在左子序列内，就再对左子序列进行分割，否则就再对右子序列进行分割。当分割后子序列元素数少于16个(_SORT_MAX),则不必再划分，直接对该子序列进行直接插入排序即可。
1.2总体实现框图
C++标准模板库中partial_sort、nth_element是泛型函数，可适用基本数据类型及对象。但是java中泛型参数只支持类对象，不能是基本数据类型。因此在java中：对基本数据类型而言只能一对一编程;对类而言，可采用泛型参数。本文主要讨论后者，其框图如图3所示。
(1)成员函数中前5个函数与局部排序功能相关，后5个函数与求第nth元素功能相关。
(2)成员变量中有一个泛型数阻t[],可知成员函数主要是以其为操作对象的。，对于基本序列容器，如对象存储在Vector、ArrayList、LinkedList等容器中，由于这些容器都有共同的父接口List。有巧妙的方法可实现图3中partial_sort(List
从图中可以看出：由于基本序列容器中都有toArray()函数，因此只须把对象容器转化为对象数组，执行已编制好的对象数组的相应功能函数，再修改对象容器中每个元素的值即可。
(3)成员函数中有一个泛型比较器接口Comparator，在JAVA固有排序sort函数中要用到，为了统一性，该接口不需要自定义的形式，应用系统原有即可。
2关键代码分析
2.1局部排序关键代码
两个重载的partial_sort函数功能是主要的，关于堆操作的三个函数都是很普通的。
可以看出,该函数应用了2.1.1中所描述局部排序的算法。
2.2求第nth元素关键代码
可以看出，该函数应用了2.1.2中所描述求第nth元素的算法。
2.3关于比较器Comparator
实际应用中，必须定义该接口的若干个实现类。例如若定义一个关于整形对象的比较器，则形式如下所示。
3灵活管理排序功能模块
本文以图3中接口MyAlgoIntr内容来论述的，仅有一个实现类MyAlgo。若MyAlgoIntr接口有多个实现类，每个类中又需要许多自定义比较器类，很明显需要工厂模式来管理这些类对象。其实采用spring框架就可以完成所需功能，避免了人为的低层次的工厂类的开发。
例如，某sort.xml配置文件如下所示。
通过此配置文件可加载功能类MyAlgo及自定义比较器类MyLess。例如：若求某Vector
可知：若配置文件中还有标识符“MyAlgo2”对应功能模块，还有标识符“MyLess2”对应比较器类，那么上述代码只需把getBean(“MyAlgo”)改为getBean(“MyAlgo2”)，getBean(“MyLess”)改为getBean(“MyLess2”)，其余不变，就可完成所需的另外一个排序功能。
因此借助Spring框架，可以编制非常灵活的选择排序功能模块及其组合程序。
4结语
本文主要在JAVA中移植了C++标准模板库中局部排序及求第nth元素算法。从分立角度来看，用到的都是学习过的常用算法，但如何把这些单独算法组合完成某一具体功能，却并不容易，我们可以从C++标准模板库中体会其精妙之处。
当然，如何全方位在JAVA中移值C++标准模板库中的算法，如何屏蔽迭代器、算法、容器间的差异等，这些都是值得继续深思的问题。
参考文献
[1]陈林,徐宝文.基于源代码静态分析的C++泛型概念抽取.计算机学报,2009,(32):9.
[2]陈林,徐宝文,钱巨等.一种基于类型传播分析的泛型实例重构方法.软件学报,2009,(20):10
[3]徐文胜,薛锦云.泛型编程扩展及其JAVA实现.计算机工程与科学.2007年.Vol(29):10
[4]王会进,陆裕奇,陈超华.设计模式和泛型技术在系统重构中的应用研究.计算机工程与设计,2007,(28):3.
PHP简单选择排序算法实例 篇7
简单的选择排序算法：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i(1<=i<=n)个记录交换
代码如下:
class Sort{
/**
* 简单的选择排序
*
* @param unknown_type $arr
*/
public function selectSort(&$arr) {
$len=count($arr);
for ($i=0;$i<$len;$i++) {
$min=$i;
for ($j=$i+1;$j<=$len-1;$j++) {
if ($arr[$min]>$arr[$j]) {//如果找到比$arr[$min]较小的值，则将该下标赋给$min
$min=$j;
}
}
if ($min!=$i){//若$min不等于$i，说明找到了最小值，则交换
$this->swap($arr[$i],$arr[$min]);
}
}
}
/**
* 将$a和$b两个值进行位置交换
*/
public function swap(&$a,&$b) {
$temp=$a;
$a=$b;
$b=$temp;
}
}
$arr=array(4,6,1,2,9,8,7,3,5);
$test=new Sort;
$test->selectSort($arr);//简单的选择排序
//var_dump($arr);
?>
简单选择排序的特点：交换移动数据次数相当少，从而节约了相应的时间
简单选择排序的时间复杂度分析：
无论最好最差的情况，其比较次数都是一样多，第i趟排序需要进行n-i次关键字的比较，此时需要比较n(n-1)/2次，
PHP简单选择排序算法实例
，
所以最终的时间复杂度是O(n^2)
go语言睡眠排序算法实例分析 篇8
这篇文章主要介绍了go语言睡眠排序算法,实例分析了睡眠排序算法的原理与实现技巧,需要的朋友可以参考下
本文实例讲述了go语言睡眠排序算法，分享给大家供大家参考。具体分析如下：
睡眠排序算法是一个天才程序员发明的，想法很简单，就是针对数组里的不同的数开多个线程，每个线程根据数的大小睡眠，自然睡的时间越长的，数越大，哈哈，搞笑吧，这种算法看起来很荒唐，但实际上很天才，它可以充分利用多核cpu进行计算。
代码如下:
package main
import (
“fmt”
“time”
)
func main {
tab := []int{1, 3, 0, 5}
ch := make(chan int)
for _, value := range tab {
go func(val int){
time.Sleep( int64(val)*10000000 )
fmt.Println(val)
ch <-val
}(value)
}
for _ = range tab {
<-ch
}
}
浅析排序算法 篇9
关键词：排序,冒泡算法,插入排序,快速排序,选择排序
1 引言
随着计算机的不断普及, 技术越来越成熟, 计算机硬件以及存储设备具有局限性, 提供计算机的效率成了程序员特别关注的一方向, 其中排序就是其中之一。如何能在最短时间, 在最节省内存的情况下, 使呈任意序列的数据元素, 在最快的时间得到从大到小或从小到大的序列, 是程序员一直研究的问题。
本文主要是简单的讲述一下排序的几种算法, 冒泡排序, 插入排序, 快速排序, 选择排序。
2 冒泡排序
冒泡排序, 是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的数列, 一次比较两个元素, 如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换, 也就是说该数列已经排序完成。
算法用C语言的实现如下:
3 插入排序
插入排序的思路简要的描述是:将序列的元素分作有序和无序两类, 然后在保持前一类有序的前提下, 通过迭代将后一类元素逐一插至前一类中的适当位置。
插入排序有直接插入排序, 折半插入排序, 2-路插入排序和希尔排序。这里仅给出直接插入排序的实现。
算法用C++语言的实现如下:
4 快速排序
快速排序的基本思想是, 通过一趟排序将待排记录分割成独立的两部分, 其中一部分记录关键字均比另一部分记录的关键字小, 则可分为对这两部分继续进行排序, 已达到整个序列有序。
算法用C语言的实现如下:
int Quick Sock (int*a, int Left, int Right) //算法的核心
5 选择排序
选择排序的基本思想是, 每一趟从待排序的数据元素中选出最小 (或最大) 的一个元素, 顺序放在已排好序的数列的最后, 直到全部待排序的数据元素排完。
算法用C语言的实现如下:
6 对比各种排序
参考文献
[1]严蔚敏, 吴伟民, 编著.数据结构 (C语言版) .清华大学出版社, 2011年5月.
[2]邓俊辉, 编著.数据结构 (C++语言版) (第二版) .清华大学出版社, 2011年10月.
[3]Mark Allen Weiss, 著.数据结构与算法分析——C语言描述.机械工业出版社, 2011年10月.
排序算法课程设计 篇10
研究了遗传算法在终端区跑道分配以及飞机排序中的应用,建立了多条跑道多架飞机排序的`数学模型,并进行了算例仿真分析.仿真结果表明,遗传算法与先到先服务排序相比较,适应度增加了80%,延时减小了40%,说明遗传算法的排序结果优于先到先服务的排序结果.
作 者：徐肖豪 姚源 作者单位：中国民航学院,空中交通管理学院,天津,300300 刊 名：交通运输工程学报 ISTIC PKU英文刊名：JOURNAL OF TRAFFIC AND TRANSPORTATION ENGINEERING 年，卷(期)：2004 4(3) 分类号：V355 关键词：空中交通管制 终端区 遗传算法 飞机排序 跑道分配★ Isomap算法在地震属性参数降维中的应用
★ 浅析电视教材及其在化学实验教学中的应用的论文
★ 基于熵权的属性识别模型在水库富营养化评价中的应用
★ 浅析项目教学法在化学检验技能培养中的应用
★ 网络环境下的化学多媒体技术的应用
★ 西门子列车网络控制系统在广州地铁中的应用
★ 微波扩频无线网络技术在教学中的应用网络知识
★ 浅谈纳米技术在化学工业中的应用
★ 地理信息系统在消防工程中的应用
操作系统课程设计-磁盘调度算法 篇11
磁盘调度算法。
建立相应的数据结构；
在屏幕上显示磁盘请求的服务状况；
将一批磁盘请求的情况存磁盘文件，以后可以读出并重放； 计算磁头移动的总距离及平均移动距离； 支持算法：FIFO、SSTF、SCAN、CSCAN;
2.设计目的:
调度磁盘I/O请求服务，采用好的方式能提高访问时间和带宽。本实验通过编程对磁盘调度算法的实现，加深对算法的理解，同时通过用C++语言编写程序实现这些算法，并在windos平台上实现，更好的掌握操作系统的原理以及实现方法，提高综合运用专业课知识的能力。
3.任务及要求
3.1 设计任务
编程实现下述磁盘调度算法，并求出每种算法的平均寻道长度：
1、先来先服务算法（FCFS）
2、最短寻道时间算法（SSTF）
3、扫描算法（SCAN）
4、循环扫描算法（CSCAN）
3.2 设计要求
对用户指定的磁盘调度请求序列，基于以上四种算法，实现各自的调度顺序并输出，同时计算出各种算法下的平均寻道长度。
4.算法及数据结构
4.1算法的总体思想
queue[n] 为请求调度序列，diskrode为磁盘磁道数，headstarts为正在调度的磁道
①先来先服务算法（FCFS）按queue[n]数组的顺序进行磁盘调度，将前一个调度磁道与下一个调度磁道的差值累加起来，得到总的寻道长度，再除以n得到平均寻道长度。
②最短寻道时间优先算法（SSTF）将queue[n]进行由小到大的排序，首先定位当前调度磁headstarts在queue[n]的位置，通过循环语句找出离起始磁头最短的位置。
③扫描算法（SCAN）
将queue[n]进行由小到大的排序，首先定位当前调度磁headstarts在queue[n]的位置，然后在此位置按给定的方向遍历queue[n]，当道端点（queue[0]或queue[n-1]）时，再在定位处反向遍历到另一端。当调度磁道不在queue端点时，总的寻道长度为为前一个磁道与后一个磁
道差值的累加，当到达端点且queue[n]未全调度时，总寻道长度加上端点值再加上下一个调度磁道的值，再按前面的算法进行，直到磁道全部都调度完毕，得到总的寻道长度，除以n得到平均寻道长度。
④循环扫描算法（CSCAN）将queue[n]进行由小到大的排序，首先定位当前调度磁headstarts在queue[n]的位置，然后在此位置按给定的方向遍历queue[n]，当道端点（queue[0]或queue[n-1]）时，反向到另一端点再以此方向进行遍历，直到queue[n]中所有都调度完。当调度磁道不在queue端点时，总的寻道长度为为前一个磁道与后一个磁道差值的累加，当到达端点且queue[n]未全调度时，总寻道长度加上端点值再加上磁盘磁道总长度，再加上下一个调度磁道的值，再按前面的算法进行，直到磁道全部都调度完毕，得到总的寻道长度，除以n得到平均寻道长度。
5、源代码：
#include 1、先来先服务算法（FCFS)**********”< cout<<“****** 2、最短寻道时间优先算法(SSTF)**********”< cout<<“****** 3、扫描算法(SCAN)**********”< cout<<“****** 4、循环扫描算法(CSCAN)**********”< cout<<“****** 5、退出 **********”< /*======================初始化序列=======================*/ void init(int queue[],int queue_copy[],int n){ int i;for(i=0;i //对当前正在执行的磁道号进行定位，返回磁道号小于当前磁道中最大的一个 int fix(int queue[], int n, int headstarts){ int i =0;while(i /* ====================以下是FCFS算法==================*/ void FCFS(int queue[],int n,int diskrode,int headstarts)//queue是请求调度序列，n为其个数，diskroad为磁盘磁道数，headstarts为正在调度的磁道 { cout<<“************以下为FCFS调度算法***********”< /*=====================SSTF算法====================*/ void SSTF(int queue[], int n, int diskrode, int headstarts){ int k=1;int l,r;int i,j,count=0;queue =bubble(queue,n);cout<<“************以下为SSTF调度算法***********”< -headstarts)){ cout< /*======================以下是SCAN算法====================*/ void SCAN(int queue[], int n, int diskrode, int headstarts){ int direction, i, fixi;cout<<“***********以下是SCAN调度算法*************”< /*======================以下是CSCAN算法====================*/ void CSCAN(int queue[],int n,int diskrode,int headstarts){ int direction,i,fixi;cout<<“***********以下是CSCAN调度算法*************”< void main(){ int n, i, diskrode, headstarts;//n表示调度磁盘请求序列queue的长度，diskrode表示磁盘磁道的个数，headstarts表示目前正在调度的磁道； cout<<“请输入磁盘的总磁道数:”< if(menux ==2)SSTF(queue,n,diskrode,headstarts); 二路插入排序是将插入区间分成大致等长的两段,选择性地插入到其中一段,平均插入长度可缩小为原来的一半左右。 1 二路插入排序算法在单链表上的实现 首先定义如下的链式结构: 算法思想描述:二路插入排序的一般过程是取某个数当基准,一般情况下取线性表或链表中的第一个元素为基准,对其他数扫描,若比基准小,插入到其前的有序区,否则插入到其后的有序区。在单链表中取链表的的第一个元素的数据域为基准,对链的其他元素扫描,若比基准小,插入到其前的有序链1中,否则插入到其后的有序链2中。最后将链1和链2链起来即可完成二路排序在单链表上的实现。具体算法如下: 2 比较 在线性表上的插入排序,共需要n-1次元素的插入,每次插入最少需要比较一次和移动元素两次,最差需比较元素i次和移动元素(i+1)/2次。所以插入排序最好情况下的时间复杂度是O(n),最差和平均情况下的时间复杂度是O(n2),辅助空间为O(1),算法一般比较稳定。 在顺序表上二路插入排序算法中,移动记录的次数约为n2/8,而在单链表上二路插入排序算法不需要移动只需要改变链的指针域,通过分析该算法的实现可看到排序算法实现的广泛性,不仅仅在顺序表上能实现,而且在链表上同样也能实现。链式结构上每个数据元素占用一个结点,而不会有多余的结点存在,所以数据所占的存储空间不会浪费。链式结构上的排序只改变链的指向,而不会改变数据元素所占结点的位置,即不会移动数据元素。 参考文献 [1]严蔚敏,吴伟民.数据结构[M].清华大学出版社,1997. [2]耿国华.数据结构(C语言版)[M].西安:西安电子科技大学出版社,2002. [3]Robert L.Kruse,Alexander J.Ryba.Data Structures and ProgramDesign in C++[M].Pearson Education,USA,2001. [4]傅清祥,王晓东.算法与数据结构[M].北京:电子工业出版社,1998. [5]Shell D L.A high-speed sorting procedure[J].Communic-ations of the ACM,1959. [6]任志国,蔡小龙,等.插入排序算法的双链表模拟[J].电脑编程与维护,2010,(3):8-9. [7]达文姣,任志国,等.链式结构上排序算法的研究[J].电脑编程与维护,2011,(3):1-2. [8]祁建宏,任志国,等.单链表中双插入排序算法研究[J].电脑编程与维护,2011,(2):26-27. [9]达文姣,任志国,等.静态链表上排序算法的研究[J].自动化与仪器仪表,2011,(2):80-81. 【排序算法课程设计】推荐阅读： 检测算法排序05-22 数组排序算法05-22 冒泡排序算法08-25 常用算法与排序面试05-21 排序均压算法09-05 最常用的排序算法总结07-29 循环排序大班数学课程教案设计09-10 按规律排序教案设计05-03 程序设计与算法语言课程设计题目05-07 《有趣的排序》优秀公开课教案设计07-01链式二路插入排序算法研究 篇12