常用加密算法比较研究

常用加密算法比较研究（共3篇）

常用加密算法比较研究 篇1

0 引言

无线识别射频技术 (RFID) 具有非接触扫描, 体积小型化, 抗污染能力强, 可重复使用, 穿透性强, 识别距离远等优点, 在物流监管, 门禁系统, 电子自动收费等领域得到了迅猛地发展[1]。它的信息安全问题也越来越受到人们的关注[2]。以往经典的加密算法如高级加密标准 (AES) , 侧重的是提供高级别加密性能, 而没有过多的考虑硬件资源开销问题[3]。显然, 在RFID这种硬件资源极端受限的环境下, 采用高性能的加密算法是不明智的选择。

轻量级 (lightweight) 加密算法在密钥长度, 加密轮数等方面作了改进, 使之对处理器计算能力的要求和对硬件资源的开销均有不同程度上的降低, 却足以提供所要求的加密性能[4]。在很多RFID低成本无源电子标签 (如RFID门票) 中, 所进行的加密算法只是为了换取一个时间代价, 即只要能够保证标签内的信息在所要求的一个时间段内安全即可。

流密码中的RC4算法和分组密码中的PRESENT算法, 都属于对称加密算法即加密和解密使用相同的密钥, 故能较容易做到算法的轻量化, 而椭圆曲线加密算法是不对称加密算法[5,6,7]。本文利用ATmaga⁃32单片机在AVR Studio.4仿真平台上, 对这三种算法的运行效率和密码破译时间进行分析比较。得出在硬件资源同样极端受限的环境下, 椭圆曲线加密算法的运行效率要高于另外两种, 所生成的密码最难被破译, 证明了非对称加密算法同样可以做到轻量化。

1 算法介绍

1.1 椭圆曲线加密算法

1.1.1 椭圆曲线概述

椭圆曲线加密算法属于公开密钥加密算法, 加密和解密使用不同的密钥。椭圆曲线定义:椭圆曲线是指在射影平面上满足Weierstrass方程的一条光滑曲线和一个无穷远点0∞的集合[8]。本文所选取的这条光滑曲线可以表示为E:Y2=X3+a X+b, 此时方程的特征值为大于3的素数。点加运算是椭圆曲线上一条很重要的运算规则, 具体规则如下:任意选取椭圆曲线上两点P, Q (若P, Q两点重合, 则做P点的切线) 做直线交于椭圆曲线的另一点R′, 过R′做y轴的平行线交于R, 则有P+Q=R。图1给出了椭圆曲线的加法运算法则。根据这个法则, 可以知道椭圆曲线内无穷远点0∞与曲线上任一点P有:0∞+P=P, 故把无穷远点0∞称为零元。同时可以得出如下结论:如果椭圆曲线上的三个点A, B, C, 处于同一条直线上, 那么他们的和等于零元, 即A+B+C=0∞。k个相同的点P相加, 记作k P。如, P+P+P=2P+P=3P。

1.1.2 椭圆曲线加密流程

首先确定一个有限域Fp, 这个域只有p (p为素数) 个元素, 在这取p=79。

(1) 用户A在这个有限域中选定一条椭圆曲线Ep (a, b) , 并取椭圆曲线上一点, 作为基点G。

(2) 用户A在1~p-1之间随机选择一个素数作为私有密钥k, 并根据加法则, 生成公开密钥K=k G。

(3) 用户A将Ep (a, b) 和点K, G传给用户B。

(4) 用户B接到信息后, 将待传输的明文编码到Ep (a, b) 上一点M, 并产生一个随机整数r (r<n) 。

() 用户计算点C1=M+rK;C2=r G。

(6) 用户B将C1, C2传给用户A。

(7) 用户A接到信息后, 计算C1~k C2, 结果就是点M, 再对点M进行解码就可以得到明文。在这个通信过程, 偷窥者只能看到Ep (a, b) , K, G, C1, C2, 而通过K, G求k或通过C2, G求r都是十分困难的。这正是椭圆曲线加密所基于的数学难题, 因此偷窥者无法得到用户A, B间传送的明文信息。本文选用密钥为79 b的椭圆曲线加密算法。图2给出椭圆曲线算法的加解密流程。

1.2 流密码加密算法

1.2.1 流密码概述

流密码 (stream cipher) 也称为序列密码, 按位或字节对数据流进行处理, 加密和解密使用相同的密钥, 是对称密码算法的一种。本文选取的是流密码中的RC4算法。RC4算法是一个面向字节操作、密钥长度可变的流密码 (stream cipher) 。算法的基本原理可描述为:对于n位长的数据, 有共N=2n个可能的内部置换状态矢量S=S[0], S[1], …, S[N-1], 这些状态是保密的。密钥流K由S中的2n个元素按一定方式选出一个元素而生成, 每生成一个密钥值, S中的元素就重新置换一次, 置换后的S自始至终都包含从0~N-1的所有n位比特数, 这体现了“一次一密”的加密体制[9]。

1.2.2 流密码加密流程

内部状态矢量S的初始化:把S中的元素按升序从0~N-1赋值, 即S[0]=0, S[1]=1, S[N-1]=N-1。同时建立一个临时矢量T, 如果密钥K的长度为N字节, 则将K赋给T否则, 若密钥长度为keylen字节则将K的值赋给T的前keylen个元素, 并循环重复用K的值赋给T剩下的元素, 直到T的所有元素都被赋值。

用类C伪代码可表示如下:

密钥流的生成:矢量S一旦完成初始化, 输人密钥就不再被使用。密钥流的生成是从S[0]~S[N-1], 对每个S[i], 根据当前S的值, 将S[i]与S中的另一字节置换。当S[N⁃1]完成置换后, 再从S[0]开始继续重复操作。用类C伪代码可表示如下:

加密时, 将k的值与下一明文字节异或;解密时, 将k的值与下一密文字节异或。

1.3 PRESENT算法

1.3.1 PRESENT算法概述

PRESENT是分组密码, 分组大小是64位, 根据密钥的大小可分为PRESENT⁃80和PRESENT⁃128两种参数版本, 密钥长度分别为80位和128位, 因此, 在这里选用PRESENT⁃80。

1.3.2 PRESENT算法流程

图3为PRESENT⁃80的算法流程图。

PRESENT⁃80算法要经过31轮加密, 每一轮都经过一个SP结构, 每个SP结构都是由add Round Key、s Box⁃Layer和p Layer三步操作组成[10]。add Round Key操作是将PRESENT⁃80的分组数据与轮密钥Ki按位进行异或操作;s Box Layer是一个非线性置换操作, 在PRESENT⁃80中由一个4位到4位的S盒 (S⁃box) 实现。表1给出了S⁃box的16进制表示;

p Layer操作是一个位变换操作, 用于改变PRES⁃ENT当前分组数据的顺序, 把第i位变为第P (i) 位, 表2给出了p Layer具体操作。

密钥调度:PRESENT⁃80的初始密钥存放在一个80位的密钥寄存器 (Key Register) 里, 表示为K79K78…K0, 然后取其高64位的值作为轮密钥Ki=k63k62…k0 (1≤i≤32) 。在第i轮加密中, 轮密钥Ki=k63k62…k0=K79K78…K16该轮加密完成后, 密钥寄存器更新, 产生新的轮密钥如此完成31轮的PRESENT⁃80加密。

2 实验与分析

2.1 实验设计和实现

在微处理器平台的选择上, 希望微处理器既能够适用于低功耗的RFID系统中, 又能够很好地对上述三种算法进行实现。ATmega32单片机是Atmel公司推出的一款高性能、低功耗AVR高档微处理器。芯片内部集成了较大容量的存储器和丰富强大的硬件接口电路, 但由于采用了小引脚封装 (为DIP28和TQFP/MLF32) , 所以其价格相对比较便宜, 非常适用于成本较低的RFID系统[11]。另外, ATmega32含有32 KB的内存容量, 能够完全满足这三种加密算法的内存需要。所以可以把ATmega32单片机作为目标平台。

开发工具选择方面, 仿真工具选用AVR Studio4, 编译工具选用Win AVR (GCC) , 并把后者添加前者内, 这样就可以在同一个界面下完成对算法编译和仿真。为了数据的准确性, 所有仿真都执行多次, 取其平均值。

2.2 算法性能评估与比较

本文从三个方面对这三种算法进行评估和比较:一是评估它们运行时的内存开销, 来比较它们各自对硬件资源的需求;二是评估执行这三种算法所需要的机器周期, 来比较这三种算法的运行效率;三是评估三种算法各自的密码破译时间, 来比较它们的密码安全强度。

2.2.1 内存开销比较

算法的内存开销, 主要是指算法在完成一次加密和解密的过程中所需要的内存大小[12]。表3给出了这三种算法在完成一次加密和解密的过程中所需要的内存大小, 单位为字节。为了更直观的比较, 在图4中以三维柱状图的形式给出。

从表3可以看出, 三种算法的代码开销都没有超过总内存的1 10, 佐证了这三种算法的轻量级性, 而流密码中的RC4算法的代码开销尤为突出, 这与其密钥短小有莫大的关系。RRESENT的代码稍大, 主要是因为算法过程中的位置换运算消耗内存大。

2.2.2 算法的运行效率

算法的运行效率, 是指算法完成一次加密和解密所需要的机器周期, 它反应了算法对能量的运用效率。在能量及其有限的RFID系统中, 算法的运行效率显得尤其的关键。在此我们把CPU工作频率设定在8 MHz下, 并且为了能够完全覆盖这三种算法, 选取一个256位的测试向量进行。表4给出了这三种算法各自的执行时间, 单位是机器周期。

为了更直观, 图5给出了三种算法完成一次加密和解密所需要的机器周期的比较。

可以明显的看出, 在算法的运行效率上椭圆曲线算法要优于另外两种算法, 这与在仿真过程中, 软件只运行椭圆曲线加密算法的低计算开销部分有关。而在运行RC4算法和PRESENT⁃80时, 都要进行位置换和位赋值的操作, 这在硬件上实现可能没有任何性能开销, 所做的只是将电路的对应位置相连, 但是在软件上实现就显得困难多。

2.2.3 算法安全强度比较

算法的破译, 称为密码分析, 针对这三种加密算法选用各自最有效的密码分析方法分别对其进行密码分析, 用破译算法所耗时间和所占的空间, 来衡量这三种算法的密码安全强度。

椭圆曲线加密算法, 加密和解密所用密钥是不同的, 对此采用密钥穷尽搜索方式[13]。在一个有3 000台计算机的网络中进行密钥穷尽搜索的计算, 使用粗略的时间估算原理可以得出破解椭圆曲线密钥需要几小时到几天的时间, 尽管如此, 这种加密强度对于低成本的RFID系统来说还是绰绰有余的, 因为召集这样多的人力和计算机资源来破解这种低成本的电子标签是得不偿失的。

流密码中的RC4算法, 是对称加密算法中的一种, 采用暴力攻击方式对其进行破解[14]。暴力攻击RC4算法, 必须知道密文某几个字节对应的明文, 使之成为已知明文攻击, 知道明文后, 通过逐一假设密钥尝试解密密文与已知明文进行比较, 若解密结果与明文匹配, 那么正确的密钥就已经找到。找到了加密密钥, 剩余的密文就可以完全解密。用暴力攻击中的全查表法, 破译RC4算法所需空间为10 TB, 所需时间几乎为0。可以看出虽然RC4算法的代码所占内存小但是安全性却是比较低的。

对于分组密码中的PRESENT算法, 采用代数分析对其进行攻击[15]。所谓代数分析就是将一个密码算法的计算过程构造成一组代数方程, 通过求解这组方程中的未知元来获取该密码算法中的密钥信息。在PRES⁃ENT算法的代数分析中, 所需的空间可以由单台个人计算机提供, 所需要的时间代价是几天, 这些时间代价主要用在求解方程组上。为了便于比较, 表5给出这三种算法的破译代价。

尽管在衡量破译时间上使用的是粗略估算时间原理, 但这并不妨碍对这三种算法安全强度的分析, 因为RFID系统本身成本就很低, 在其中进行加密运算, 很大程度上就是为了换取一个安全的时间代价。从表4可以看出:流密码中的RC4算法是最好破译的, 这与它的算法简单、密钥短小、算法按位操作有关;椭圆曲线算法和PRESENT⁃80算法所换取的时间代价是相似的, 但是在破译所需空间上, 椭圆曲线算法却要比PRESENT⁃80算法大很多, 可以这样说, 椭圆曲线加密算法的安全强度胜过PRESENT⁃80算法。

3 结语

对于RFID这种硬件资源极端受限的系统中, 就如何在算法的加密性能与硬件资源消耗之间取得一个最佳的权衡。本文选取了不对称加密算法中的椭圆曲线加密算法, 并选取对称加密算法中RC4加密算法和PRESENT⁃80算法与之进行比较。对它们在微处理器平台上进行仿真分析, 并比较它们各自的内存消耗, 运行效率和密码破译难度。从最后的实验数据可以看出, 运行这三种加密算法所耗用的内存都没有超过微处理器内存的10%, 证实了这三种算法都属于轻量级的加密算法;在算法的运行效率上, 椭圆曲线加密算法所需要的机器周期要比另外两种算法少。

在加密强度上, 椭圆曲线加密算法作为不对称加密算法所表现出的密码强度更是两外两种算法不能企及的。在硬件资源极端受限的环境下, 椭圆曲线加密算法在内存开销、运行效率和密码的安全强度之间做到了较好的兼顾, 不对称加密算法同样也可以做到算法的轻量化。

摘要：随着无线射频识别 (RFID) 技术在各个应用领域的迅猛发展, 轻量级 (lightweight) 加密算法日益受到人们的关注。在RFID中硬件资源是极端受限制的, 为了在算法加密性能与硬件资源开销间得到一个好的权衡, 把椭圆曲线加密算法 (ECC) 与流密码加密算法中RC4算法, 分组加密算法中的PRESENT算法, 进行分析比较。并选取Atmega-32微处理器在AVR Studio仿真平台上进行分析比较。实验获得了这三种算法在算法运行效率、密码安全强度和硬件资源开销间的比较结果。得出, 在硬件资源同样极端受限的环境下, ECC所表现出的运行效率和密码安全强度是其他两种算法所不能比拟的, 证明了非对称加密算法也可以做到轻量化。

关键词：轻量级加密,RFID,椭圆曲线加密,流密码,PRESENT加密算法

常用加密算法比较研究 篇2

关键词：混沌序列,加密算法,算法安全性

0 引言

由于图像和多媒体数据信息量极大, 能够更加直观的表达, 因此他们在人们数据利用和传递中占有举足轻重的地位。进入21世纪, 越来越多的数据在网络中传递, 数据安全问题日益严重。由于图像和多媒体信息数据量巨大, 使用传统的加密方法已经不能满足需求, 混沌序列的出现, 使得这些问题迎刃而解。典型的混沌序列有Logistic映射、二维广义猫映射 (Cat Map) 、三维统一混沌系统 (Three Dimensional Unified Chaotic System) 、超混沌 (Hyper Chaos) 等, 由于超混沌序列还在不断的更新完善, 本文主要分析前三种序列用于图像加密的优劣点。

1 改进的Logistic图像加密算法

1.1 Logistic映射模型

Logistic映射[1]是经典混沌映射的典范, 也是混沌序列发展的奠基者, 它蕴含了现代混沌理论的基本思想, 是混沌序列的雏形。它的出现为混沌的研究和发展开辟了先河。Logistic映射系统定义如下:

当μ达到极限μ∞=3.5699456时, 系统的稳态解是周期2∞的解, 即3.569945<μ≤4时, logistic映射呈现混沌状态[1]。

1.2 改进的Logistic映射模型

Logistic序列后来被证明并不是一致性分布序列, 于是有人对它做了改进变换, 从而得到随机性更好的序列, 变换后的Logistic映射数学模型如下:

1.3 加密算法描述

使用改进后的Logistic序列进行算法设计时, 由式 (2) 产生两个混沌序列f1 (x) 和f2 (x) , 分别异或图像的奇数点和偶数点, 得到密文。

1.4 实验结果分析

(1) 密钥空间分析

加密时使用了2个序列, 若每个序列取2个系统参数, 于是就有了4个系统初值, 如果所有参数都使用有15位小数的双精度数, 则每个参数取值空间有1015, 四个参数的组合空间是1015*4=1060, 密钥空间巨大。率增加, 且趋。总深4.0m000 mg/L。运设置水泵一台组装示意图

(2) 对密钥和明文的敏感性分析

在试验验证中得知, 解密时, 密钥有10-10的误差将导致不能准确解密, 若密文有一个像素的灰度值有变化, 也会导致解密结果误差巨大, 完全不能解密。由此可知该算法具有对初值的极端敏感性。

(3) 统计特性分析

在图1的直方图中可以很直观的看出, 明文的像素灰度值分布很不均匀, 而密文的像素灰度之在区间[0, 255]均匀分布。这说明明文图像和密文图像之间的相关性非常小, 大大降低了已知明文的攻击可能性。

(4) 解密准确性分析

试验验证时, 在Mat Lab中将原始图像矩阵和解密后的图像矩阵相减, 得到了零矩阵, 说明解密图像和原始图像没有任何差异。

2 二维广义猫映射加密算法与Logistic加密算法比较

2.1 二维广义猫映射模型

Arnold最早提出了猫映射[2], 其数学模型如下:

猫映射经过变换后, 可得到式 (4)

2.2 加密算法描述

加密算法设计时, 取三组p, q, n, 分别用式 (4) 产生的三组坐标 (xi, yj) , 对原始图像A的R、G、B三基色的坐标RA (xi, yj) 、GA (xi, yj) 、BA (xi, yj) 进行置换得到新的坐标值RA1 (xi, yj) 、GA1 (xi, yj) 、BA1 (xi, yj) 。合成三个新矩阵R1、G1、B1得到密文图像A1。

2.3 实验结果分析

(1) 算法安全性分析

取三组不同的初值, 二维广义猫映射有更大的密钥空间, 而且该映射的复杂度较Logistic高许多, 此算法的安全性高于Logistic加密算法。

(2) 加密性能分析

由于改进的Logistic加密算法是用混沌序列与图像的像素值进行异或替代的, 数据计算量非常大。使用Mat Lab7进行实验时, 使用配置为PⅥ2.8、512内存的计算机进行试验, 实验结果如表1所示。可以看出, 广义猫映射算法用时缩短了很多, 具有更高的时间效率。

(3) 统计特性分析

由于采用广义猫映射的加密算法, 只对明文图像的三基色的坐标进行了置换, 没有对图像的像素进行处理, 也就是没能改变图像的直方图。明文和密文的像素相关性较高, 无法抵御已知明文的攻击, 所以, 此算法仍然不是很理想。

3 广义猫映射与三维统一混沌系统结合的加密算法

3.1 三维统一混沌系统的模型

Jin-hu等人[3]于2002年提出了一个新的三维混沌系统, Liu将Lorenz系统和Chen系统连接起来, 而Liu系统仅为其一个特例, 故称其为统一混沌系统, 其数学模型为[3]:

3.2 加密算法描述

算法设计时, 先将明文图像A使用广义猫映射算法进行坐标置换得到密文A1, 依次取A1中的像素A1 (xi, yi, k) , k=1、2、3。当k=1时, r=x (n) ;当k=2时, r=y (n) ;当k=3时, r=z (n) 。一次取A1的三个点, 分别使用序列r构造的三个密钥Intkey1 (k=1时) 、Intkey2 (k=2时) 、Intkey3 (k=3时) 进行像素灰度值异或替代, 直到所有的点的灰度值全都被替代。

3.3 实验结果分析

采用广义猫映射与三维统一混沌系统结合的加密算法后, 由于使用两种混沌序列分别对明文进行了坐标置换加密和像素值异或替代加密, 密钥空间更大, 序列也更加复杂。使用三维统一混沌系统对像素值异或替代后, 密文图像的像素灰度值也分布均匀了, 弥补了广义猫映射算法的不足。算法的安全性大大提高。

参考文献

[1]黄润生.混沌及其应用[M].武汉大学出版社, 2005, 12:134.

[2]Jorge A Gonzalez.Absolutely unpredieatable chaotic sequences[J].International Journalof Bifurcation and Chaos, 2000, 10 (8) :1867-1874.

常用排序算法的比较与分析 篇3

关键词：排序算法,时间复杂度,空间复杂度,算法实现

排序是计算机图形学、计算机辅助设计、模式识别、商业事物处理和日常生活等领域的一种重要操作,应用广泛[1],比如招生切线的分数排序、录取新生的成绩排序等,是计算机科学中的需要解决的重要问题之一。计算机程序中的排序是将一串任意序列的数据按照所要求的既定排序方式确定每个数据的具体位置的算法。在以上领域的数据处理时,程序的排序算法占了很大的比重。因此,排序算法既有广泛的应用价值,又有深刻的理论意义,曾经被列为对科学与工程计算的研究影响最大的十大问题之一[2],长期以来,人们为了各种领域的应用需要,研究、开发出了多种排序算法,这些算法有着各自的特点,实现方法不尽相同、速度也有差异,而且都在各自的应用领域扮演了重要的角色。

尽管已经开发出了各种不尽相同的排序算法,但是对排序算法的复杂度分析、算法的稳定度和数据结构的研究是解决许多实际应用的基础。该文从排序算法的基本概念、原理出发,分别从算法复杂度(时间、空间)、算法的稳定性和速度等方面进行分析比较,为具体领域应用的排序选择提供依据,使得执行效率更高。

1 排序的基本概念和算法分析的理论依据

1.1 排序的基本概念

排序:将数据表中没有规律、任意序列的数据元素按照既定的排序依据(关键码)排列成有一定规律的序列。

关键码:规定数据对象的其中一个属性域用作排序依据,从而区分对象,该属性域就是关键码。当数据表中各对象的关键码互不相同时,该关键码为主关键码;否则为次关键码;根据主关键码进行排序时,结果是唯一的,否者可能不唯一。

内部、外部排序:所谓内部排序是指排序时数据元素全部存放在j计算机的随机存储器(内存);外部排序是指排序时数据元素在内、外存之间不断移动(待排序的数据量很大,内存无法一次容纳全部数据)。

静态排序:所谓静态排序是指对数据元素经过比较和判断之后将对象移动到相应的位置。

动态排序:所谓动态排序是指给每个对象增加一个链接指针,对数据元素经过比较和判断之后不移动对象,而是修改对象的链接指针来达到元素之间顺序的改变。

1.2 算法分析的理论依据

一个问题可以采用不同算法来实现,算法的质量优劣直接影响算法的效率。算法分析的目的在于选择合适的算法和改进算法。评价一个算法的优劣主要是根据算法的复杂度(分为时间复杂度和空间复杂度),不同的排序算法,其复杂度也不一样,简单的算法程序,其执行效率也低;反之,复杂的算法程序,其执行效率相对来说也会比较高。

如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数,T(n)称为这一算法的时间复杂度。当问题规模n趋于无穷大时,如果存在某个辅助函数f(n),T(n)/f(n)的极限值为不等于零的常数,该时间复杂性的极限情形称为算法的渐近时间复杂度[3,4],记作O(f(n))。一般情况,在算法分析时对两者不予区分,经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度,f(n)是算法中频度最大的语句频度。常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),k次方阶O(nk),指数阶O(2n)。n越大,时间复杂度也越大,算法的执行效率就越低。例如:

sum=0;(1次)

for(i=1;i<=n;i++)(n次)

for(j=1;j<=n;j++)(n2次)

sum++;(n2次)

在上述交换i和j的算法中,时间复杂度为T(n)=2n2+n+1=O(n2)。

空间复杂度是指算法在执行过程中,根据n的规模大小需要临时占用的存储空间[3-4],和时间复杂度类似,也是问题规模n的函数,记作S(n)=O(f(n))。

一般情况,时间复杂度和空间复杂度是相互影响的,即:时间复杂度较好时(效率较高),空间复杂度的可能就变差(占用较多的存储空间),反之也一样。所以设计或选择一个好的算法时要考虑算法的时间复杂度和空间复杂度。

对于排序算法的稳定性,如果待排序的序列中存在两个或两个以上具有相同关键词的数据,排序后这些数据的相对次序保持不变,即它们的位置保持不变,则该算法是稳定的;如果排序后,数据的相对次序发生了变化,则该算法是不稳定的。

不仅仅是时间复杂度和空间复杂度之间相互影响,算法的所有性能之间或多或少都会相互影响。因此,当设计或选择一个算法时,尤其是大型算法,要综合考虑算法的各项性能:复杂度、稳定性、以及算法描述语言的特性,算法运行的机器系统环境等各方面因素。

2 排序算法的分析比较

2.1 插入排序

基本思想:每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数据元素依然有序;直到待排序数据元素全部插入完为止。关键在于将新的数据元素插入到已排序好的序列当中,包括找到应插入的位置、如何移动序列当中的数据元素。因此,插入排序又分为以下两种。

2.1.1 直接插入排序

基本思想:将欲插入的第i个数据元素的关键码与前面已经排序好的i-1、i-2、i-3、…数据元素的关键码进行顺序比较,通过这种线性搜索的方法找到第i个数据元素的插入位置,并且原来位置的数据元素顺序后移,直到全部排好顺序。

直接插入排序中,关键词相同的数据元素将保持原有位置不变,所以该算法是稳定的,时间复杂度的最坏值为平方阶O(n2),空间复杂度为常数阶O(1)。

该排序方法是对冒泡排序的改进,比冒泡排序大约快3倍,但是只适用于数据量较小(1000)的排序。

2.1.2 希尔排序

基本思想:根据不同步长对数据元素执行插入排序,刚开始数据非常无序时,步长最大,此时插入排序的元素个数很少,速度很快;数据基本有序时,步长很小,插入排序对于有序的序列效率很高。因此,如果元素为你的待排序序列,先取一个小于n的整数I作为步长,将所有元素分为I个子序列,在每个子序列中分别执行直接插入排序。然后缩小步长I重新划分子序列和排序,直到I=1,此时,相当于将所有元素放在一个序列当中。

刚开始,由于步长I很大,所以排序效率很高,当步长I逐渐减小时,序列也趋于有序化,所以排序效率也很高。因此,希尔排序时间复杂度会比O(n2)好一些,然而,多次插入排序中,第一次插入排序是稳定的,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,所以希尔排序是不稳定的。

相对来说,希尔排序比较简单,适用于小数据量(5000以下)的排序,比直接插入排序快2倍、比冒泡排序快5倍,因此,希尔排序适用于小数据量的、排序速度要求不高的排序。

2.2 选择排序

基本思想:每一趟扫描时,从待排序的数据元素中选出关键码最小或最大的一个元素,顺序放在已经排好顺序序列的最后,直到全部待排序的数据元素排完为止。

2.2.1 直接选择排序

基本思想:给每个位置选择关键码最小的数据元素,即:选择最小的元素与第一个位置的元素交换,然后在剩下的元素中再选择最小的与第二个位置的元素交换,直到倒数第二个元素和最后一个元素比较为止。

根据其基本思想,每当扫描一趟时,如果当前元素比一个元素小,而且这个小元素又出现在一个和当前元素相等的元素后面,则它们的位置发生了交换,所以直接选择排序时不稳定的,其时间复杂度为平方阶O(n2),空间复杂度为O(1)。

该算法和冒泡排序算法一样,适用于n值较小的场合,而且是排序算法发展的初级阶段,在实际应用中采用的几率较小。

2.2.2 堆排序

堆排序时对直接选择排序的一种有效改进,其基本思想是:将所有的数据建成一个堆,最大的数据在堆顶,然后将堆顶的数据元素和序列的最后一个元素交换;接着重建堆、交换数据,依次下去,从而实现对所有的数据元素的排序。完成堆排序需要执行两个动作:建堆和堆的调整,如此反复进行。

由基本思想可知,堆排序有可能会使得两个相同关键码的元素位置发生互换,所以是不稳定的,其平均时间复杂度为O(nlog2n),空间复杂度为O(1)。由于堆的不断建立和调整,所以堆排序不适用于数据元素较少的排序,但是对于n较大的情形,该算法能够表现出较大的优越性。因此,堆排序比较适用于数据量达到百万及其以上的排序,在这种情况下,使用递归设计的快速排序和归并排序可能会发生堆栈溢出的现象。

2.3 交换排序

基本思想:顾名思义,就是一组待排序的数据元素中,按照位置的先后顺序相互比较各自的关键码,如果是逆序,则交换这两个数据元素,直到该序列数据元素有序为止。

2.3.1 冒泡排序

基本思想:对于待排序的一组数据元素,把每个数据元素看作有重量的气泡,按照轻气泡不能在重气泡之下的原则,将未排好顺序的全部元素自上而下的对相邻两个元素依次进行比较和调整,让较重的元素往下沉,较轻的往上冒。

根据基本思想,只有在两个元素的顺序与排序要求相反时才将调换它们的位置,否则保持不变,所以冒泡排序时稳定的。时间复杂度为平方阶O(n2),空间复杂度为O(1)。

冒泡排序时最慢的排序算法,是排序算法发展的初级阶段,实际应用中采用该算法的几率比较小。

2.3.2 快速排序

快速排序是对冒泡排序本质上的改进。其基本思想为:是一个就地排序,分而治之,大规模递归的算法。即:通过一趟扫描后确保基准点的这个数据元素的左边元素都比它小、右边元素都比它大,接着又以递归方法处理左右两边的元素,直到基准点的左右只有一个元素为止。

快速排序时一个不稳定的算法,其最坏值的时间复杂度为平方阶O(n2),空间复杂度为O(log n)。

快速排序是递归的、速度最快的排序算法,但是在内存有限的情况下不是一个好的选择;而且,对于基本有序的数据序列排序,快速排序反而变得比较慢。

2.4 归并排序

归并排序的基本思想是:把数据序列递归地分成短序列,即把1分成2、2分成4、依次分解,当分解到只有1个一组的时候排序这些分组,然后依次合并回原来的序列,不断合并直到原序列全部排好顺序。

合并过程中可以确保两个相等的当前元素中,把处在前面的元素保存在结果序列的前面,因此归并排序是稳定的,其时间复杂度为O(nlog2n),空间复杂度为O(n)。

归并排序比堆排序要快,但是需要的存储空间增加一倍。

2.5 基数排序

基数排序属于分配式排序,其基本思想是:首先是低位排序,然后收集;其次是高位排序,然后再收集;依次类推,直到最高位。

基数排序基于分别排序、分别收集,是稳定的排序算法,其时间复杂度为O(nlog(r)d),r是采取的基数、d是堆数,空间复杂度为O(rd)。

基数排序适用于规模n值很大的场合,但是只适用于整数的排序,如果对浮点数进行基数排序,则必须明确浮点数的存储格式,然后通过某种方式将其映射到整数上,最后再映射回去,过程复杂。

3 排序算法的选择

经过排序算法的分析比较,各种算法有自己比较适合的应用场合,选择算法时应综合考虑稳定性、时间复杂度和空间复杂度等因素。综合前面的分析比较,各种算法的各种因素影响见表1。

4 结束语

排序算法的应用非常广泛,是计算机图形学、计算机辅助设计、模式识别、商业事物处理和日常生活等领域的一种重要的程序操作。该文从时间复杂度、空间复杂度、稳定性以及规模n值的大小等方面对常用的排序算法进行了分析比较和总结,为排序算法的选择提供了依据。规模n值较小时、且对稳定性不作要求时选用选择排序比较有利,对稳定性有要求时选用插入或冒泡排序比较有利。规模n值较大、且关键码元素随机、对稳定性没要求时选用快速排序比较有利;关键码元素有序、对稳定性有要求时,存储空间又允许的情况下选用归并排序比较有利;关键码元素有序、对稳定性没有要求时选用堆排序比较有利。总而言之,充分了解各种排序算法自身的特点及其基本思想在选择、设计高效且合理的算法具有重要意义。

参考文献

[1]Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to Algorithms[M].2nd ed.The MIT Press,2001.

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

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