目标排序

目标排序（精选9篇）

目标排序 篇1

摘要：为降低微电网运行成本和污染排放,建立微电网多目标优化运行模型,并提出一种新型的α约束支配排序混合进化算法求解模型,该算法通过采用α约束支配排序机制,将所有约束条件统一处理为α约束水平度,并将其作为进化选择指标以控制所有个体快速转化为可行解,可显著提高约束处理效率。提出一种基于非劣排序的混合多目标进化算法,有效融合微分进化算法与分布估计算法各自的优点,克服单一算法种群多样性不足和易早熟的缺陷。通过分类逼近理想解的排序方法实现多属性决策,以获得最优折中解。某微电网算例结果表明所提算法有效、可行。

关键词：微电网,优化,α约束支配,进化算法,多属性决策,模型

0引言

随着节能减排的需求逐渐增强,分布式发电DG (Distributed Generation)的利用率也逐渐增加 ,由小容量分布式电源形成的微电网研究也逐渐深入[1,2]微电网将微型燃气轮机、燃料电池、光伏电源和风力发电机等分布式电源通过电力电子接口等方式联合在一起,为负荷端提供电能和热能。 根据微电网与常规配电网的连接与否,将其划分为并网、孤岛2种运行模式[3,4]。

微电网的经济运行与优化调度一直是国内外研究的热点,微电网运行优化问题的研究中,优化目标多种多样,如电能质量等技术目标、运行成本等经济目标、排污成本等环境目标,其中经济目标和环境目标是目前微电网运行所考虑的主要优化指标[5,6,7],鉴于微电网内基于化石燃料的分布式电源运行时会产生一定的碳排放,且排放量与其出力密切相关,同时基于国家“十二五”规划对低碳经济更为重视,本文将以运行成本和CO2排放量最小化为目标构建微电网多目标优化运行模型。

微电网的多目标优化运行是一个复杂的带多种等式约束和不等式约束条件的多目标优化问题,采用多目标优化算法求解其帕累托(Pareto)最优解集是一种常用手段[8]。 然而如何在优化算法中方便快捷地处理这些约束条件一直是各学者所致力研究的难题,常用的约束处理方法有罚函数法及多目标法等[9,10],这些方法都存在不足之处。 罚函数法为个体加入惩罚项,将约束问题简化成无约束问题,但惩罚项的设计多种多样,很难找到一个确切方案;多目标法将个体违反约束条件的程度作为优化指标,增加了优化问题目标函数的个数,计算更加复杂。 随着约束条件数量的增加,传统的约束处理方法复杂度也大幅增加。 因此,本文提出一种新型的 α 约束支配排 序混合进 化算法 α-CDSHEA (α-Constrain Dominant Sorting Hybrid Evolution Algorithm),可显著提高约束处理效率,降低算法的复杂度。 同时,为有效利用种群的宏观分布信息和个体信息,保持种群多样性,提高算法的收敛性和寻优速度,提出一种微分进化算法DEA(Differential Evolution Algorithm以及分布估计算法EDA(Estimation of Distribution Algorithm)相融合的混合进化算法 。 最后,通过分类逼近理 想解的排 序TOPSIS (Technique for Orde Preference by Similarity to an Ideal Solution)方法对算法得到的Pareto最优解集进行多目标决策,以获得最优折中解。

本文将以一个含光伏PV(Photo Voltaic)、风机WT (Wind Turbine)、微型燃气轮机MT(Micro Turbine) 燃料电池FC(Fuel Cell)以及负荷的微电网为算例分别用 α-CDSHEA、采用常规罚函数约束处理方法的非劣 排序微分 进化算法NSDEA (Non-dominate Sorting Differential Evolution Algorithm)和动态加权遗传算法(GA)进行求解,对比各自得到的Pareto最优前沿和运行时间,测试本文提出算法的有效性。

1微电网运行数学模型

1.1分布式电源模型

1.1.1微型燃气轮机模型

微型燃气轮机运行时的耗量特性[11]可描述为:

其中,PMT(t)为微型燃气轮机t时刻的功率 (k W);Δt为微型燃气轮机运行时间(h);ηMT(t)为微型燃气轮机t时刻发电效率;RLHVf为天然气低位热值(k W·h/m3); VMT(t)为 Δt运行时间内微型燃气轮机消耗的天然气量(m3)。

1.1.2燃料电池模型

燃料电池的耗能特性与微型燃气轮机类似[11], 可描述为:

式中各参数的意义参照式(1)。

光伏和风机的功率外特性模型分别参照文献 [12]和文献[13]。

1.2优化运行目标函数

1.2.1运行成本目标函数

运行成本目标函数F1包括投资折旧成本、运行维护成本、燃料成本以及微电网与外网的交互成本[14,15]:

其中,CDP(t)、COM(t)、Cfuel(t)、Cgrid(t) 分别为t时刻各DG的投资折旧成本 、运行维护成本 、燃料成本以及微电网向外网的购电成本;NG为系统DG总数;Caz,i为第i个DG的单位容量安装成本;Pi N为第i个DG的装机容量;r为年利率;ni为第i个DG的使用寿命;KOM,i为第i个DG的单位电量运行维护成本系数;Pi(t)为第i个DG在t时刻的有功输出 ;fi为第i个DG的燃料成本函数;CF为天然气的价格;CE(t)为t时刻微电网向外网购电的实时电价 ;Pgrid(t)为t时刻微电网向外网的购电量。

1.2.2CO2排放量目标函数

CO2排放量目标函数F2为[16]:

其中,ki为第i个DG的CO2排放系数;kgrid为配电网的CO2排放系数。

1.3约束条件

a. 潮流方程约束:

其中,Pfs、Qfs分别为节点f的有功和无功注入量;UfUg分别为节点f和g的电压;Gfg、Bfg、θfg分别为节点f和g之间的电导、电纳和相角差;g  f为与节点f相连的节点。

b. 功率平衡约束:

其中,Pd(t)为实时有功负荷;Ploss(t)为实时有功损耗。

c. 节点电压约束:

其中,Ui,min、Ui,max分别为节点i的最小、最大电压允许值;N为系统节点数。

d. 微电源的有功出力约束:

其中,Pi,min、Pi,max分别为第i个DG有功功率的最小、最大值。

e. 微电网与外网允许交互的传输功率约束 :

其中,Pgrid,max、Qgrid,max分别为微电网与外网允许交互的最大有功和无功功率。

f. CO2排放约束:

其中,Lmax为该地区CO2允许排放的最大限值。

2α-CDSHEA

2.1α约束支配排序

Takahama提出了 α 约束处理方法[17],α 约束方法将种群个体符合约束条件的程度数值化,提出了约束水平度的概念。 用 μ(x)表示个体x的约束水平度,且 μ(x) [0,1]。 μ(x)越大表示个体x属于可行解的概率越大,若 μ(x)=1,则表示个体x属于可行解。 约束水平度 μ(x)的值可由下式计算得出:

其中,hi(x)、gj(x) 分别表示个体的等式约束和不等式约束值;bi、bj分别为种群中不可行解对应的等式约束和不等式约束的平均值。

在得到个体x对应各约束条件的约束水平度之后,定义个体x的总约束水平度为:

从而定义 α 约束水平截集为:

对于个体x,如果xAα,则称之为满足 α 约束的个体。

由此可定义如下的 α 约束支配关系(用fα表示):

式(17)中,若个体x、y均满足 α 约束,即x,y∈Aα, 或者个体x、y的 α 约束水平度相等,即 μ(x)=μ(y),那么目标函数值f(x)、f(y)决定它们之间的支配关系; 否则,α 约束水平度 μ(x)、μ(y)决定它们之间的支配关系。

式(16)中的约束判定量 α 是一个时变量,可表示为 α(T),它随着进化代数T在0~1之间逐渐增加。 其初值 α(0)的大小由优化问题的可行域占全部搜索空间的比例决定,比例越大,α(0)可取的值越大。 α(T)可由下式计算得出:

其中,β 为 α 的控制参数,β [0,1],根据文献[17], 本文取 β=0.03。 由式(18)可以看出,在 β 的控制下, α 的值随着进化代数T增大逐渐增大到1,即 α 约束条件越来越严格,代表解集逐渐向可行域收敛。

将 α 约束支配关系作为主选择排序机制并以传统的非劣排序方法[18]为辅助排序机制引入多目标优化算法。 在算法种群进化过程中,父代和子代种群按以下原则进行选择和种群更新操作。

a. 父代群体P (T) 和子代种群P (T +1) 构成集合Q(T),将Q(T)分成满足 α 约束的子集Qf和不满足 α 约束的子集Qinf。

b. 将Qf中的个体进行 α 约束支配排序分级,同一级别的个体按非劣排序方法进行排序;将Qinf中的个体按 α 约束水平度大小进行排序。

c. 将Qinf中的个体按顺序排在Qf中的个体之后更新集合Q(T),按照种群规模M在Q(T)中选择前M位的个体更新子代种群P(T+1)。

设最优前沿的个体集合为Bbest(Bbest最终输出即为Pareto最优解集),初始Bbest为空集,在产生初始种群并进行种群排序后,将满足 α 约束的个体储存其中。 种群进化过程中,考察Qf中满足 α 约束的全部个体xi与Bbest中的全部个体yj之间的 α 约束支配关系,Bbest的更新操作按以下原则进行:如果xi被yj支配,Bbest集合不变;如果xi支配yj,则从Bbest中删去yj并加入xi,即Bbest= (Bbest- yj)∪xi。

Bbest的规模如果超过预定值,则按非劣排序方法对其中个体进行排序,删去排序靠后的个体以保持其规模恒定。

2.2混合进化算法

文献[18]提出NSDEA,它是一种基于DEA的多目标优化算法。 DEA是一种非常优秀的进化优化算法,具有结构简单、鲁棒性强、收敛性好、易于与其他进化算法混合等特点[19]。 至今为止,DEA已发展出多种进化策略[20]。 本文采用的DE / best / 2 / bi策略简述如下。

a. 变异。

在种群进化到第T代时,通过下式变异产生新个体:

其中,vi,T为变异得到的新个体;xbest,T为全局最优个体;F为缩放因子,F  (0,1);xr1,T、xr2,T、xr3,T、xr4,T为随机抽取的4个个体。

b. 交叉。

进化群体Xi,T+1和变异之后的群体Vi,T+1通过下式进行交叉产生新个体:

其中,uj,i,T+1为交叉位;k为随机整数;rand(0,1)为随机产生的0~1之间的数;δCR为交叉概率。

然而,上述DEA在进化过程中,种群会较快失去个体多样性而导致变异差分项趋于0,使得寻优停滞或陷入局部搜索。 EDA是一种基于统计学原理的新型进化算法[21],不同于传统进化算法采用交叉、变异等进化手段,EDA通过建立概率模型描述解集在搜索空间的分布信息,然后采用随机采样从群体宏观角度进化产生子代,能充分利用群体的智能信 息,具有较强的全局搜索能力。 为此本文拟将EDA基于整个种群统计信息的宏观层面控制种群进化的模式与DEA基于个体变异、交叉的传统进化模式相融合,提出一种混合进化算法,可有效加强算法的种群多样性,提高其收敛速度并防止早熟收敛。 本文采用基于高斯分布建模的连续域EDA,其建模原理简述如下。

用一个概率向量pT(x)来表示第T代种群的概率分布,pT(x)=(pT(x1),pT(x2),…,pT(xM))。 从其中选择m个优势个体,本文取m = M / 2,假设其满足以下高斯分布:

其中,N(xi; μiT; σiT)为关于xi、 μiT、σiT的高斯分布。 各代的均值 μi和方差 σi2估计如下:

其中,xiT,1、xiT,2、…、xiT,m为第T代种群的m个优势个体。

3算法求解步骤

3.1Pareto最优解集

本文提出的 α-CDSHEA流程如图1所示。

综上所述,α-CDSHEA的Pareto最优解求解步骤如下。

a. 种群初始化 。 进化代数T = 0, 最优前沿以一天24 h各时段的微型燃气轮机 、 燃料电池有功出力和微电网向电网的实时购电量为个体变量,随机产生初始种群P(T),计算种群的适应度f和针对各约束条件的约束值[gj(x) hi(x)],然后计算个体的 α 约束水平度进而得到个体的总 α 约束水平度。

b. 排序并选择优势个体。 对种群进行 α 约束支配排序和非劣支配排序,选择前一半个体形成优势种群,并更新最优前沿集合Bbest。

c. 种群进化产生子代 。 根据优势种群建立概率分布模型,分别用DEA和EDA进化产生子代种群P1(T + 1)和P2(T + 1),计算子代种群的适应度f和约束值[gj(x) hi(x)],并计算个体的 α 约束水平度和总 α 约束水平度。

d. 选择和种群更新 。 依据2.1节中的操作原则更新种群P(T+1)和最优前沿集合Bbest。

e. 判断 。 若达到进化代数要求且最优前沿集合Bbest达到预定规模,进入下一步;否则T =T +1,转步骤b。

f. 输出最优前沿集合Bbest中的个体为最终的Pareto最优解。

3.2最优折中解

为挑选最优折中解,决策者需根据偏好对Paret最优解集 进行筛选 排序 。 Hwang和Yoon提出的TOPSIS方法[22]通过计算Pareto最优解集和理想解的距离,使其与理想解距离最近,并且与负理想解距离最远,判断解集的优劣并排序。 以r个目标、l个解为例,其排序流程如下:

a. 对原始决策矩阵X =[xij]l ×r进行向量规范化, 得到规范化决策矩阵Y=[yij]l×r;

b. 构成加权规范化决策矩阵Z = [zij]l×r,其中zij= τjyij,τ=[τ1,τ2,…,τr]T为决策者给定的加权向量;

c. 确定正理想解Z+和负理想解Z-;

d. 计算各个解到正理想点的距离di+和到负理想点的距离di-;

e. 计算各个解的综合评价指数, 进而排序 。

其中的加权向量τ 可采用客观赋权的变异系数法[23]确定 , 其流程如下 : 计算各目标的均值和方差计算各目标的变异系数将变异系数归一化 , 可得各目标的加权系数

4算例分析

4.1微电网结构与参数

本文以一个含光伏发电、风力发电、微型燃气轮机、燃料电池4种微源的微电网系统为例[24],如图2所示,馈线L1为民用负荷(功率因数为0.85),馈线L2、 L3分别为工业负荷和商业负荷(功率因数为0.90)。

本文作如下假设:在单位时间间隔内,各微源的有功和无功出力恒定、负荷需求恒定、微电网与主网间的交互功率恒定且交互电价维持恒定。 本文取单位时间间隔为1 h。

微电网中各线路参数以及各节点最大负荷如表1所示,表中R、X和Smax分别为线路电阻、电抗和末节点最大负荷。 实时的民用负荷、工业负荷、商业负荷占节点最大负荷的百分比如图3所示。 微电网与外网允 许传输的 最大有功 和无功功 率分别设 为75 k W和46.48 kvar(传输线功率因数0.85),实时电价见文献[25],天然气价格为3元 / m3,各DG的运行成本系数、CO2的排放系数以及某地区CO2的排放限值见文献[26],微电网中各DG的参数见表2。

光伏和风机均为不可控的分布式电源,采用最大功率跟踪输出模型,且由于光伏、风机发电成本低和污染物排放率低,本文假设其为零运行成本、零排放。 根据某日的光照和风力强度,假定光伏和风机的预测日小时出力如图4所示。

4.2优化结果

为了证明本文算法在处理复杂约束多目标优化问题上的优越性,分别用 α-CDSHEA、采用常规罚函数约束处理方法的NSDEA以及动态加权遗传算法对本文算例进行求解,得到该日微电网运行成本和CO2排放量的Pareto最优解集。 3种算法的种群规模均设为100,α-CDSHEA和NSDEA的微分进化缩放因子均为0.85,交叉概率为0.5,α-CDSHEA的 α 初值设为0.5。 本文中遗 传算法直 接调用现 成的MATLAB遗传算法工具箱(GAOT)[27],由于该软件包不能直接求解多目标优化的Pareto前沿,为此需对双目标函数进行加权使之转化成单目标函数,鉴于加权值难以确定,可通过在0~1之间均匀取100个动态权值构造动态加权遗传算法,以间接获得Pareto前沿。 本文运行算法硬件环境的CPU为Intel Core i53317 @ 1.70 GHz 1.70 GHz , 仿真环境为MATLAB R2013a。 以上3种算法各自运行100代得到的优化曲线如图5所示,运行时间如表3所示。

图5中曲线对比可以看出,α-CDSHEA比采用常规罚 函数约束 处理方法 的NSDEA最终得到 的Pareto前沿分布更加均匀 、解集更加全面 。 而采用GAOT通过动态加权函数优化得到的解集明显劣于 α-CDSHEA,与真正的Pareto最优解集相差甚远。 另外,由于采用GAOT求解多目标优化问题需要不断动态改变权值进行单目标优化,因此表3中GAOT运行时间远大于 α-CDSHEA和NSDEA。 而 α-CDSHEA所需要的运行求解时间略小于NSDEA,实际上由于 α-CDSHEA是融合了DEA与EDA这2种不同算法机制的混合算法,其理论运行时间应远大于NSDEA,但本文提出的约束处理方法有效降低了算法的复杂度,导致最终运行时间略小。

为进一步 比较 α-CDSHEA和NSDEA在得到Pareto解集时在收敛速度上的优劣 ,取各自运行25代时的优化曲线对比,如图6所示。

由图6可知,运行至25代时,α-CDSHEA已基本收敛,而NSDEA还远未达到收敛,可见 α-CDSHEA的收敛速度要高于NSDEA,说明引进 α 约束处理方式和混合进化算法是有效、可行的。

经过对 α-CDSHEA优化得到的Pareto前沿进行最终多目标决策优选,可得到该日最终运行成本和CO2排放量分别为4 101.2元和68.236 8 kg,对应的该日微型燃气轮机、燃料电池的有功出力及微电网系统与电网的交互购电优化结果如图7所示。

为保证微电网的独立性,当网内DG输出足够满足负荷需求时,不向外网购电,此时相当于孤岛运行;当网内DG输出无法满足负荷需求时,在允许传输限值范围内向外网购电,此时相当于并网运行。 从图7中可以看出,01:00 — 08:00时微型燃气轮机和燃料电池的出力足够满足网内负荷安全有效运行不需要向外网购电;09 : 00 — 14 : 00、16 : 00 — 19 : 00 22 : 00 — 24 : 00,微型燃气轮机和燃料电池的出力满足不了网内负荷需求,故需要向外网购电 ;15:00 19:00 — 21:00, 微型燃气轮机 、 燃料电池的出力配合向外网购电仍然不能满足网内负荷需求,存在有功缺额,此时微型燃气轮机和燃料电池为最大功率输出,向外网所购电量也达到传输上限,此时为保证微电网安全有效运行,应适当切除民用负荷。 微电网的无功负荷也由微型燃气轮机和燃料电池共同负担,并配合少量外网提供的无功出力。

5结论

本文构建了以微电网运行成本和CO2排放量最小为目标的优化模型。 微电网多目标优化运行是一个复杂的带多种等式约束和不等式约束条件的多目标优化问题,为了提高约束处理效率并改进算法提高其质量,本文提出了 α-CDSHEA。 以一个含光伏发电风力发电、微型燃气轮机、燃料电池以及负荷的微电网为算例进行仿真分析,分别用 α-CDSHEA、采用常规罚函数约束处理方法的NSDEA以及动态加权遗传算法进行优化得到其Pareto解集,算例结果表明 α-CDSHEA在解集质量、收敛速度和运算时间上都明显优于另外两者,能有效地处理复杂约束的多目标优化问题,较好地验证了本文所建模型和求解算法的可行性和有效性。

目标排序 篇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

在传统的方法中,多目标优化问题是将多目标函数通过赋予不同的加权系数转换为单目标函数来处理,只有当这些权重系数选择的合适,预期的最优目标才可以实现。然而,设计者要确定这些权重系数是非常困难的。例如,在文献[2]中,研究者采用了两步优化过程来设计高频变压器。首先确定了磁芯的优化尺寸,然后再设计绕组,使损耗达到最小。 多目标进化算法以其处理多目标问题的优势,在过去几年的研究中已经逐步进入了实用性阶段。文献[3—6]是对进化算法的早期研究,在文献[5]中, Srinivas和Deb基于Pareto优化技术提出的非支配排序遗传算法( NSGA) 。和传统的优化方法相比, NSGA避免了加权系数的选择,但它计算量庞大,缺乏最优保护策略,需要确定共享参数。后来,研究者们通过提高进化算法的性能提高了算法的实用性［7—10］。在文献[7]中,Deb和其他研究者提出了二代非支配排序遗传算法( NSGA-Ⅱ) ,通过拥挤距离的定义,改善了排序方法和分割操作,一定程度上解决了之前进化算法存在的这些缺陷。在文献[8] 中,采用动态的种群规模,可以得到理想的种群分布密度,通过局部搜索取得了更好的收敛性。在文献[9]中,提出了在动态多目标进化算法中,基于单元的等级和密度有效计算优势度和多样性信息的估计策略,文献[10]对多目标优化中的相似性和多样性保护进行了讨论。由于在实用性的改进,NSGA -Ⅱ 逐渐应用于不同的优化设计中。例如,Kannan S等首先尝试采用NSGA-Ⅱ解决发电扩建规划问题［11］。 Soyel,Hamit等将NSGA-Ⅱ算法用于一种特征选择方法的研究［12］。文献[13]基于NSGA-Ⅱ,对螺旋轴流式多相泵叶轮做了多目标形状优化。在文献[14]中,一些研究人员基于NSGA-Ⅱ使用二维目标函数研究了小功率铁氧体变压器的优化设计方法, 但表面温度计算采用了近似的计算公式,具有一定局限性。

尽管采用NSGA-Ⅱ做优化具有很大的优势,但依旧存在一些缺点。在文献[15]中,通过将受控精英和动态拥挤距离组合,研究者对NSGA-Ⅱ算法做了修改,在解决多目标优化问题的研究中提高了非支配解的多样性。当我们在大功率电子变压器优化设计中使用NSGA -Ⅱ时,发现优化过程有时会收敛到局部最优解。为了减少早熟收敛的概率、缩短优化时间,本文提出了一种改进的NSGA-Ⅱ算法。并采用该算法对大功率电子变压器进行了多目标优化。根据优化结果,制作了30 k W超微晶合金磁芯电子变压器。

1改进的NSGA-Ⅱ算法

与其他进化算法相比,NSGA-Ⅱ是一种计算速度快、性能好的多目标进化算法。将NSGA-Ⅱ应用于电子变压器的优化设计中,发现优化过程有时收敛到局部最优解。为了避免这种早熟收敛现象,进一步降低计算量,本文对该算法加以改进。把改进后的算法称之为改进的NSGA-Ⅱ算法。图1是该算法的流程图。改进如下:

( 1) 在种群划分步骤中,将初始种群分为两个子群体。

( 2) 对各个子群体独立地进行选择运算,判断个体相似性,淘汰相似个体。

( 3) 将两个子群体中选择的个体重新组合生成下一代种群。然后对下一代种群进行交叉和变异运算。

( 4) 如果种群规模不足,则应从淘汰的个体中选择适应度值高的个体补足群体规模。

设参与交叉运算的个体数为n,通常n大于100。采用NSGA-Ⅱ算法时,需要进行C2n次运算,而采用改进的NSGA-Ⅱ算法时只需要2C2n/2次运算。因此,后者的计算量较前者减少了近一半。此外,设xi=[x1i,x2i,…,xni],xj=[x1j,x2j,…,xnj]是群体中的两个点,定义这两个点的距离为,给定一个阈值,淘汰距离小于给定阈值并且适应值低的个体,这样增大了种群的多样性,避免了局部最优的出现。同时,由于补充了高适应值个体,整代种群的竞争力得到提升,早熟收敛现象大大降低。

2电子变压器的优化

2. 1多目标函数

在许多应用场合下,电子变压器都要求小型高效,合理地选择设计参数可以使变压器体积和损耗达到最小。变压器的大小主要由磁芯尺寸确定,磁芯的尺寸取决于窗口面和磁芯横截面的面积乘积( AP)［16］。将AP值作为第一目标函数f1( X) 。铁芯损耗作为第二目标函数f2( X) 。绕组损耗作为第三目标函数f3( X) 。选择Bm和j作为优化变量。 三维数学模型表示如下。

式( 1) 中,Pt为总视在功率; Po为输出功率; Km为窗口占空系数; f为工作频率; Bm为磁芯磁通密度; j为电流密度; V为磁芯体积; Cm,α,β 为超微晶合金损耗曲线系数; Kr为交流电阻系数; Rdc为直流电阻; S为导线横截面积; η 为效率。

2. 2磁芯材料

高频大功率变压器需要低损耗、高饱和磁通密度、高居里温度的材料作为磁芯材料,铁氧体、硅钢片、非晶合金以及超微晶合金是电子变压器常用的磁芯材料,这些磁芯材料的一些特性在表1中列出。 可以发现,硅钢片的饱和磁通密度和居里温度很高, 但这种材料的损耗也很大,如果将这种材料用作高频大功率变压器的磁芯材料,效率将会很低。铁氧体的饱和磁通密度在这些材料中最低,若采用这种材料做磁芯,则会导致磁芯体积非常庞大,此外,铁氧体的居里温度很低,在磁芯工作温度高于其居里温度时会出现磁性消失。超微晶合金是一种具有优良特性的新型磁性材料,拥有较高的饱和磁通密度,较低的损耗和较高的居里温度。综上所述,超微晶合金材料具有高频大功率的变压器磁芯所需的最好综合性能。超微晶合金1K107的损耗曲线如图2所示。

3采用改进的NSGA-Ⅱ算法对电子变压器进行优化

分别基于NSGA、NSGA-Ⅱ和改进的NSGA-Ⅱ三种优化算法,对电子变压器进行了优化设计; 并对优化结果进行了比较。变压器的设计参数为: 输出功率Po= 30 k W,工作频率f = 20 k Hz,输入电压U1= 1 200 V,输出电压U2= 350 V。

设计中的电子变压器采用型号为1K107的超微晶合金作为磁芯材料,在程序中,根据磁芯材料的特性,Bm的取值范围设置为0. 4 ~ 1 T,j的取值范围设置为4 ~ 10 A/mm2。

利用NSGA-Ⅱ算法对电子变压器进行了优化设计,选择的参数如下: 种群规模100,交叉概率0. 9, 变异概率0. 1,代沟0. 8。

根据传统设计方法获得初始设计值,程序运行获得一组Pareto解,可以根据工程的需要选取最优解。已有的研究表明,当变压器磁芯损耗等于绕组损耗时,变压器的效率最大［16］,根据此原则从一组Pareto解中选择最优解。当优化程序重复运行时, 获得的Pareto解集是不同的。可以发现,根据文献[16]中的效率最大原则选择的最优解实际上不是全局最优,这个现象称为早熟。图3所示是一组早熟结果。这些结果的坐标和相应的Bm和j如表2所示。如图3所示的星形点被认为是这组Pareto解的最优解,其坐标为: 磁芯损耗235. 8 W,绕组损耗235. 7 W,AP值94. 6 cm4。这个结果并不合理,其效率低于最初设计结果,且它的面积乘积值明显小于初始值,分析认为这是由于早熟收敛导致的一个错误结果。在五十次程序运行中共有六次这样早熟收敛发生。

其中,变压器的磁芯损耗由图2所示的损耗曲线和设计尺寸得到。初级和次级绕组长度由设计尺寸计算得到。绕组损耗由公式P = I2Rac得到。

之后我们对算法进行改进,利用改进的NSGA- Ⅱ算法再对电子变压器进行优化设计。得到的一组优化结果如图4所示。这些结果的坐标和相应的Bm和j如表3所示。结果发现,早熟收敛概率大大下降,在五十次程序运行中,只有两个早熟收敛结果。一个全局最优解如图4中的星形点所示。坐标为: 磁芯损耗144. 1 W,绕组损耗144. 4 W,AP值195. 2 cm4。

作为比较,基于NSGA-Ⅱ算法的一组全局优化结果如图5所示。这些结果的坐标和相应的Bm和j如表4所示。星形点是全局最优解。坐标为: 磁芯损耗144. 5 W,绕组损耗144. 2 W,AP值195. 2 cm4。

用NSGA算法进行同样的优化设计,在五十次程序运行中,早熟收敛发生八次。全局优化结果如图6所示。最优解坐标为: 磁芯损耗144. 8 W,绕组损耗144. 5 W,AP值195. 1 cm4。

优化方法和传统方法之间的比较如表5所示。 可以看出,采用优化方法设计的变压器的效率要高于采用传统方法。根据这些优化方法得到相同的最优点,但改进的NSGA-Ⅱ算法收敛速度最快,早熟收敛概率最低。

4温度场分析和变压器制作

变压器的功率损耗会引起变压器温度的升高,在变压器制造之前需要对其进行温度校核。但是最高温度点的位置和最高温度值无法事先确定。现有的热校验公式只适用于温升极限为60 ℃的小功率变压器［17］。 因此,可以通过数值计算得到温度场的分布来对变压器进行热校核。

根据图4所示的优化结果,设计了一台变压器。 磁芯型号为CD40 ×40 ×110,初级绕组匝数为62,次级绕组匝数为18。为减小漏电感,绕组采用“三明治”结构形式,次级绕组夹在两部分初级绕组之间。初级和次级绕组均采用扁铜线,规格分别为5. 0 mm ×2. 0 mm和10. 0 mm ×2. 0 mm。选用聚四氟乙烯( PTFE) 膜作为绝缘层材料。最后用浸渍漆将变压器灌注。

在制作变压器之前,利用ANSYS有限元软件计算了变压器的温度场。结果如图7所示。考虑变压器的结构对称性,采用实体单元SOLID90建立其八分之一模型。环境温度设置为20 ℃。散热系数设为50 W / ( cm2·K) ,这使用普通风扇可以达到。由图7可知,所设计的变压器的最高温度是82. 28 ℃。而超微晶合金材料1K107的居里温度是560 ℃,正常工作温度达120 ℃,因此这种材料能满足该变压器温升要求。

根据图4所示的优化设计结果制作了一台变压器。制造商对其进行了绝缘强度和温升试验,最高耐压为3 400 V,在工作频率下没有发生过热现象。最终的变压器如图8所示。

5结论

在本文中,首先提出了改进的NSGA-Ⅱ算法,提高了算法的性能。通过提高种群多样性和竞争力,减少了早熟收敛的概率。同时,将种群分割成两个子种群提高了计算效率。采用改进的NSGA-Ⅱ算法,可获得一组合理的Prato结果。优化结果可以根据设计要求从这些Prato结果中选择。与NSGA-Ⅱ相比,改进的NS- GA-Ⅱ算法在电子变压器的优化设计中具有早熟概率低、计算量小的优点。

改进的NSGA-Ⅱ算法对追求小体积、高效率的电子变压器的优化设计是非常有效的。本文选择电子变压器的AP值,磁芯损耗和绕组损耗作为目标函数。采用改进的NSGA-Ⅱ算法对其做了优化设计,使得优化设计变量Bm和j的确定不再依赖于设计者的经验。

目标排序 篇4

索引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;

浅谈冒泡排序与选择排序 篇5

1 冒泡排序

1.1 排序简介。

在计算机排序范围中属于一种简单的排序算法, 排序过程中较小的数放到前面较大的数放到后面, 类似气泡不断往水面上升, 称为冒泡排序。

1.2 排序代码

1.3 过程分析。假设程序运行时通过键盘输入38, 49, 65, 76, 13这五个数, 按照由小到大进行排序 (方括号内的属于无序区) 。

具体排序过程如下:a.将整个记录序列划分为无序区和有序区, 刚开始无序区包含所有待排序的记录。b.在无序区从前到后依次比较相邻记录, 若反向则交换记录值, 最终实现较小记录值往前移, 较大记录值往后移。c.不断重复进行步骤b, 直到无序区没有反序记录为止。

初始序列:[38, 49, 65, 76, 13]

2 选择排序

2.1 排序简介

该方法也是一种简单直观的排序方法, 每一次从待排序的数列中找出最小或最大的数放到有序序列的起始位置, 直到全部排完。

2.2 程序代码

2.3 过程分析。

具体排序过程如下:a.将整个记录序列划分为有序区和无序区, 刚开始有序区为空, 无序区含有待排序的所有记录。b.在无序区查找值最小的记录, 将最小值与无序区第一个记录交换, 使有序区增加一个记录, 无序区减少一个记录。c.不断重复进行步骤b, 直到无序区只剩下一个记录值为止。

初始序列:[38, 49, 65, 76, 13]

3 比较总结

判断一种算法的优略, 主要从空间复杂度和时间复杂度两个方面考虑。下面对冒泡排序和选择排序分别进行分析、说明:

3.1 对于冒泡排序而言, 空间方面只用了一个辅助单元, 排序稳定, 时间方面N个记录需要N-1轮排序, 对于j个记录的无序序列进行一轮排序需要j-1次记录值比较, 总比较次数为O (n2) , 各个记录需要交换的次数:最理想的情况该序列已有序不需要交换;最差的情况每次比较后都得进行交换三次, 总交换次数为:O (n2) 。经分析, 要提高简单冒泡排序效率我们应做如下改进:当进行每一轮比较时, 对交换的数据做一个标记, 即标志值为1发生交换否则未交换。只要标志值为0, 就会停止循环扫描, 减少扫描的次数, 这样有效的降低时间复杂度。带标志冒泡排序对于大批量数据排序很有效。

3.2 对于选择排序而言, 空间方面也是用了一个辅助单元, 排序不稳定, 时间方面N个记录同样需要N-1轮排序, 比较次数与记录初始序列无关, 序列初态为正序时, 移动次数为0;最差状况每轮排序都进行交换, 总的移动次数为3 (n-1) , 交换记录只执行一次, 直接选择排序最终的平均时间复杂度仍为T (n) =O (n2) 。经分析, 要提高直接选择排序的效率我们应做如下改进:在传统选择排序的基础上, 我们可以在一轮比较完成后能同时找到当前最大值和最小值, 分别放到对应的第一个位置和最后一个位置, 这样比较轮数就会减少一半, 达到降低时间复杂度。

在C语言中排序方法很多, 但是每一种排序算法既有优点又有缺点。本文对冒泡法和选择法的排序思想在时间效率方面改进是合理、有效的。我们对给定数据记录进行排序时应从多角度考虑并试着采取多种方法实现。

摘要：排序是C语言中一类穷举算法问题, 主要对冒泡排序和选择排序的排序思想、排序过程及代码实现进行介绍, 最后对其分析并找出改进每一种排序方法的思路, 让读者今后更好的理解、运用这两种排序方法。

关键词：冒泡排序,选择排序,记录值

参考文献

[1]王红梅、胡明.算法设计与分析 (第2版) [M].北京:清华大学出版社, 2013.

目标排序 篇6

随着科技的不断发展, 计算机的应用领域越来越广, 但由于计算机硬件的速度和存储空间的有限性, 如何提高计算机速度并节省存储空间一直成为软件编制人员努力的方向, 在众多措施中, 排序操作成为程序设计人员考虑的因数之一, 排序方法选择得当与否直接影响程序执行的速度和辅助存储空间的占有量, 进而影响整个软件的性能。数据分类也是一个值得优化的问题, 本文将对上述问题进行阐述。

1、相关技术介绍

1.1 排序算法

所谓排序, 就是使一串记录, 按照其中的某个或某些关键字的大小, 递增或递减的排列起来的操作。输入一列数<a1, a2, …, an>, 输出对输入序列的一个变换 (重排列) <a1’, a2’, …, an’>, 其中a1’≤a2’≤…≤an’。

1.2 QT介绍

Qt是诺基亚开发的一个跨平台的C++图形用户界面应用程序框架。它提供给应用程序开发者建立艺术级的图形用户界面所需的所用功能。Qt是完全面向对象的, 很容易扩展, 并且允许真正地组件编程。

2、排序算法性能分析

根据各种排序算法的性能比较, 每种排序算法都各有优缺点, 没有哪一种方法是绝对最优的, 如何在实际应用中选择合适的排序算法, 选择的依据是否就是算法的平均时间复杂度"O", 事实上对排序的效率来说, 影响它的因素非常多, 平均时间复杂度最优的算法在进行某一些实际数据排序时, 其时间并不一定是最优的。而平均时间复杂度差的算法, 有可能更加适合某一些具体的情况。一般而言, 可依据以下准则进行排序算法的选择。

(1) 一般不使用或不直接使用“原始”的冒泡排序算法冒泡排序虽然容易理解, 编程简单, 但在实际应用中, 是不可取的。

(2) 快速排序和堆排序适用于大数据且空间复杂度有要求的情况下快速排序和堆排序平均时间复杂度都为O (nlogn) , 对于基于比较的排序算法而言, 其平均时间复杂度的下限为O (nlogn) , 不可能找到比这更优的算法。

(3) 插入排序最适用于加入新数据的情况对于插入排序算法, 由于它对数据的有序性非常敏感。

(4) 基数排序适用于大数据量且有较多内存空间的情况, 它的平均时间复杂度是。但是, 在进行的过程中, 需要额外的空间, 且所需的空间和数据个数相当, 所以应用这种排序算法的前提是要能使用附加空间。

3、算法演示系统

本演示程序使用QT设计图形界面, 通过调用指定排序算法处理输入数据并输出排序过程达到演示的目的。首先, 在“Data Input”区域输入待排序的数据, 或者通过点击“Select File”按钮选择文件充当输入数据, 然后在“Select Sort Model”处选择排序方式后, 就可以点击“Start”按钮开始演示过程。演示结果在程序左侧的“Demonstrate”区域显示, 部分关键数据以红色显示。

4、关于数据分类

本文所阐述的数据分类, 是指将数据按照类型和属性分类。算法描述如下:

Step 1:获取需要分类的数据。

Step 2:处理获得数据每一项的类型和种类

Step 3:设置数据的优先级

Step 4:for i=0 to Set the priority number

Queue<Type>q[Type number]

Push to the correspond queue

Pop the data to the initialization queue

以学生信息为例, 每个学生有对应的信息 (专业、班级、姓名、性别、民族、政治面貌、省份) 。在乱序的数据中, 设置排序的优先级为学生省份、学生班级、学生性别。则该算法处理后的程序会按照设置的优先级分好类。分析本算法的复杂度, 只需要O (kn) , k为需要设置优先级的数据类型, n为需要分类的数据项。而普通的朴素的算法需要的复杂度为O (nlogn) 。使用类似于基数排序的算法在数据分类上, 能比较有效的提高数据分类的效率。

5、结论

完成了一套排序算法的演示程序, 可以实际的运用到课堂教学中提高教学效率。同时完成了一个使用基数排序类似算法进行数据分类的程序。

参考文献

[1]刘红岩, 陈剑, 陈国青.数据挖掘中的数据分类算法综述[J].清华大学学报 (自然科学版) , 2002, 42 (6) :727-730.

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

[3]徐章艳, 刘作鹏等.一个复杂度为max (O (|C||U|, O (|C|2|U/C|) 的快速属性约简算法[J].计算机学报, 2006, 29 (3) :391-399.

排序题解题指要 篇7

一. 看语段是否按时间 (事物的发展变化) 顺序排列

例1:下列句子顺序正确的一组是 () (注:以下例题, 题干略)

(1) 青年期是记忆最好的时期。 (2) 老年人记忆力随着大脑功能的衰退逐渐下降, “近期记忆”不好, 而“远期记忆”却比较牢固。 (3) 儿童的大脑发育未完成成熟, 因此“直观记忆”能力较强。 (4) 成年人生活经验比较丰富, 语言能力和逻辑思维能力比较强。 (5) 不同的年龄有不同的记忆特点。 (6) 有的学者估计, 人到六十岁到八十岁, 记忆只是最高水平的一半左右。

A、 (2) (4) (1) (3) (5) (6) B、 (5) (3) (1) (4) (2) (6)

C、 (1) (3) (2) (4) (5) (6) D、 (1) (3) (4) (2) (6) (5)

思考:第 (5) 句“不同的年龄有不同的记忆特点”显然是总起句。因为其它句子是从“不同年龄”和“不同记忆特点”两方面说明总起句的, 从逻辑关系来看应是总分关系。又因为关于老年人的记忆特点是由两个句子组成的, 用以强调记忆遗忘曲线规律, 而其它句子都是一个句子, 只有一层意思。所以除第五句总起句, 其余五句以 (3) (1) (4) (2) (6) 的顺序, 由儿童到老年, 按时间顺序入座, 本题的答案是B。

例2: (1) 我们在规划现代化建设蓝图时, 把科技兴国战略和可持续发展战略放在十分突出的位置。 (2) 在二十一世纪里, 我们将实现科学和教育的腾飞, 使中国的现代化建设始终沿着依靠科学技术进步和提高劳动者素质的轨道不断前进。 (3) 新中国成立以后, 特别改革开放二十年来, 中国政府一直高度重视发展科技和教育事业。 (4) 最近我们又决定, 由中国科学院率先进行建设国家知识创新体系的试点工程, 就是要从下一个世纪中国发展的战略需要和世界科学前沿的前景出发, 明确新的科技目标, 调整现行的运行机制, 力争取得更多更大的科技新成就, 真正搞出中国的创新体系来。 (5) 邓小平同志提出的“科技是第一生产力”的著名论断, 正是成为中国发展的一个重要指导思想。

A、 (2) (1) (3) (4) (5) B、 (3) (5) (1) (4) (2)

C、 (3) (4) (1) (2) (5) D、 (4) (5) (3) (1) (2)

通读全段, 我们可以从 (2) (3) 句来判断作者在回顾历史, 即按时间顺序从二十世纪直到二十一世纪我国在科学和教育上取得的成就。所以, 应将 (3) 句放首句, (2) 句放在尾句, (5) 句引用邓小平著名诊断。 (1) (4) 句是写在邓小平理论指导下的使科学和教育腾飞的有关措施, 所以这三句是总分顺序, 排列应是 (5) (1) (4) 。本题答应是B。

遇到按时间顺序排列的语段, 解题时需考虑:甲比乙早, 丙比乙晚或乙是甲产生的, 丙是乙产生的这样的规律性的因素。

二. 看语段是否按空间 (事物的存在) 顺序排列

例3: (1) 峰前清溪环流, 寒泉明冽, 给人清幽之感。 (2) 峰上杂草丛生, 苍翠四幂。 (3) 峰下岩洞幽深, 千回百转, 曲折相通。 (4) 峰高数丈, 虽非崇岗峻岭, 然而怪石嵯峨, 山势玲珑。

A、 (1) (2) (3) (4) B、 (4) (3) (2) (1)

C、 (2) (3) (1) (4) D、 (4) (2) (3) (1)

思考: (4) 句对山峰作概括介绍为总起, 与 (1) (2) (3) 句的关系是先总后分, 符合逻辑。 (1) (2) (3) 句, 按先“峰上”, 再“峰下”, 后“峰前”, 从上而下, 按 (2) (3) (1) 空间顺序排列, 故答案为D。

例4: (1) “一片白, 那是窗”。 (2) 一片蓝, 那是墙。 (3) ……只在树与树之间露出一些建筑的线条。 (4) 一排整齐的图案式的屋瓦。 (5) 一角活泼翘起的屋檐。 (本语段摘《我的空中楼阁》)

A、 (1) (2) (3) (4) (5) B、 (2) (1) (3) (5) (4)

C、 (3) (5) (4) (2) (1) D、 (2) (1) (4) (5) (3)

思考:标示该语段出处起提示作用, 同时也降低了解题难度。学生如熟悉课文就不难看出观察角度是站在山下, 仰视小屋, 因其远, 所以只能看到“……树与树之间露出的一些建筑物的线条。”所以, (3) 句应为首句。因为远, 又有树, 所以先看到“屋檐”, 然后看到“屋瓦”;看到“墙”, 看到“窗”。应该都是建筑的某一局部。而从这个局部来看也有“先”、“后”, “上”、“下”的次序, 本题正确答案是C。

遇到按空间顺序排列的语段, 则要注意标示距离远近, 方位上下左右等词语。

三. 看语段是否是按逻辑 (表现事物的内容各方面的内在联系或事物性质) 顺序排列

例5: (1) 但是他们不是历史的脊梁, 他们像蛛丝一般无力, 绊不动历史的脚步。 (2) 自然就不免有清谈者, 有酣睡者, 有摇头者, 有彷徨者, 有哭泣者。 (3) 行程是艰难的。 (4) 历史在前进中, 不免有挫折, 有迂回, 有失败。

A、 (3) (4) (2) (1) B、 (1) (2) (3) (4)

C、 (4) (2) (1) (3) D、 (3) (1) (4) (2)

思考: (3) 句总起全段。 (2) (4) 句把历史前进中遇到艰险的人们的种种表现与过万重山时遇到艰险时人们的种种表现作类比 (因为前文已对后者作了种种描写, 所以这里省略) 。因此第二次选择顺序为 (4) (2) , 然后用 (1) 句转折句“清谈者, 酣睡者……”的表现, 用以突出那些敢为天下先的英雄, 所以 (1) 句应安排在尾句。本题答案为A。

例6: (1) 旧记载中还有一些稀奇的品种, 如细长如指形的“龙牙”、圆小如珠的“珍珠”, 因为缺少经济价值, 现在已经绝种了。 (2) 顶端叫果顶, 浑圆或尖圆。 (3) 蒂部周围微微突起, 称为果肩;有的一边高, 一边低。 (4) 荔枝呈以及形、卵圆形或圆形, 通常蒂部大, 顶端稍小。 (5) 两侧从果顶到蒂部有一条沟, 叫做缝合线, 显隐随品种而不同。

A、 (1) (5) (3) (2) (4) B、 (5) (1) (4) (3) (2)

C、 (4) (3) (2) (5) (1) D、 (4) (2) (3) (1) (5)

本题是从《南州六月荔枝丹》这篇说明文中摘选的。从全段看是介绍荔枝形态的。而点出“荔枝”一词的只有第 (4) 句, 其余几句都承前省了主语“荔枝”, 所以, 第一次选择将第 (4) 句放在首句。具体介绍外形是按整体到局部这样的逻辑顺序排列的。 (4) (3) 两句体现整体, (2) (5) 两句介绍“顶端” (果顶) 和“两侧”, 属于部分。从整体到局部说明顺序是由大到小, 从上到下到侧, 因而第三次选择应为 (4) (3) (2) (5) 。而第 (1) 句是介绍“稀奇”品种, 从全段来看是从一般 ( (4) (3) (2) (5) 句) 到特殊 ( (1) 句) 的顺序, 所以第 (1) 句应排在本段末句。综上分析, 正确答案应为C。

遇到按逻辑顺序排列的练习题, 则要抓住文段内容上的内在联系, 结构上的内外, 整体与局部以及变化上的动静、光线上的明暗、认知上的浅深等因素来判定。

四. 注意知识的综合性和迁延性

例7: (1) 《死水》的文字色彩浓烈。 (2) 如:“再让油腻织一层罗绮, 霉菌给他蒸些彩霞。” (3) “也许铜心要绿成翡翠, 铁罐上锈出几瓣鲜花”; (4) 它是以美的词藻写丑。

A、 (1) (2) (3) (4) B、 (2) (3) (4) (1)

C、 (1) (4) (2) (3) D、 (1) (4) (3) (2)

思考的第一步:从语段上看, 是赞美《死水》文字色彩优美的。所以第 (1) 句应在句首。其次再索引诗句:“霞”, “花”押韵, 判断出 (2) (3) 两句, 不是 (2) 在前, 就是 (3) 在前。但 (2) 句的“再”说明该句应在后。分号标点可以判断 (3) 在 (2) 前。再看第 (4) 句, 如果放在最后, 则该文段应为总——分——总结构。然而, 该文段从形式上看是赞其“色彩浓烈”的, 但从内容上来看, 却是把“丑”的事物“油腻和霉菌”、“铜绿”和“铁锈”——写美的, 所以它应该排在 (1) 句的后面, 同为总起句。本题的答案为D。

从例7我们不难看出该题综合性很强, 要鉴别逻辑上的总分关系, 还要检测诗句的重组能力, 了解诗歌的韵律, 以及分析文段内容与形式的关系。

这里我们需强调的是:因其难度, 这种练习题, 并不局限在课文里选题, 而多在课文外选题, 注意了知识的迁延性。因其深度, 排序题的练习, 多安排在高中阶段。那种单纯的按时间或空间顺序的练习题并不多见。即使是以时间或空间顺序为主的练习题, 也兼及其它顺序, 如例1到例4题。有些综合性强的选题, 我们难以区分究竟以什么顺序为主。因其广度, 有些练习题还涉及多种知识, 写作手法, 表现技巧等。如例1到例7, 文章的体裁、诗句的融合、诗歌的韵脚、文句的排比甚至标点符号的考查都有体现。

最简单的排序算法 篇8

冒泡排序很简单,其原理也比较容易理解,但冒泡排序效率很差。世上也存在着许多效率很高的排序算法,但它们又都比较难理解。本文将介绍一种简单又“高效”的排序算法——珠排序, 大家不妨一起来玩玩。

空间站里玩排序

之所以要在“高效”两个字上打引号,是因为珠排序需要特殊的硬件支持。怎么个特殊法呢?为了方便说明问题,请想象在某个失重的空间站里,有一系列排列整齐、从1到n依次编了号码的透明管子,在管子里放入小球,小球的直径与管子横截面的直径相仿,只是略小一点,放球的规则如下:

1预先设定一系列未排序的数字, 如5、4、8、1、2、3、6、4。

2按预先设定的数字往管子里放球,如果是5,就放5个球,但并不是把5个球都放到1个管子中,而是依次放入1号到5号管子。如果是4,就把4个球依次放入1号到4号管子(如图1A、B)。

3在空间站的无引力真空环境中, 所有球都浮在空中,这时候若忽然施加重力,如用离心力模拟重力,于是所有的球都掉到了管子的底部,这时如果从侧面数球的个数,就能发现,先前的未排序数字,此时已经排序完成了(如图1C、D)。

这个实验当然不一定非要在太空站里做,把原本水平放置的管子竖立起来,产生的效果也是一样的。

记事本里玩排序

即便没有管子和小球,也可以在记事本中模拟珠排序的过程。

假设预设的未排序的数字为5、 4、8、1、2、3、6、4,第一个数字是5,则在记事本的第一列(注意是列而不是行) 写5个“1”,然后再在“1”下面多补充一些“0”,因为需要排列的数字最大是8,用8减去5得3,则最少补充3个“0”, 当然多补充点“0”是没关系的,接着要排序的数字是4,则在记事本第二列写4个“1”,再补充4个“0”,第三列8个“1”……以此类推(如图2)。

把所有的1和0按次序排列好后,用记事本中的“编辑—替换”功能,将文本中的“10”全部替换成“01”,反复这个全部替换过程,当不再有可替换的对象时,排序也就完成了(如图3)。 就这样,不用写一行代码就完成了排序。当然,若想要一本正经地把珠排序的代码写出来,也不是特别困难的事情, 这个任务就交给有兴趣的朋友自行探索了。

数值排序算法比较分析 篇9

按照排序的数据规模，可以将排序分为内部排序和外部排序两类[3]。内部排序就是将待排序序列全部加载到内存中一次性排序的过程。外部排序是数据规模超过内存容量而产生的一种多次读取外存数据到内存，分别进行排序后最终整合的排序过程。外部排序本质上是多次内部排序加上多次外存读取的融合，因此，内部排序是排序问题的基础和核心。常用的内部排序算法按照基本思想可以分为插入排序、交换排序、选择排序、归并排序和基数排序等几类，在此选取了常见的7种排序算法，冒泡排序、快速排序、直接插入排序、希尔排序、堆排序和基数排序进行比较分析。

在排序方面的研究和文章已经存在[2,3,4,5]，但是这些研究和数据都是基于C平台和整形数据，而实际应用中Java平台和浮点型数据应用较多。鉴于目前Java计数的广泛应用，在Ja va平台上用7种常用的数值排序算法测试不同规模的整型数据和浮点型数据，为采用何种排序算法提供参考。

1 算法描述和分析

算法描述中的待排记录均用R{R1,R2,R3,R4,R5….Rn}表示，n表示数据规模。

1.1 冒泡排序

1.1.1 基本思想

冒泡排序是一种交换排序算法。基本思想是依次从头到尾依次遍历含有n个元素的待排记录R，比较相邻元素，例如R1,R2，若R1>R2则交换两元素位置。每遍历一次选出最大的元素并且置于排序记录尾位置，为一次冒泡过程。接着排序前n-1个元素序列，进行相同的比较交换过程，选出最大元素置于序列的次尾位置。依次类推，直到待排序列有序位置。通常冒泡排序中会有一个哨兵来记录是否发生了元素交换，当一次遍历中没有发生元素交换时，表明序列已经有序。

1.1.2 时间复杂度

若有n个待排元素，第1次遍历的比较次数为n-1,第二次遍历为n-2,依次类推，第i次为n-i，时间复杂度表示为

冒泡排序的最差时间复杂度为O(f(n))=O(n2)，最优时间复杂度为O(f(n))=O(n)

1.1.3 空间复杂度与稳定性

冒泡排序中只是在元素交换过程中需要一个辅助空间，空间复杂度为O(1)。元素交换只发生在R1>R2的情况下，保持了原序列相同元素的前后位置，所以冒泡排序是一种稳定的排序算法。

1.2 快速排序

1.2.1 基本思想

快速排序是一种交换排序算法。首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面的序列Rleft，所有比它大的数都放到它后面序列Rright，这个过程称为一趟快速排序。接着分别对Rleft和Rright进行同样的快速排序，重复相同的操作，直到序列有序为止。

1.2.2 时间复杂度

每次快速排序是将待排序列分成两个规模较小的子序列接着进行快速排序，即二分问题，形似二叉树问题。其时间复杂度是由快速排序的次数和排序规模决定的，也就是二叉树的树高和元素的个数。

根据树结构理论，快速排序的最优，也是平均时间复杂度为O(f(n))=O(nlog2n)，最差时间复杂度为O(f(n))=O(n2)。

1.2.3 空间复杂度和稳定性

每执行一次快速排序都需要一个辅助空间，若采用递归方式实现需要额外的压栈空间，快速排序的空间复杂度即为执行快速排序的次数，为O(nlog2n)。在排序过程中，不能保证原序列中相同元素的前后位置，是不稳定的。

1.3 插入排序

1.3.1 基本思想

插入排序在这里指直接插入排序，直接插入排序是最简单的插入排序算法。基本思想是把待排记录R按其关键码值的大小逐个插入到一个已经排好序的有序序列RinOrder中，直到所有的元素插入完为止，得到一个新的有序序列。

1.3.2 时间复杂度

插入排序的时间主要消耗在查询待排元素Ri的插入位置过程中，一般采用从后向前顺序遍历序列Rin Order，找到插入位置j,顺序移动Rj(Ri>=Rj）后的元素并将Ri插入到原Rj处。时间消耗由排序序列长度n和和待排元素在原序列中的位置i决定，

最差时间复杂度O(n2)，最优时间复杂度O(n2)，平均时间复杂度O(n2)。

1.3.3 空间复杂度和稳定性

插入排序只需要一个辅助空间，并且插入过程保持了原序列相同元素的前后位置。空间复杂度为O(1)，稳定的排序算法。

1.4 希尔排序[6]

1.4.1 基本思想

希尔排序是一种改进的插入排序算法。首先选取一定的增量d(d<n)将待排记录R进行分组，形成若干个类似分组Ri{Ri,Ri+d,….Ri+jd|i+jd<=n}。在每个小分组里面进行直接插入排序，使得分组记录有序。接着逐渐减小d值，重复相同操作，直到增量d为1，待排记录R有序。

1.4.2 时间复杂度

希尔排序时间复杂度和增量的选取有关，一般采用希尔增量，即初次增量选取待排记录的一半，以后每次减半，直到增量为1。选取希尔增量的时间复杂度为O(n2)，希尔排序时间复杂度的下界为O(nlog2n)。

1.4.3 空间复杂度和稳定性

希尔排序只需要一个辅助空间，空间复杂度为O(1)。希尔排序反复执行了多次插入排序，相同的元素可能在各自的插入排序中移动，所以，插入排序是不稳定的排序。

1.5 堆排序

1.5.1 基本思想

堆排序是一种选择排序算法。堆排序将待排记录R根据元素下标关系看作一棵完全二叉树，并且具有根元素最大或者最小性质，简称大根堆或小根堆。每次排序首先调整大根堆或者小根堆性质，而后交换堆顶R0与最后一个元素Rn(n为待排记录长度，随着排序过程递减)位置，接着在余下待排记录R{R0,…,Rn-1}上进行相同的排序操作，直到只有一个元素R0，排序完成，记录有序。

1.5.2 时间复杂度

堆排序的时间主要消耗在大根堆或小根堆的调整上。堆调整过程是相当于一次完全二叉树的查询过程，整个过程的复杂度为O(nlog2n)。

1.5.3 空间复杂度和稳定性

堆排序过程只需要一个辅助空间用来存放交换过程中的临时变量，但是在交换过程中不能保证原纪录中相同元素的前后位置。空间复杂度为O(1)，算法不稳定。

1.6 归并排序

1.6.1 基本思想

归并排序是一种采用分治思想、建立在归并操作上的有效排序算法。归并操作将已经有序的子序列合并，得到完全有序的序列。通常以每个子序列长度为1开始，两两合并成长度为2的序列，再继续进行归并操作，直到待排记录R完全有序。

1.6.2 时间复杂度

以二路归并为例，每次归并过程都是将两个有序子序列合并为一个有序序列，时间消耗是一个递推的过程。和其他二分递归问题类似，时间复杂度为O(nlog2n)。

1.6.3 空间复杂度和稳定性

归并排序过程需要和待排记录R等大的辅助空间，但是保持了原序列相同元素的前后位置关系。所以，归并排序的空间复杂度为O(n)，稳定的排序算法。

1.7 基数排序

1.7.1 基本思想

基数排序是一种分配式排序算法，也称作桶子法。基数排序根据键值的部分信息（例如数值最高位）将待排记录R分组，而后将分组后的待排记录排序并且按序组合，再按照键值的部分信息（例如数值次高位）分组，继续按序组合。重复相同的过程，直到遍历全部键值信息（例如数值最低位），待排记录R即有序。

1.7.2 时间复杂度

基数排序的时间复杂度和待排记录长度n、采用的键值部分信息（简称关键码d）以及d取值范围r有关，复杂度为O(d(n+r))。空间复

1.7.3 空间复杂度和稳定性

基数排序需要和待排记录R等大的辅助空间来存储原始排序记录，另外仍然需要rd个空间来辅助计数排序的过程。空间复杂度为O(rd+n)，保持了原序列相同元素的顺序，是稳定的排序过程。

2 实验与结果

本实验使用一台装配32位Win7系统，4G内存，core i5CPU的电脑，在Eclipse开发环境下进行。为了验证基本数据类型、数据泛型封装和代码实现（泛型）对算法的影响，实验首先采用正序和逆序的int型序列对算法进行测试，而后调用Java里面的随机函数生成随机待排序列进行实验。

2.1 算法性能测试

为了测试算法实际运行效率实验选取1000-50000间隔为1000的49组正序、逆序、随机的int类型数据进行5轮测试，计算每种算法的时间消耗平均值，绘制得到图1正序序列排序时间消耗图、图2逆序序列排序时间消耗图和图3随机序列排序时间消耗图。

对比3组实验对比折线图，可以看出各个排序算法实际效率和理论分析基本一致。BubbleSort、InsertSort和ShellSort表现出了对序列顺序的敏感性。HeapSort和MergeSort时间消耗比理论要高，甚至在逆序下耗时超过BubbleSort，其原因在于算法实现过程中引入了过多的条件判定操作、分配内存操作以及寻址操作，这些操作增加了算法的复杂度，致使程序本身的复杂度增大。至于HeapSort和BubbleSort效率相当，与序列是随机序列以及HeapSort操作破环了堆的随机性[8]存在关系。

2.2 测试序列数据类型对排序影响

为了观察基本数据类型是否影响算法效率，实验分别选取1000-50000间隔为1000的49组正序、逆序、随机的int、double基本数据类型数据进行5轮测试，计算每种算法的时间消耗平均值，得到表1实验结果。

算法的性能稳定性指的是随着数据规模的改变，时间消耗是否稳定变化，表现为时间消耗折线图的走势是否平滑。根据实验结果显示，BubbleSort、QuickSort和InsertSort性能稳定，其余算法稳定性较差。

基本数据类型影响着排序算法的效率，排序相同规模下的浮点型数据和整形数据，浮点型数据消耗略大于整形数据。

2.3 Java内部封装类对排序算法的影响

为了测试Java内部封装类[9]对排序算法的影响，实验同样进行了5次。每轮实验仍然调用Java随机函数生成50组范围1000-51000间隔为1000的实验数据，类型为Integer、int、Double和double，测试明确指定数据类型的7种排序算法。而后，计算5轮实验时间消耗的平均值，得到表2的实验结果。

根据表2中实验数据，可以看出Java内部的封装数据类型对排序算法存在影响，程度因算法而异。InsertSort和Radix Sort受影响较大，封装数据类型和基本类型时间消耗比例达到了4:1,MergeSort受影响最小，浮点类型封装数据Double排序效率超过了基本数据类型double，产生这种现象的原因和Jav对象的存储机制和内存的分配方式有关。总结起来就一般情况而言，封装数据类型会加大排序算法的开销，时间开销是基本数据类型的1.2到4倍。

2.4 泛型编程方式对排序算法影响

为了测试采用泛型[7]方式编写程序对排序算法效率影响，实验进行了5轮重复测试。每轮实验调用随机函数生成50组范围1000-51000间隔为1000的实验数据，数据类型为Inte ger和Double，测试采用泛型方式和非泛型方式编写的7种排序算法。而后，计算5轮实验时间消耗的平均值，得到表3的实验结果

根据表2的实验结果，可以得到采用泛型编写方式对算法效率存在影响，影响程度依据算法的不同存在差异。Insert Sort和HeapSort影响程度较大，MergeSort基本不受影响，产生这种差距的原因和Java自身的运行机制存在一定的关系。总体来说，采用泛型编程方式会加大排序算法的时间开销，约为非泛型编程的1.5-2.4倍。

3 结果分析

通过以上的实验结果，可以得出如下结论：

(1）排序算法的效率在很大程度上由算法的思想决定。

(2）算法的实际运行效率也依赖于书写代码的复杂度以及采用的基本操作类型等外界因素。

(3）排序算法效率和基本类型有关，排序相同排序规模的浮点型数据比整形数据耗时。

(4）使用Java内部封装类会影响排序算法效率，排序相同规模数据的时间消耗增加0.2-3倍。

(5）采用泛型方式编写程序会增加排序算法的时间消耗，为非泛型方式的1.5-2.4倍。

(6）根据实验数据显示，综合多种因素的影响，QuickSor和ShellSort表现出良好运行效率，符合[8]中的描述。

4 结语

排序算法的效率是由多种因素决定的，本实验验证了排序记录数据类型、数据封装以及代码的编写方式对排序算法的影响。但是影响算法效率的因素还有很多，在选择排序算法时应该综合考虑各种因素，以便做出最合理选择。

摘要：排序是计算机科学领域的一个基本问题。从算法时间复杂度、空间复杂度和稳定性的角度对常见的7种内部数值排序算法进行了理论分析。在Java平台下测试了7种算法的执行效率,指出了算法的执行效率不仅和算法设计思想相关,基本数据类型、数据封装,以及代码实现方式都影响算法的执行效率。同时进行了实验对比数据,为排序算法的选择提供一定的参考。

关键词：内部排序算法,效率,数据类型,数据封装

参考文献

[1]Dongarra J.The top 10 algorithms[J].IEEE Computing in Science&Engineering,2000,2(1):22-23.

[2]江燕,周军,等.内部排序算法的表分析[J].电脑编程计数与维护,2014,12:23-24.

[3]吴伟娜,等.常用排序算法的比较分析[J].电脑知识与技术,2013,03:2416-2147.

[4]张静.常用的排序算法的分析与比较[J].河西学院学报,2010,02:26.

[5]淦艳,等.五种排序算法的性能分析[J].重庆文理学院学报,2016,06:45-50.

[6]杨智明.希尔算法实现与分析[J].软件与开发,2010,02:13-14.

[7]Joshua Bloch.Effective Java[M].北京.机械工业出版社,2009:97-102.

[8]Mark Allen Weiss.数据结构与算法分析:Java语言描述[M].北京.机械工业出版社,2008:77-125,183-219.