快速排序（共8篇）
快速排序 篇1
0 引言
快速排序算法在所有的排序算法中是比较优秀的算法, 也是推荐的常用算法, 但它不完善, 即它是不稳定的排序算法。所谓排序算法的稳定性是指在待排序的记录序列中, 如果存在多个具有相同的关键字的记录, 若经过排序, 这些记录的相对次序保持不变, 即在原序列中, ri=rj, 且ri在rj之前, 而在排序后的序列中, ri仍在rj之前, 则称这种排序算法是稳定的, 否则称为不稳定的。在实际处理数据的过程中, 有时对排序的稳定性要求很高, 例如在处理类似有奖问卷问题时, 常根据问卷的成绩给部分人一定的奖品, 但有时相同成绩的人很多, 不可能都给奖品, 一般采取的是在成绩相同的情况下, 提交答案早的得奖品, 提交答卷晚的不得奖品, 这时就需要对成绩排序的算法是稳定的。
近年来, 不少学者提出各种改进的快速排序算法, 如三路基数快排[4]、高效快速排序算法[5]和超速快排[7]等, 都是增强了快速排序时间性能, 但对排序算法的稳定性基本上没有涉及。本文针对这一情况提出了一种稳定快速排序算法。
1 稳定快速排序算法设计
1.1 算法设计思想
经典的快速排序算法设计思想是通过一趟排序将待排记录分割成独立的二部分, 通过直接交换方式使其中一部分记录的关键字均比另一部分记录的关键字小, 然后再分别对这两部分的记录继续进行排序, 以达到整个序列有序。在把待排序的数据分割成两部分时, 需要把前后的数据直接进行交换, 这样的交换可能导致数据前后颠倒, 所以经典快速排序是不稳定的。要想使排序稳定, 需要改掉这种直接交换前后数据的办法, 采用其他方法处理。稳定快速排序算法就是这样一种改进算法。
稳定快速排序的设计思想如下:
(1) 通过一趟排序将要排序的数据划分成独立的两部分。
(2) 每部分各自再分成两小块, 使一小块所有数据都按原顺序排列且比另一小块按原顺序排列的所有数据都小 (或大) 。
(3) 把四块中两个小 (或大) 块按原顺序连接起来, 放在所有数据的前部, 把另外两个不小于 (或不大于) 块也按原顺序连接起来, 放在所有数据的后部。
(4) 然后再按此方法对形成的两部分数据分别进行稳定快速排序, 直到所有数据都是有序的。整个排序过程可以递归进行。
1.2 算法设计思路
本文以递增顺序排序为例进行说明。
(1) 增加与待排序数据数量相同的辅助存储空间如图1所示。
(2) 将待排序序列按经典算法的处理方法相似的方法分成二部分如图2所示深色部分和浅色部分, 同时把前面一部分数据进行如下处理, 所有小于middle值的元素按原顺序存放在原来存储区最前部D1区, 所有不小于middle值的元素按原顺序连续存放在辅助存储区最前部T1区;把后面一部分数据处理如下, 所有大于等于middle值的元素按原顺序存放在原来存储区最后部D4区, 所有小于middle值的元素按原顺序连续存放在辅助存储区最后部T3。
(3) 把前面一部分数据中不小于middle的数据 (T1区数据) 复制到后面一部分数据的最前部 (D3区) , 把后面一部分数据中小于middle的数据 (T3区数据) 复制到前面一部分数据的最后部 (D2区) 。一趟处理完成。
(4) 再递归地对第一部分和第二部分分别进行上述操作, 直至整个序列排序完成。
根据上面的算法设计思路可以知道, 当被排序的数据中任何数据相等时, 排在前面的数据永远排在前面, 所以此算法是稳定的。
1.3 算法描述
由于使用已知数据和未知数据不影响排序算法描述, 为了直观现以实际的数据为例对稳定快速排序算法进行描述, 假设待排序的关键码序列为Str1, 排序前增加同样存储空间的整型数组Str2, 如图3所示。
第一趟稳定快速排序过程:
(1) 选择str1中第一个数据34为middle, 作为数据分割依据。
(2) 从str1前面依次判断每个数是否小于middle, 34不满足小于middle条件, 结束判断。
(3) 从str1后面依次判断每个数是否大于或等于middle, 111满足条件, 34满足条件, 53满足条件, 21不满足条件, 结束判断。
(4) 把str1前面的34移到str2的前头, 把str1后面的21移到str2的后头, 结果如图4所示。
(5) 再回到str1前部继续判断21, 21满足小于middle的条件, 把21前移到原来34的位置, 继续判断53, 53不满足小于middle的条件, 判断结束。结果如图5所示。
(6) 再从str1后部继续判断, 123满足条件, 把123后移到原来21的位置, 78满足条件, 把78后移到原来123的位置, 8不满足条件, 判断结束。结果如图6所示。
(7) 把str1前部的53移到str2中34的后面, 把str1后部的8移到str2中21的前面。至此第一轮判断结束, 结果如图7所示。
(8) 最后把str2中前面的34、53顺序移到str1中78的前面, 把str2中前面的8、21顺序移到str1中21的后面, 结果如图8所示。到此整个第一趟稳定快速排序才真正结束。然后把分割的两部分再依次用上面方法完成整个稳定快速排序。
1.4 算法实现
下面的代码为用递归思想描述的稳定快速排序算法 (C语言实现) 。
2 稳定快速排序算法理论分析
本稳定快速排序算法是在原来的快速排序算法的基础上改进的, 算法理论与原快速排序的算法理论相似, 在此只对改进的地方进行分析。
2.1 算法稳定性
本稳定快速算法在进行数据分割的过程中, 把需要前后移动的数据不是直接交换, 而是先把它们按原顺序移出来保存起来, 被移走数据的位置用后面 (或前面) 的数据前移 (或后移) 填充, 等所有数据检查、移出和前后移完成后, 把保存起来要移动的数据分别移回到原来存储区前面所有数据的后面和后面所有数据的前面, 完成一次数据分割。然后把分割结果的前后两部分数据再按前述方法进行分割, 直到所有的数据都被分割成单个数据, 完成排序。确保相同的数据按原来的顺序存放即排序的稳定性。
2.2 算法空间复杂度
稳定快速排序算法与原来的快速排序算法相比, 在空间上多用了与原排序数据相同数据量的排序空间, 用来存放需要前后移动的数据, 它的空间复杂度还是O (N) 。
2.3 算法时间复杂度
稳定快速排序算法与经典快速排序算法在处理方式方面的主要不同在于对需要移动的数据处理方式有所差异, 算法时间复杂度不同就是由此引起的。
经典快速排序算法若需要数据移动, 通过前后两数据交换完成, 需要下面的处理过程:
稳定快速排序算法若需要数据移动, 先把数据顺序存放到临时存储区:
当所有数据检查处理完后, 再把临时存储区中所有数据顺序移回原数据区:
综上所述, 改进算法与经典算法相比每次移动数据只是多了一个赋值语句, 其他语句基本相同, 因此对n个排序数排序时最坏情况需移动n个数, 假定花费时间为Tf (n) , 对n个排序数进行一次划分的时间代价为C (n) , 则:
稳定快速排序的总时间代价为:
故, 稳定快速排序的算法没有引起时间性能大的变化, 算法时间复杂度仍为O (Nlog N) 。
3 实验结果与结论
3.1 稳定性测试
为了验证稳定快速算法, 随机组合了大量数据进行了实验, 如使用如图9表中十条记录的数据用本算法进行了简单的测试, 根据字段1按递增排序, 排序后记录数据的输出效果如图10所示。
从图中的结果可以看出, 根据字段1排序后, 字段1中相同的数据的先后顺序没有发生改变, 字段2为0的排第一位, 字段2为1的排序第二位, 字段2为4的排第五位, 因此算法是稳定的。
3.2 时间复杂度测试
在Windows XP的VC 6.0平台上, 对大量数据进行多次测试 (数据由随机函数Rand () 产生) 。
1) 随机产生50 000个整型数据用各种排序方法排序所用时间基本如图11所示。由图11可知, 稳定快速排序有很好的性能表现, 速度与原快速排序基本上相同, 与稳定排序的归并排序也基本相同。
2) 随机产生50 000个整型数据, 然后用求余法得到50 000个1位整数、50 000个2位整数、50 000个3位整数、50 000个4位整数和50 000个5位以上整数用稳定快速排序法进行排序所用时间基本如图12所示。由图12可知, 当数据的位数少时, 重复的数据多, 需要移动的数据多, 排序效率较慢, 3位以上数据的排序效率基本相同, 达到了最好。
4 结语
稳定快速排序算法是在原快速排序算法的基础上, 对算法的稳定性进行的完善, 理论和实践证明, 使用稳定快速排序算法, 可以确保排序是稳定的, 且本算法的时间复杂度没有大的改变, 只是多用了与排序数据数量相同的存储空间。
摘要：快速排序算法与其他算法相比是相当有效的排序算法, 但此算法并不完善, 它是不稳定的。为此, 对快速排序算法进行改进, 在每次对数据分割时, 对需要移动的数据先分别顺序拷出并保存, 分割结束前再按要求分别顺序拷入, 使得新排序算法是稳定算法。理论分析和实验数据表明, 在任何情况下, 稳定快速排序算法都是稳定的, 并且其他性能不比快速排序算法和归并算法差。
关键词：排序算法,算法稳定性,算法时间复杂度,算法空间复杂度,稳定快速排序
参考文献
[1]庞建雄.排序算法稳定性的深入讨论[J].桂林电子工业学院学报, 1996, 16 (1) :1-4.
[2]汪沁, 奚李峰.数据结构[M].北京:清华大学出版社, 2009.
[3]秦锋.数据结构[M].合肥:中国科学技术大学出版社, 2007.
[4]王善坤, 陶祯蓉.一种三路划分快速排序的改进算法[J].计算机应用研究, 2011, 29 (7) :2513-2516.
[5]汤亚玲, 秦锋.高效快速排序算法研究[J].计算机工程, 2010, 36 (7) :77-78.
[6]Cantone D, Cincotti G.Quic kHeapsort:An Efficient Mix of Classical Sorting Algorithms[J].The Oretical Computer Science, 2002, 285:25-42.
[7]周建钦.超快速排序[J].计算机工程与应用, 2006, 42 (29) :41-43.
[8]郭晶旭.基于快速排序的改进算法[J].计算机科学, 2006, 39 (4A) :343-344.
快速排序 篇2
这篇文章主要介绍了Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法,以实例形式详细分析了几种常见的排序技巧与实现方法,非常具有实用价值,需要的朋友可以参考下
本文实例讲述了Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法，分享给大家供大家参考。具体分析如下：
算法是程序的灵魂，而排序算法则是一种最基本的算法。排序算法有许多种，这里介绍4中排序算法：冒泡排序，选择排序，快速排序和插入排序，以从小到大为例。
一、冒泡排序
冒泡排序的原理是，对给定的数组进行多次遍历，每次均比较相邻的两个数，如果前一个比后一个大，则交换这两个数。经过第一次遍历之后，最大的数就在最右侧了；第二次遍历之后，第二大的数就在右数第二个位置了；以此类推。
代码如下:
//冒泡排序（排序10000个随机整数，用时约145ms）
func bubbleSort(nums []int) {
for i := 0; i < len(nums); i++ {
for j := 1; j < len(nums)-i; j++ {
if nums[j] < nums[j-1] {
//交换
nums[j], nums[j-1] = nums[j-1], nums[j]
}
}
}
}
二、选择排序
选择排序的原理是，对给定的数组进行多次遍历，每次均找出最大的一个值的索引。
代码如下:
//选择排序（排序10000个随机整数，用时约45ms）
func selectSort(nums []int) {
length := len(nums)
for i := 0; i < length; i++ {
maxIndex := 0
//寻找最大的一个数，保存索引值
for j := 1; j < length-i; j++ {
if nums[j] > nums[maxIndex] {
maxIndex = j
}
}
nums[length-i-1], nums[maxIndex] = nums[maxIndex], nums[length-i-1]
}
}
三、快速排序
快速排序的原理是，首先找到一个数pivot把数组‘平均‘分成两组，使其中一组的所有数字均大于另一组中的数字，此时pivot在数组中的位置就是它正确的位置。然后，对这两组数组再次进行这种操作。
代码如下:
//快速排序（排序10000个随机整数，用时约0.9ms）
func quickSort(nums []int) {
recursionSort(nums, 0, len(nums)-1)
}
func recursionSort(nums []int, left int, right int) {
if left < right {
pivot := partition(nums, left, right)
recursionSort(nums, left, pivot-1)
recursionSort(nums, pivot+1, right)
}
}
func partition(nums []int, left int, right int) int {
for left < right {
for left < right && nums[left] <= nums[right] {
right--
}
if left < right {
nums[left], nums[right] = nums[right], nums[left]
left++
}
for left < right && nums[left] <= nums[right] {
left++
}
if left < right {
nums[left], nums[right] = nums[right], nums[left]
right--
}
}
return left
}
四、插入排序
插入排序的原理是，从第二个数开始向右侧遍历，每次均把该位置的元素移动至左侧，放在放在一个正确的位置（比左侧大，比右侧小），
代码如下:
//插入排序（排序10000个整数，用时约30ms）
func insertSort(nums []int) {
for i := 1; i < len(nums); i++ {
if nums[i] < nums[i-1] {
j := i - 1
temp := nums[i]
for j >= 0 && nums[j] > temp {
nums[j+1] = nums[j]
j--
}
nums[j+1] = temp
}
}
}
通过多次测试可以发现，快速排序是效率最高的。
任意类型的分类数据的快速排序 篇3
在实际应用中,经常遇到数据量很大,但是种类却很少的数据排序问题。例如在工资表中常常有关于职工的性别或年龄的排序,往往涉及的数据量非常大,但是数据的种类很少,性别的排序其实就只涉及“男”和“女”的排序,至于年龄排序,无非是0到120之间的大量的分类数据的排序。尤其针对于材料属性方面的数据排序更是如此,数据量非常大,但是数据的种类却很少。如果关键字的值为任意数值型整数或字符串,使用基数排序比较快,但如果涉及到浮点数,那么基数排序就不适合了。快速排序算法采用分治原则,算法结构简单,平均性能较佳为O(nlog2n),因而被广泛使用。但快速排序算法,在数据部分相等或有序时,时间复杂度最坏为O(n2)。本文提出一种新的排序算法,具有快速排序算法的简洁性,但不使用递归算法,时间复杂度为O(n),空间复杂度为O(1)。因此对于分类数据的排序,尤其是数据量大的场合,本文所提出的算法与其它方法的排序相比效率高。
1 改进的快速排序算法
1.1 传统的快速排序
快速排序是交换排序的一种,快速排序也叫做分区排序。这是一种平均性能非常好的排序方法,其基本思想是取待排序对象序列中的某个对象(例如取第一个对象)作为枢轴(或支点),然后按下列原则重新排列其余元素:按照该对象的关键码大小,将整个对象序列划分为左右两个子序列,左侧子序列中所有对象的关键码都小于或等于枢轴对象的关键码,右侧子序列中所有对象的关键码都大于枢轴对象的关键码,枢轴对象则排在这两个子序列中间(这也是该对象最终应安放的位置),这个过程称作一趟快速排序。一趟排序结束时,枢轴数据放到了合适的位置,整个序列被划分为两个子序列。然后再通过递归的方法,分别对这两个序列继续进行快速排序,直到所有的记录都排在适当的位置为止。对于快速排序算法来说,枢轴值的选择非常重要。
如果枢轴值选择的不好,快速排序的运行时间将会是O(n2)级。当初始记录序列中有大量的关键字值相等时,快速排序将蜕化为冒泡排序,同时其时间复杂度变为O(n2)。
1.2 改进的快速排序算法的描述
如果数据量非常大,但是数据的种类却很少,此时使用快速排序进行排序,效率会非常低。为了提高效率,我们将关键码中最小数作为枢轴值,并且统计与其相等的关键码的个数,然后进行一趟划分。由于具有大量的相同值,因此需要将关键码与枢轴值一致的数据都放到合适的位置。快速排序算法中的分割算法,只能将一个枢轴放到合适位置,这也是对于分类数据排序时,快速排序速度慢的主要原因。基于以上的分析,我们需要改变快速排序中的分割算法。
设置如下的数据结构:
改进的快速排序的算法思想是:
(1)求list数组中的关键码最小的值Min及其下标suf,并统计最小值的个数MinNum;
(2)将最小值放在分割位置即low;
(3)确定分割范围:low,high=low+MinNum;
(4)进行一趟分割,将数值相同的最小值都排列在合适位置;
(5)对其余的数值作如上的处理,直至所有的数均有序。
这个改进的快速排序算法适合分类数据,尤其是数据量大的场合,效果会更好。此算法中不需要使用递归,因此其时间复杂度和空间复杂度都优先于传统的快速排序。
1.3 改进的快速排序算法的源程序
具体的算法如下所示:
经过一趟分割,我们能将与枢轴值相同的所有的数据排到合适的位置,下次再取数据只需从low+Min Num(low为枢轴值的位置,MinNum为关键字与枢轴值相同的元素个数)位置开始即可,这样避免了递归算法,提高了算法的效率。
1.4 算法的时间复杂度和空间复杂度
假设待排的序列为{list[low],list[low+1],…,list[high]},在以上改进的快速排序算法中,由于每次都挑选出关键字值最小的元素,然后将此最小值作为枢轴(支点),一趟快速排序之后,关键字值与枢轴相同的所有记录都安置到{list[low],list[low+1],…,list[low+MinNum]}区间。由此序列从low+MinNum位置作分界线,low+Min Num之前的元素已排好序,只需对low+Min Num之后的元素排序即可。可以看出以上算法的时间复杂度与数据的分类个数有关,假设数据中需要排序的关键字有k种类型,那么算法的时间复杂度为O(kn)。当k<
另一方面,该算法用到三个辅助变量,因此空间复杂度为O(1)。与其它的算法相比,本文所介绍的算法效率比较高。
2 与传统快速排序算法的性能对比实验
在各种内部排序中,当数据量很大而且有很多关键码相等的数据排序时,相比之下直接插入算法所用的时间较少,因此本文选择了三个算法进行实验,即直接插入排序、快速排序和改进的快速排序。用Visual C++6.0编程,由RAND函数随机产生0-100之间的数据(包括浮点数),在Intel(R)Core(TM)2 Duo CPU 76500/2.10Ghz/Windows Vistap平台上运行,结果见表1:
当数据量达到百万以上时,时间差距会拉得更大。直接插入算法需要的时间太长了,无法统计。下表中比较了快速排序和改进的快速排序的时间,结果见表2:
从上表中可以看出,基于新的快速排序的算法明显优于传统的快速排序,特别是随着数据量增大,快速排序会出现“over flow”栈溢出的信息,从而导致无法排序,而本文所介绍的算法由于不使用递归算法,因而数据无需压栈,当出现大量数据时,可以充分体现其优越性。
实验表明,当数据的种类k<<总数量n时,新算法的效率明显的高于其它算法。
3 结束语
本文所介绍的算法特别适合于任意类型的分类数据的排序,尤其是数据量大的场合。事实上,在实际应用中,我们很多时候遇到这样的情况,数据的种类不多,但数据的个数却庞大,即数据的种类k<<总数量n,这种情况如果使用本算法,其效率会远远的优于其它排序。该算法克服了快速排序的缺点,不使用递归,空间复杂度为O(1),时间复杂度为O(n),并且是一种稳定的排序,具有很高的实用价值。
摘要：快速排序在数据部分相等或有序时,时间复杂度最坏为O(n2)。针对于任意类型的分类数据的排序,文章在快速排序的基础上,提出一种新的排序算法,具有快速排序算法的简洁性,但是不使用递归算法,时间复杂度为O(n),空间复杂度为O(1)。通过理论分析和实验表明,该算法的性能明显优于其它排序算法,特别适合于数据量大的场合。
关键词：排序,算法,快速排序,时间复杂度
参考文献
[1]Dongarra J.The Top 10 Algorithms[J].[IEEE]Computing in Science&Engineering,2000,2(1):22~23.
[2]Hoare C A R.QuickSort[J].The Computer,1962,15(1):10~15.
[3]曹新谱.算法设计与分析[M].长沙:湖南科学技术出版社,1984.
[4]王向阳,杨红颖.分段快速排序法的改进[J].小型微型计算机系统,2001,22(11):1382~1385.
[5]江华,谭新星.一种非比较分段排序算法的研究[J].计算机应用与软件,2003,20(4):46~48.
快速排序 篇4
Win10系统中文件夹的顺序是固定的，如果用户不作出修改的动作，那么他们就是按照访问时间来排序，那么怎么调整Win10快速访问中文件夹顺序呢？
调整步骤
1、按住鼠标左键或手指长按，拖动你想要改变位置的文件夹，例如Windows.pro文件夹，虽然它已经是固定在“快速访问”中了，但你拖动时依然会显示“固定到快速访问”，
如图：
2、不用管它，拖动到想要改变顺序的位置，例如“下载”文件夹的上面，松开鼠标左键或抬起手指（触控操作），这时你会发现，Windows.pro文件夹已经跑到“下载”文件夹前面了，不光是左侧导航窗格中的“快速访问”排序，而且右侧窗口中的“常用文件夹”排序也同时发生变化了。如图：
快速排序 篇5
由于图像采集、传输等过程中产生了各种噪声,图像的质量变差。要消除这些图像噪声,首先需要对图像进行预处理,为后续图像处理、运动目标检测、运动目标跟踪等奠定良好的基础。但是传统硬件处理速度慢,难以满足系统的实时性要求,采用大规模可编程逻辑器件FPGA,可实现复杂的数字逻辑系统设计,在实时性处理要求高的场合具有独特优势。
统计排序滤波(OSF)在图像预处理过程中一种非线性空间滤波方式,既可以消除随机噪声和脉冲干扰,又可以很大程度的保留图像的边缘信息,在图像平滑和数据分析处理等多个领域中得到广泛的应用。统计排序滤波中最常见的例子是中值滤波,另外常用的还有最大值滤波和最小值滤波等。
2图像统计排序滤波原理
2.1传统的统计排序滤波算法
统计排序滤波器响应基于图像滤波器包围的图像区域中像素的排序,然后用统计排序结果决定的值代替中心像素的值。以统计排序滤波器中最常见的中值滤波为例,它是将某像素邻域内的像素灰度从大到小排序的中间值代替该像素的值。传统的中值滤波定义如下:
其中,G(x,y) 为输出像素灰度值,F(s,t)为邻域内像素的灰度值。传统的中值滤波算法需要对邻域内的所有像素进行排序,跟据排序结果输出相应灰度值。例如,像素值为34的5×5邻域内有一系列像素值(10,11,12,13,14,20,21,22,23,24,31,30,34,33,32,40,41, 42,43,44,50,51,52,53,54),对这些值排序后为(10,11,12,13,14, 20,21,22,23,24,30,31,32,33,34,40,41,42,43,44,50,51,52,53, 54),那么其中值就是32,中值滤波后就用32代替原像素值34。
传统的统计排序滤波多采用软件方式通过冒泡法实现数据排序,时间复杂度为n(n-1)/2,算法执行过程需要大量的处理时间,很难满足实时性要求。
2.2快速排序滤波算法
冒泡排序是以两两之间的串行比较为基础,进行数据排序。本方案也是以两两之间的比较为基础,但采用同时并行比较得出排序结果的方式进行排序。这种数据同时比较的排序方法可称为并行全比较排序法。
进行全比较排序时,待排序的数据,每两个数进行比较后,都会得到一个比较结果。可将比较的结果定义输出为0或1。然后对比较结果进行相加,即可得到该数在序列中的排序值。由于所有数的两两之间的比较都在硬件内同时进行,因此只需一个FPGA时钟的时间即可得到两个相邻数据的比较结果,再加上各数比较结果的和的计算时间和排序的处理时间,即4个FPGA时钟实现了数字序列的排序。
3统计排序滤波器设计实现
图像快速统计排序滤波器主要有2部分组成:滤波窗口生成模块、统计算法模块。
3.1滤波窗口生成模块设计
对图像的中值滤波首先要生成5×5的滤波窗口,为了使5×5模板中的5行5列共25个数据能够在同一时刻同时输出,便于后续算法进行流水线处理。5×5窗口模板由五组寄存器和四个FIFO组成,滤波窗口生成模块实现了数据的串入并出,在FPGA中定义五组25个寄存器,寄存器中存储的数据分别为dat11、dat12、dat13、dat14、 dat15,dat21、dat22、dat23、dat24、dat25,dat31、dat32、dat33、dat34、 dat35,dat41、dat42、dat43、dat44、dat 45,dat 51、dat52、dat53、 dat54、dat55。其硬件实现结构如图1所示:在进行统计滤波时,先从数据端口读入四行图像数据保存在寄存器和FIFO中,在第五行数据到来后,从第五个数据开始滤波,从数据端口不断读入数据,第一个作统计滤波的像素数据为第三行的第三个数据,此时图像输入端到来的数据为第五行的第五个数据。
3.2统计滤波算法模块设计
本文采用5×5滤波窗口,一次采集5×5邻域内25个数。对这25个数进行并行排序处理,并行排序采用基于FPGA的全比较排序方式,在4个时钟周期内即可实现排序结果,其中包括三个过程,第一个时钟周期内,实现所有数据的并行比较结果,第二个周期,实现数据排序;第三个周期,实现滤波算法。在并行排序处理结束后,根据得出排序结果,把所需要的值输出。若为中值滤波,则把25个数的排序第13的值输出;若为最大值滤波,则把排序第1的值输出。如图2所示。
4基于FPGA实现及实际效果
排序算法在FPGA内进行,采用ALTERA公司Cyclone III系列FPGA,内部时钟周期为20ns。
在QUARTUS II平台环境下,原理图设计文件作为主文件,内部模块采用Verilog语言设计,内部主要模块包括滤波窗口生成模块和统计滤波算法模块。
工程编译完成后,对工程文件进行仿真,观察仿真结果,与实际值对照,确认算法的正确性。图3为设计仿真效果图。
图3中,in13为某点的像素值,in0~in24(包括本像素值)为该点邻域内的25个数据,采用的时钟频率50M,时钟延时约三个周期后, 输出滤波结果,out2和outm分别为该像素5×5邻域内的第三大值和中值。
图4为云的原始图像和在FPGA内经过5×5中值滤波处理后的图像,前一幅为原始图像,后一幅为处理后的图像。
5结语
本文主要介绍了图像统计滤波排序算法,先介绍了传统的统计滤波,在此基础上提出基于FPGA实现的图像统计排序滤波算法,采用并行全比较方式,对于5×5的滤波窗口,进行了仿真验证,在4个时钟周期即求出统计排序要求值,采用流水线方式,满足图像统计排序滤波处理的实时性要求。
参考文献
[1]侯发柱,彭楚武.图像中值滤波算法及其FPGA的实现.嵌入式与SOC,2011(1),69-71.
快速排序 篇6
关键词：多核处理器,OpenMP,并行算法,快速排序
1. 引言
现代计算机的多核、众核技术正在快速发展,如何利用多核实现并行计算提高计算效率,已成为高性能计算技术领域研究的热点。对于配置了多核CPU的共享存储计算机系统,目前Open MP已是一种共享存储并行编程模型的工业标准,具有良好的可编程性,能够显著提高编程和计算效率。
本文分析Open MP的并行编程模型特点,应用Open MP设计和实现一种快速排序并行算法,并进行Open MP并行程序与串行程序性能比较,验证本文所采用的Open MP并行编程方法的有效性。
2. Open MP并行编程简介
计算机多核技术的发展带动了并行编程方法的研究和发展,其中以Open MP为代表的并行编程方法是多核计算机并行编程的主要方式。Open MP具有简单、移植性好和可扩展等优点,由一组与平台无关的编译指导命令(directives)、环境变量(environment variables)和运行库(runtime library)组成。Open MP的缩主语言目前支持Fortran、C和C++语言,当前最新版本为3.0。
Open MP是通过编译器对程序中编译指导语句的翻译来实现并行计算的。例如在C/C++语言中,用语句#pragma omp parallel来标识一段并行执行的程序块。Open MP编译指导语句可以根据需要包含多个子句项,在没有其它约束的条件下,子项可以无序和任意选择。例如#pragma omp parallel for[子句…]是使用最为频繁的编译指导语句,并且可以搭配使用private,firstprivate,if,lastprivate,reduction,schedule等多种子句。
Open MP并行编程模式主要有两种:(1)fork-join模型,常用于开发计算任务中内在的循环级并行性。其中fork负责建立多线程,启动多个线程完成并行计算量的任务;join使各线程汇集于主线程,由主线程完成串行计算量的任务,这种模式较为简单直观。(2)编写类似SPMD形式的程序,利用Open MP的库函数omp_get_num_threads()和omp_get_thread_num()可以进行任务划分。本文主要采用第二种方式。
3. Open MP快速排序并行算法
3.1 问题描述
快速排序(quick-sort)算法是对冒泡排序算法的一种改进,由C.A.R.Hoare在1962年提出。它的基本思想是:通过一次排序将数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按照此方法对这两部分数据分别进行快速排序,整个排序过程可以递归并行处理,以此达到整个数据变成有序序列。
3.2 串行算法描述
设要排序的数组为A[0]……A[N-1],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它之前,所有比它大的数放到它之后,这个过程称为一次排序。一次排序的算法描述如下:
(1)设有两个变量I、J,排序开始的时候:I=0,J=N-1;
(2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];
(3)从J开始向前搜索,即由后开始向前搜索(J=J-1),找到第一个小于key的值A[J],并与A[I]交换;
(4)从I开始向后搜索,即由前向后搜索(I=I+1),找到第一个大于key的A[I],与A[J]交换;
(5)重复第3、4步,直到I=J;
(6)将数据A[0]放置到I处;
排序的整个算法采用递归调用一次排序的过程。设一次排序的函数为qkpass(),则递归形式快速排序算法如下:
3.3 快速排序并行算法的设计与实现
通过对传统快速排序串行算法并行化,可以形成快速排序Open MP并行算法。首先分析计算问题的数据依赖关系,挖掘其内在并行性,然后进行数据分割,创建N个线程,为每个线程分配一份分割后的数据,各线程分别对各自的数据进行排序后,再利用归并排序算法进行排序。具体过程如图1所示。
由图1所示的Open MP快速排序并行算法步骤如下:
(1)设随机产生的待排序数组为p,个数为count;
(2)由Open MP编译指导语句控制产生并行执行代码区段;
(3)各线程获取自己的线程号iam和总线程数量no;
(4)各线程调用串行快速排序算法:将p,iam*count/no,(iam+1)*count/no作为函数参数,并行地执行快速排序函数quicksort();
(5)调用merge()函数合并排序各个线程已经产生的部分有序数据。
以上代码中“#”开头所在行是编译指导语句。#pragma omp parallel表示下面一段代码并行执行,shared(A,count,no)表示A,count,no为所有线程共享变量,即每个线程都可以访问的变量,主要用于共享存储和数据交换。private(p)表示p为每个线程中私有变量,每个线程自身可以访问的变量,不能用于变量共享。
3.4 实验结果分析
实验环境和条件在拥有双CPU的4核处理器Intel E5405(主频2.0GHz)上进行实验)。
实验数据是模拟产生的100万个、500万个和2000万个随机整数,对三种规模的数据分别进行串行快速排序,计算时间分别为0.219秒,1.312秒,7.234秒。然后在分别设定2核、4核和8核的Open MP并行环境上进行同样三种数据规模的并行排序,对比结果表明,Open MP并行算法比串行算法效率有明显提高。两种算法计算效率对比如表1所示。
从表1可知,并行计算时间随处理器核的增加而减少。由表中数据生成的并行加速比(Speedup)图和并行效率(Efficiency)图分别如图2和图3所示。
由图2和图3可以得知,在多核CPU中,Open MP多线程并行加速比随处理器核个数的增加而增加,规模越大,加速比增加得越快。并行效率随处理器核的增加而降低,但若同时适当增大规模,则可基本保持并行效率不降低,因此本该算法具有良好的可扩展性。
5. 结束语
随着多核、众核时代的到来,多核软件编程方法将成为主流技术。从本文设计的Open MP快速排序并行算法可以看出,Open MP提供了一种简单的、可移植的方法来实现串行代码到并行代码的转换,以多线程方式并行运行程序,从而提高了处理器的利用效率。Open MP具有良好的可编程性,开发人员不需要考虑线程的通信和控制等问题,只需要编写适当的编译指导语句即可实现并行计算,使得开发人员可以致力于研究并行计算中的算法设计和负载均衡等核心问题,以提高并行效率。
参考文献
[1]Michael J.Quinn.MPI与OpenMP并行程序设计[M].陈文光,武永卫等译.北京:清华大学出版社,2004.
[2]OpenMP标准[EB/OL].http://www.openmp.org.2010.
[3]罗省贤,何大可.基于MPI的网络并行计算环境与应用[M].成都:西南交通大学出版社,2001.12.
[4]郭晶旭.基于快速排序的改进算法[J].计算机科学,2009,36(4A):343-344.
[5]陈国良.并行算法实践[M].北京:高等教育出版社,2004.
快速排序 篇7
本节课是“简单排序”的第5个课时, 是一堂信息学研讨课, 主要的知识点是快速排序。学生已经对计数、插入、选择和冒泡排序进行了学习, 初步掌握了简单排序的算法, 并能应用于实际问题。
我先通过一道竞赛真题 (NOIP2007提高组的第1题统计数字) 引入, 让学生结合已学的排序算法思考求解。有的学生说直接用已学的选择或插入排序算法来做;有的学生在分析题目时便发现题目给出的数据最大可达到200000, 而之前学的排序算法的时间复杂度是O (n^2) , 简单一算发现超时。这个环节本意是让学生发现数据范围的问题, 从而寻求效率更高的排序算法, 但是也发现了一部分学生不能认真审题, 盲目做题 (审题, 即观察问题, 这是一切有效思考的基础) 。由此, 我自然引出本课的主题——快速排序, 它是一种时间复杂度O (nlog2n) 的排序算法, 然后先学习快速排序“是什么”, 在此基础上寻找快速排序“为什么快速”的答案。
首先, 我给出了快速排序的思想, 让学生有一个总体的把握;接着阐述了一次快速排序的算法, 使学生了解具体的做法和步骤。这时, 学生产生了疑问:这样就能实现“排序”吗?于是, 我用一组数据在课件上动态模拟 (如图1、图2) , 展现快速排序的一次划分过程, 学生对算法的开始、关键步骤、结束条件等产生直观的认识。
这时就继续讲解快速排序的具体程序吗?学生能根据程序自己揣摩消化吗?在备课过程中, 我发现了一些问题, 觉得可以作为突破口引导学生“重新发现”和深入理解快速排序。内涵理解了, 具体程序是水到渠成的 (在备课过程中, 教师要以学习者的角色发现问题提出疑问, 不能人云亦云, 自己探索才能引导学生探索) 。
我预设了两个课堂问题: (1) 基准元素A[3]已放在目标位置, 应该以A[3]为基准将数据分为A[1]～A[2], A[4]～A[8]两部分吗? (2) I和J指针最后是由I<J直接变化为I>J, 你能举出最后由I<J变化为I=J的例子吗?让学生进行认真思考, 动手模拟, 相互讨论, 发现真相。第一个问题需要先判断真伪, 再给出自己的解释;第二个问题不需要判断, 是找不同情况的例子, 都关系到算法的核心设计。有些学生能很快给出不能或能的答案, 根本没有深入思考, 这说明稳定的思考能力是需要训练的;个别学生则经过演算、讨论, 给出自己的见解, 并举出反例, 这是科学的研究态度, 也说明学生已能初步运用快速排序算法模拟解决问题。 (这一过程是很关键的, 目的是让学生自我建构快速排序的模型, 而不是被动接受前人的研究成果, 使学生懂得有质疑才有发现和创新, 培养学生的自主探究和交流协作能力)
在学生思考、讨论的基础上, 我通过一个例子具体演示这两个问题的解决过程, 并与学生共同得出结论: (1) 基准元素最后的位置是不确定的, 未必放到目标位置, 因此划分中必须将基准元素包括在内。 (2) I=J时数据已完成一次划分, 但为了方便调用子序列继续快排, 仍多做一次, 统一为I>J时退出。接着, 我进一步提出疑问:在什么情况下基准元素放在目标位置, 且不参与下次划分?这是上述第一个问题的后续问题, 同样需要找例子证明自己的观点, 有助于学生思维的深入发展。大多数学生能较快地找出反例, 并模拟出全过程。 (课堂中问题的提出要具有连贯性和逻辑性, 不能泛泛而问, 要从探究的知识内部找问题, 关注学生认知能力的发展)
经过上述多个环节的思考、质疑和讨论, 这里水到渠成地给出快速排序算法的程序实现 (当然也可以尝试让学生自己先写, 再给出完整程序, 可能效果更好, 因课堂时间问题未这样操作) , 学生都能够较快地理解和掌握程序的书写, 而不是死记硬背式的, 并顺势编程解决了例题。大部分学生完成例题的求解后, 我继续提出疑问:基准元素取法不同, 对算法效率是否有影响?从而引出对快速排序算法效率的分析, 这是本节课的一个难点问题。有学生认为取中间数和取其他数效率一样, 有学生认为可能会有影响, 但是找不到合适的方式进行表达和研究。这时教师给出提示:还是根据实际例子来分析, 并以“1, 2, 3, 4, 5”这样一组简单的数据为例, 让学生画图思考分析 (如图3、图4) 。
以中间数3为基准, 要做几次划分, 交换多少次……
以开头的1为基准, 要做几次划分, 交换多少次……
但以中间数为基准元素就一定是最好的吗?学生A马上说:待排序的数不是按照顺序给出就不行了。此时, 教师正好提出可以有效提高快速排序的平均性能的做法——随机选取基准数, 并顺便介绍一下随机化算法 (要善于启发学生, 拓展学生的视野) 。以此为突破口, 师生共同对快速排序算法的最好情况、最坏情况、平均性能、空间复杂度、稳定性等进行了分析。在分析快速排序算法的不稳定性时, 我提出疑问:如果有的题目必须要用快排, 但是题目中要求稳定性, 如何针对题目对快排进行稳定性改造呢?并给出待解决的竞赛真题“分数线划定”让学生思考解决。 (学生在前面已学过选择排序的稳定性改造, 这里旨在锻炼学生举一反三的能力)
最后给出快速排序算法的一个应用:第k小数。即对快速排序算法进行局部改造, 创造性地解决问题。这里我先让学生思考、讨论, 然后给出了一些提示:直接先快排再按照顺序找第k小数是最直接的做法, 但是如何在快排原始算法中加入第k小数的判断?是否可以加入一个参数?这样自然引导学生实现应用。 (所学知识的应用核心, 它是在简单的模仿、理解和使用的基础进行创造性实验, 旨在培养学生创新思维能力)
快速排序 篇8
所谓遗传算法收敛的复杂条件,是指约束条件苛刻、可行解的可行区域狭窄的条件。降低发动机颤振故障发生的几率,对发动机压气机转子的制造、安装作出一系列的限制措施是必要的。其中,最重要的两个问题是如何控制叶片静质量矩和叶片固有频率。除了在制造时采取措施以外,在安装时降低叶片静质量矩和保证转子叶片具有合格的固有频率也是必不可少的。这就需要对叶片安装施加必要的约束条件。在复杂条件下,人工叶片排序效率很低。
利用计算机求解此类问题时,叶片排序问题被看作是一个组合优化问题。采用常规的组合优化求解叶片排序问题,算法复杂,对于某些“恶劣”的数据可能求不出正确的排序结果。遗传算法在求解组合优化问题上具有很大的优势,但是当叶片排序条件较为复杂时,收敛速度慢、甚至不能求出优化排序结果;适应度函数设计也较为困难。为解决这个问题,本文利用改进遗传算法,在此基础上进行了适应度函数设计,并采用植入种子染色体导引法和内外交换法进行排序,所得结果正确,收敛速度快。
1 叶片排序约束条件
某航空设备制造厂根据实际工作需要提出了下述叶片安装条件:
1)整级中的每个叶片与相邻叶片应具有频率差,且各叶片频率应为一大一小锯齿型分布,不允许连续增大或减小。即为“错频”排列。
2)在整级叶片中,其中三对叶片1～2、8～9、16～17的频率差应不小于11Hz,且应比其它的相邻叶片对的频率差高出不小于2Hz。允许这三对叶片的频率差比这三对中的任一叶片与相邻叶片的频率差高出不小于2Hz。
3)整级叶片中,相邻的4个叶片之间的三个频率差不得完全相同。
4)相邻叶片之间频率差应不小于6Hz,允许在互不相邻的三处,与相邻叶片频率之差不小于4Hz。
5)整级叶片的最大频率与最小频率之差应不小于14Hz。
6)整级叶片中的每六分之一位置(即1～4号、5～8号、9～12号、13～16号、17～20号、21～24号)上的叶片静质量矩的和之差应当不大于138g·cm,相邻象限叶片静质量矩的和之差应当不大于115g·cm。
7)压缩机全部叶片共分为3级,每级叶片都必须符合上述条件。为了生产率,单级叶片所提供的备选叶片数量不得大于26枚。程序运行时,一次最多可以输入100枚备选叶片,至少输出4组叶片数据。
8)非可行解可行化。如果叶片数据确实“恶劣”,有一组输出数据不是可行解。则应给出最佳备选叶片的频率和静质量矩范围(也就是如果有一组输出叶片不合格,这时,更换里面的一枚或几枚叶片,则更新后的叶片组是合格的。此时,应当给出更换叶片的频率和静质量矩的值)。
上述约束条件,给出了叶片优化排序的多个目标。为了方便求解,把3级叶片逐次求解,因此,三级叶片可以采用同一目标函数。因此,一个多目标优化问题转化为三个单目标函数求解问题。
2 单级叶片目标函数
本文的研究目标就是要求排列在180°相对位置的两片叶片的静质量矩差的绝对值之和最小,即
式中:k为叶片个数的一半,(mr)i为第i个叶片的静质量矩(g·mm)。因此:目标函数设计为:
3 适应度函数设计
适应度函数的优良与否在很大程度上影响程序的收敛速度。在构造遗传算法时,处理约束条件主要有三种方法:搜索空间限定法、惩罚函数法、可行解变换法。本文采用罚函数法。本文将约束条件作为罚函数包含到适应度函数中去,从而将约束优化问题转换为无约束优化问题进行求解。此时适应度函数可以写为:
其中,r1、r2、r3、r2为罚函数尺度系数,f(x)为目标函数,Hz1为整级叶片中相邻叶片的频率差。Hz2是约束条件中(2)所允许的三对大频率差值与其他相邻叶片频率差值的频率差。
4 种群初始化
由于条件要求在100枚叶片里同时输出4组数据,因此本文把4组数据作为4条染色体,每条染色体代表一组叶片。程序同时对4组叶片优化排序。但是,在种群初始化时,一次只能产生一条染色体。这样做的结果是:最先产生的染色体把性状好的叶片挑选了,留到最后的是性状“恶劣”的叶片,这样很可能最后一组得不到可行解,造成资源浪费。为了避免这个问题,我们先来看单级叶片染色体的产生办法:
在单级叶片中,由于对1和2号位、8号和9号位、16和17号位的频率差要求严格,因此,为了加快收敛速度,在每条染色体中,本文先在原始数据中选取三个频率最大的叶片,随机放入1、9、17号位置;然后,选取三个频率最小的叶片,随机放入2、8、16号位置。这样,每一级叶片中,还有18个位置没有安放叶片。原始数据的剩余叶片,程序自动按照频率把它分成两部分,叶片频率大于平均频率的为一部分,小于平均频率的为另一部分。利用轮盘赌法按照一大一小的原则,先从大频率数据组里面随机抽取一个,再从小频率数据组里面随机抽取一个。以此类推,安装完毕一条染色体的剩余基因位置。利用同样方法,产生其他染色体。通过在种群初始化时,实施人工干扰,间接减少了排序的约束条件。
由单级叶片染色体的产生办法可知:每条染色体在挑选叶片时,总是把频率最大和最小的叶片优先选取。因此,本文在种群初始化时,先选取12枚频率最大的和12枚频率最小的叶片。在产生每一条染色体时,其关键位置的叶片都从这两组叶片里随机选取。其余叶片按照单级叶片办法产生。这样就较好的保证了最后一条染色体的叶片性状。
这样做的结果是产生了4个种群。程序同时对4个种群进行优化。
5 遗传算法编码与算子
5.1 编码方式
常用的编码方式包括二进制编码、浮点数编码、顺序编码、布尔矩阵编码等。为了调试程序的方便,本文采用十进制编码方式。本文把一级叶片中的总叶片数目(24个叶片)作为作为一条染色体,即每条染色体含有24个基因,每个基因包含一片叶片的相关信息。染色体上,第一号基因位置表示第一枚叶片安装位置。
5.2 选择算子
从适应度函数的设计上可以看出适应度大的个体优于适应度小的个体,这与一般遗传算法中适应度大的个体优于适应度小的个体一致,因此适于直接采用基于比例的适应度分配方法。本文采用轮盘赌选择法。
5.3 交叉算子
本文的编码方式允许一个个体的染色体编码中在不同位置出现相同的基因码,如果出现相同的基因码,则表明有两个或多个叶片的相关参数是相同的,这与实际工作情况是相符合的。本文采用多点交叉。但并非完全随机交叉。由于在种群初始化时的人为因素,每个染色体中的1～2、8～9、16～17号位置基因不能和其他位置基因交叉。
5.4 变异算子
变异算子较为简单,对个体内的基因排列按一定的变异率进行随机交换即可。同样,每个染色体中的1～2、8～9、16～17号位置基因不能和其他位置基因交换。只能相同性质的基因交换,即:1、9、17可以随机交换,2、8、16可以随机交换。
6 种子染色体
普通遗传算法程序,在多约束条件下,如果原始数据比较恶劣,容易陷入局部寻优。并且,一旦陷入局部寻优,很难跳出这个局部“陷阱”,从而影响收敛速度。为了加快收敛速度,本文采用了种子染色体导引法。即事先给定一个性状比较好的染色体作为种子,其作用是引导种群向最优点靠近。在多约束条件下,人工给出性状较好的染色体可行性不高。为了减少人工工作量,本文采用种群自动产生种子的方法。通常情况下,在程序运行时,把种群最大遗传代数作为程序循环次数。本文只设定较低的最大遗传代数。例如,设定100代,即程序循环100次。在程序初次运行时,把初始种群中适应度最大个体作为种子染色体。程序运行结束后,如果没有得到优化解,所产生的种群中适应度最大个体被用来当作下一次程序运行是的种子染色体。该种子染色体被植入下一次运行时的初始种群。通过植入种子染色体不仅能够引导种群向最优点靠近;而且,当种群遗传若干代后,种群变得过于庞大,从而影响运算速度,通过再一次种群初始化,可以有效解决这个问题。
7 内外交换法
染色体一旦产生,其交叉、变异等操作只能在染色体内部进行,不能再与外部数据进行数据交换。这不但造成剩余叶片资源浪费,也会使收敛速度变慢。本文用内外交换法解决了这个问题。即:在一个种群里,随机选取一条染色体。计算它的频率差和单元静质量矩之和等相关参数。如果叶片静质量矩的和之差大于138g.cm,或相邻象限叶片静质量矩的和之差大于115g.cm,则查找出静质量矩之和大的单元;然后,在这个单元里,查找一枚静质量矩最大的叶片,并记为big。此时,原始数据的剩余叶片里,查找一枚叶片,其静质量矩比big要小,并且其频率在代替big的频率后,新的频率差应符合上述约束条件;或者与big的频率相等。同样,查找一枚静质量矩最小的叶片,并记为small。在原始数据的剩余叶片里,查找一枚叶片,其静质量矩比small要大,在代替small后,其频率要求同上。实践证明,这种方法对解决陷入局部最优解问题行之有效。
8 非可行解可行化
如果有非可行解问题,则用虚拟叶片片法解决非可行解寻优问题。在初次种群初始化时,每枚叶片都是随机选取,并且只能选取一次。对非可行解叶片组,允许部分叶片可重复选取,等于增加了叶片数量。得到可行解后,有个别叶片在染色体里出现了两次。则该叶片参数即为待更新叶片的参数。
9 实例验证
给定一组叶片原始数据如表1所示。(因篇幅限制,只给出一组数据)。
在没有种子染色体引导和没有利用内外交换法的情况下,普通遗传算法,程序循环运行了25分钟,没有得出正确结果。在有种子染色体引导和利用内外交换法时,程序循环运行20分钟,得出正确结果如表2所示。
1 0 结论
程序运行结果表明:在多约束条件下,该程序收敛速度大为加快,并且运行结果正确。同时,以上算例证明,改进遗传算法在多约束和原始数据恶劣条件下,利用种子引导法和内外交换法并在种群初始化时施加人工干扰使程序收敛速度较快,结果准确。用此方法编制的程序实用性强。能有效解决在复杂条件下的多级叶片排序问题。
参考文献
[1]杨训.基于遗传算法的转子叶片优化排序[J].计算机仿真,2008,25(11).YANG Xun Optimum Arrangement of Rotor Blade Basedon Genetic Algorithms[J].simmulink of Computer 2008,25(11).
[2]彭国华.混合遗传算法在叶片排序问题中的应用[J].西南民族大学学报,32.PENG Gguohua Application of hybrid genetic algorithm inblade arrangement of engine[J].32.
[3]DeJong Ka An Analysis of the Behavior of a Classof Gentic Adaptive Systems[J].Dissertion AbstractsInternational,1975(10).