选择排序算法

选择排序算法（精选9篇）

选择排序算法 篇1

引言

排序算法是一种被广泛使用的算法, 在计算机软件领域发挥着重要作用。排序是将数据元素的任一序列, 重新排列成一个关键字有序的序列。基于比较和移动的排序算法具有通用性, 包括插入排序、选择排序、交换排序、归并排序、基数排序等等。各种排序的算法各具有优缺点, 但就其全面性能而言, 很难提出一种被公认的最好的方法。判断一个排序算法优劣的标准一般为时间复杂度、空间复杂度和稳定性。

一、简单选择排序算法

1、排序方法

选择排序 (Selection Sort) 是最符合人们思维习惯的一种排序方法。基本思路是每次从待排文件中挑选一个key值最小的 (或最大的) 记录放置于它应所在的位置。若待排文件长度为n, 则选择n-1趟便达到排序目的。选择排序一般又分为“直接选择排序”和“堆选择排序”。

2、直接选择排序的C语言算法

对上述算法进行优化, 在一趟中找到key, 如果该key就是i位置上的记录, 就不用交换。算法如下:

3、直接选择排序的算法分析

设排序文件的记录长度为n。算法中共进行了n-1趟选择, 每趟选择一个当前最小key的记录, 要经过n-i (1≤i≤n-1) 次的key比较, 故总的key比较次数C为:

另外, 当文件按key正序时, 记录移动次数等于0。而完全逆序时, 每趟选择后有3次记录移动, 所以最多移动次数为3 (n-1) 。故直接选择排序的时间复杂度T (n) =O (n2) 。直接选择排序属于稳定排序。

二、简单选择排序算法的改进算法

1、排序方法

基本思路是每次从待排文件中挑选一个key值最小的和一个key值最大的记录, 最小的放置于最前面, 最大的放置于最后面的位置。若待排文件长度为n, 则选择n/2趟便达到排序目的。

2、改进算法的C语言算法

3、改进算法的算法分析

设排序文件的记录长度为n。算法中共进行了n/2趟选择, 每趟选择一个当前最小key和最大key的记录, 要经过2 (n-2i) (1≤i≤n/2) 次的key比较, 故总的key比较次数C为:

C和=直ni∑/=1接2 (2选n择-排2i序) 的算法相比, 时间复杂度仍为T (n) =O (n2) , 但选择趟数减少了一半, 比较次数因为内循环中比较了2次, 和直接选择排序比较次数相当。

结束语

本文作者提出的上述改进的选择排序算法, 已通过在VC++6.0环境进行正确性测试。该算法是在简单选择排序的基础上提出来的改进算法, 提高效率是显而易见的。

摘要：排序算法是一种被广泛使用的算法, 在计算机软件领域发挥着重要作用。经典的排序包括:冒泡排序、选择排序、插入排序等等。本文以简单选择排序算法为基础, 对其进行改进, 得出与之具有更高的排序效率。

关键词：选择排序,改进算法

参考文献

[1]严蔚敏等:《数据结构 (C语言版) 》, 清华大学出版社, 2005.7。

[2]潭浩强:《C程序设计》, 清华清华大学出版社, 1999.4。

[3]方同祝、胡正国、田铮、金文凯:《一种节省空间的排序算法》, 《小型微型计算机系统》, Vol.26 No.7 July 2005。

[4]王敏:《改进的双向选择排序算法》, 《信息技术》, 2010年第9期。

[5]张忆文、谭霁:《简单选择排序算法的改进及分析》, 《信息科学》, 2009 (18) 。

选择排序算法 篇2

/** * 找到最小的元素 * @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; } } /** 省略了一些代码 */}

这里在一个循环里面要进行两次比较，于是运行时间为2n,虽然也是线性时间里面完成选择，但是常数项的开销明显变多了不少

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

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

选择排序算法总结 篇4

判断元素个数是否大于五个，如果是，就跳转到步骤(2)，否则就对数组进行排序，如果元素个数为奇数，就返回中位数，若为偶数，就返回下中位数 将数组进行分组，每组元素里面的元素各个均为五个，至多有一个数组的元素个数小于五个 将每组元素进行插入排序(元素个数较少的情况下，插入排序性能还是不错的) 把每一组里面的中位数取出来，就是五个元素里面的第三个；对于不满五个元素的组，如果元素个数为奇数，就取中位数，若为偶数，就取下中位数 对取出来的中位数组成一个新的数组，并转到步骤(1),开始对取出来的中位数数组取中位数

vc/QobXE1KrL2KGjPC9wPg0KPGgyIGlkPQ==”bfprt选择算法性能分析“>BFPRT选择算法性能分析

每组五个元素，我们对数组进行分组最后会得到n/5个组。，除去不满五个元素和包括主元x的组，至少有3×(n5?2)≥3n10?6个元素是大于x的，类似的，至少有3n10?6个元素小于x的，于是在每次分组中，两个组最不平衡的情况的也就是7:3,于是得到递归式,这里140是随便选取的一个常数

T(n)={O(1)T(n5)+T(7n10+6)+O(n),n<140,n≥140

选择排序算法 篇5

排序算法的稳定性是度量排序算法质量的一个重要指标,指两条关键字相等的记录R、S在排序前与排序后应该保持次序上的先后关系不变。简单选择排序简单易懂,但其稳定性存在争议。大部分常见排序算法在是否满足稳定性方面都有明确的结论。例如,直接插入排序、折半插入排序、冒泡排序、树形选择排序、归并排序、基数排序等都是稳定的排序算法;而希尔排序、快速排序、堆排序等是不稳定的。

文献[1]在选择排序的专题内容中给出的简单选择排序算法是不稳定的,但是进行内部排序方法比较时所有时间复杂度为平方级的简单排序方法都是稳定的。文献[1]指出,选择排序方法本身是一种稳定的排序方法,但经典的简单排序算法却表现出不稳定现象,是由于经典算法采用了交换记录的策略,适当改变该策略就可以得到一个稳定的简单选择排序算法。但是,如何调整经典选择排序的交换策略,文献[1]中并没有给出具体方法。常见程序设计、数据结构以及算法方面的教材中对简单选择排序算法的稳定性问题也都缺乏深入完整的讨论[2,3]。文献[4]指出经典选择排序算法是不稳定的,同时给出了一个改进的简单选择排序算法以保证稳定性。但文献[5]所提方法提高了经典选择排序算法的空间复杂度。本文在不改变简单选择排序时间复杂度和空间复杂度的前提下,对简单选择排序算法进行改进,提出一种稳定的同等复杂度的简单选择排序算法。

1 简单选择排序算法及其性能分析

1.1 经典简单排序算法

设待排序记录数组为R[1...n],对其按照关键字key由小到大进行排序。经典的简单选择排序算法思想为:将排序过程分为n趟,第一趟从R[1]开始,通过n-1次比较,从所有n条记录中选出关键字最小的记录,记为R[IndexOfMin],交换R[1]和R[IndexOfMin];第二趟从R[2]开始,通过n-2次比较,从第2条到最后一条共n-1条记录中选出关键字最小的记录,同样记为R[IndexO-fMin],交换R[2]和R[IndexOfMin];以此类推,上述过程重复n-1趟,完成排序。经典简单选择排序算法C语言伪代码如下:

1.2 简单选择排序算法复杂度分析

简单选择排序过程基本操作分为比较、交换两类。排序过程中,需要进行的记录移动次数较小。当原始记录按照所要求顺序排列时,交换次数为0;当原始记录排序顺序与要求顺序相反时,交换次数最多达到(n-1)次,对应的赋值次数为3(n-1)。就比较次数而言,无论原始序列是何种情况,第1趟排序过程中需要比较n-1次,第2次需比较n-2次;以此类推,第i次需要比较n-i次,最后一趟比较1次。因此,总的比较次数为n*(n-1)/2。由此可知,简单选择排序算法的总时间复杂度为O(n2)。

就空间复杂度而言,由上述简单选择排序伪代码可见,无论待排序记录有多少条,简单选择排序算法只有i、j、IndexOfMin和temp四个辅助变量。因此,简单选择排序算法的空间复杂度是常数阶的,空间复杂度为O(1)。

1.3 稳定性分析

结合实例说明经典简单选择排序算法是不稳定的。假设:将以下序列从小到大排序,3,3*,3* *,2(当中,*用来区分关键字相同的不同记录)。按照经典的简单选择排序,当i=1执行第一次循环时,最小记录为最后一条记录2,它对应的下标IndexOfMin取值为4。此时,将R[1]与R[4]互换得2,3*,3**,3。第二趟和第三趟选择排序不发生任何交换。因此,最后所得有序序列仍然为2,3*,3**,3。可见,两条相等的记录3与3* 在排序前后的顺序发生了改变,经典的简单选择排序算法不稳定。

2 改进的简单选择排序及其性能分析

2.1 改进的简单选择排序算法

为了保证简单选择排序的稳定性,本文方法基本思路如下:找到最小记录R[IndexOfMin]后,不将该元素与无序快首记录(即第i条记录)直接交换,而在第i+1条记录到最小记录之间寻找与R[i]关键字相等的记录。每找到一条就将它与R[i]互换。如此,最多经过n-i次交换,R[i]就成为IndexOfMin之前、离IndexOfMin最近的与无序块首记录关键字相等的记录,而其它记录的相对顺序不发生改变。此时再将R[i]与R[IndexOfMin]交换,则排序算法将保持稳定性。

首先给出改进后的简单选择排序算法的伪代码,结合实例说明其稳定性,并对改进后算法的时间复杂度和空间复杂度进行分析。改进后的简单选择排序算法如下,加粗部分是为了保证算法稳定性而新增的代码。其目的是将无序块首记录后面的、与无序块首记录关键字相等的最后一条记录交换到无序块的首位置,同时保证其它与无序块首记录关键字相等的记录保持次序先后关系上的不变。结合实例说明这一过程。

以序列3,3*,3**,2由小到大排序过程为例说明改进算法的执行过程。第一趟排序过程中,IndexOfMin取值为最小记录2的下标4。此后,改进的算法并未将该记录与无序快首记录交换,而是执行如下交换过程:第1次,3*与3交换,得序列3*,3,3**,2;第2次,3*与3**交换,得序列3**,3,3*,2;最后一次,最小记录与无序块首记录交换,即2与3* * 交换,由此得到记录序列2,3,3*,3**。最后两趟选择排序过程中,记录未发生任何交换,最后所得有序序列为2,3,3*,3**。由此可见,与经典的简单选择排序算法不同,改进后的算法并未改变三条关键字均为3的记录的相对次序。

再如,对记录序列12,15,12*,11,15*,15**,10,15***,9,20,17,15****,111,16,15*****由小到大进行排序。15条记录中记录12出现2次,记录15出现了6次。第一趟排序过程中,IndexOfMin的取值为9,在首记录12与最小记录9交换之前,两者之间的元素12与12*先进行一次交换,从而12*成为了首记录。此后,12*与最小记录9交换得到9,15,12,11,15*,15**,10,15***,12*,20,17,15****,111,16,15*****。第二趟选择排序过程中,最小值为10,Index-OfMin的值为7在15与10交换之前,首先15与15*交换,然后15*与15** 交换,最后15* * 再与10交换。以此类推,最终可得记录序列9,10,11,12,12*,15,15*,15**,15***,15****,15*****,16,17,20,111。由此可见,取值为12或者15的记录在排序前后相对次序未发生改变,满足稳定性的要求。

2.2 改进的简单选择排序算法性能分析

改进的算法只在第一层循环(i对应的循环)内加了一个与第二层循环(j对应的循环)并列的循环。从循环结构嵌套的角度来分析,外层循环执行n-1次,内层的两个循环中,j对应的循环至多执行n-1次,新增的循环也至多执行n-1次,由此可知,整个算法中基本操作的执行次数为(n-1)*[(n-1)+(n-1)],所以改进后的简单选择排序的时间复杂度并未提高。

就具体的基本操作次数而言,改进后的简单选择排序算法需要的基本操作只包括比较和交换两类。当原始记录按照所要求顺序排列时,条件IndexOfMin!=i始终不成立,此时改进后的算法时间性能最优,交换次数为0,比较次数与改进前的简单选择排序算法相同,均为n*(n-1)/2。当原始记录排列顺序恰巧与要求顺序相反时,j所对应的循环下执行的比较次数为n*(n-1)/2;k所对应的循环下每次都判断条件与否的比较次数最多为(n-2)+ (n-3)+…+1=(n-1)*(n-2)/2;最坏情况下每次比较都要发生交换,再加上k所对应循环外的一次交换,最坏情况下交换次数为(n-1)*(n-2)/2 +(n-1)= n*(n-1)/2。由此可见,相比改进前的简单选择排序算法而言,为了保证排序算法的稳定性,改进后算法比较操作和交换操作的次数最多均增加(n-1)*(n-2)/2次。结合上节例2,第一趟选择排序过程中,经典的选择排序算法进行了14次比较和1次交换。而改进后算法在进行14次比较之后IndexOfMin值为8,还需进行7次比较,以判断是否存在k使得R[k].key==R[i].key成立,此时共进行了21次比较,中间过程中两个12交换1次、最小元素9与首元素再交换1次,共2次交换,所以,比较次数和交换次数均有所增加,但如前文所述,改进后算法最大时间复杂度与改进前保持不变,都是O(n2)。

此外,就改进后算法的空间复杂度而言,相比改进前算法,无论待排序记录有多少条,新算法只是引入了一个计数器变量k,所以改进后算法的空间复杂度也保持不变,仍然是常数空间复杂度,即空间复杂度依然是O(1)。

最后,根据简单选择排序算法的改进原理,每趟简单选择排序过程中,最小记录只是与其左侧最后一个与无序块首记录相等的记录发生了交换,交换后该记录仍然位于原本在其前面的、与其关键字相等的记录后面;同时,其它记录的相对次序保持不变。所以改进的简单选择排序算法是稳定的。结合2.1节的两个实例也可说明这一过程。

3 结语

本文对简单选择排序算法的稳定性问题进行了探讨,在对现有研究进行综述的基础上,结合实例指出经典的简单选择排序算法是不稳定的;对经典的简单选择排序算法进行改进,在保持时间复杂度和空间复杂度不变的前提下,提出一个稳定的简单选择排序算法。

摘要：稳定性是度量排序算法质量的一个重要指标。简单选择排序是一种常见的排序算法,但其稳定性存在较大争议。结合实例探讨经典简单选择排序算法稳定性,并进行改进,在时间复杂度和空间复杂度不变的前提下,提出一种稳定的简单选择排序算法。

关键词：算法设计,排序算法,选择排序,算法稳定性

参考文献

[1]严蔚敏.数据结构[M].北京:人民邮电出版社,2011.

[2]宁正元.数据结构[M].北京:中国水利水电出版社,2000.

[3]ROBERT SEDGEWICK,KEVIN WAYNE.算法[M].谢路云,译.北京:人民邮电出版社,2014.

选择排序算法 篇6

关键词：中学信息技术教学,高效课堂

追求课堂教学的高效率, 是每一位教师不断追求的目标, 它是教学过程的最优化, 教育效果的最大化, 是师生完美配合的结晶。自新课程实施以来, 新的教育理念引导着教学的改革, 课堂教学发生了很大的变化。如何教会学生掌握科学的学习方法, 增加学生学习的积极性和有效性, 提高课堂教学效率, 成了我们共同面临的问题。那么, 究竟什么是高效课堂呢?

高效必须实效。在高效课堂中教师的“教”为学生的“学”服务。高效课堂应具备以下两个条件:一是学生对三维学习目标的达成度要高;二是在实现这种目标达成度的过程中, 学生应主动参与并积极思考。从这个角度来说, 高效课堂就是学生主动学习、积极思考的课堂, 是学生对所学内容主动实现意义建构的课堂。从教师角度来说, 高效课堂应具备以下三个条件:一是教师能够依据课程标准和学生的实际情况, 科学合理地确定课堂的三维目标。二是教学的过程必须是学生主动参与的过程。这种主动参与主要体现在教师能否采取灵活机动的教学策略调动学生学习的积极性, 能否积极引导学生积极思维, 能否给予学生更多的时间和机会进行必要的合作和展示, 使全班学生分享彼此的学习成果。三是教学中适时跟进、检测、反馈、消解, 以多种方式巩固学生的学习成果, 使三维教学目标的达成度更高[1]。

如何构建高效课堂呢?下面我将以《选择排序算法》为教学案例, 从教师与学生二方面入手, 就教学实施中如何采取多种教学手段达成教学的三维目标, 构建高效课堂, 谈谈自己的一些看法。

一、教师与高效课堂

1. 要精心备课, 成竹在胸

备好课是搞好教学的根本, 教师只有深入钻研教材, 精心设计课堂教学, 才能取得良好的教学效率。备教材:教师要吃透教材, 掌握本节课的重点内容, 该教什么, 该怎样教, 在脑海中形成框架, 并贯彻到教学中去。

以《选择排序算法》为例, 它的教学重点是理解选择排序的算法思想, 只有理解了它的算法思想, 才能真正学会选择排序的使用。教学难点是通过绘制流程图去理解选择排序算法的思想, 并能使用选择排序算法编程解决具体问题。对于初接触选择排序的同学来说, 去理解好算法的思想与结合实际使用好选择排序算法是很难的, 所以老师在设计的时候要做到深入浅出, 能让学生更容易去理解它。

2. 课堂设计要合理、巧妙, 激发学生的求知欲望

高效课堂的教学设计应要让学生一直处于不断的思考之中。因此, 教师应努力设计好每一个教学环节, 让学生一直处在一种积极的思考状态中, 让他们在充分思考的基础上, 发表自己的观点, 教师适时加以点拨, 此举对于调动学生学习的积极性, 提高他们的求知欲望有很大帮助。教师应充分掌握学生的学情, 精心设计学生的活动, 激发学习兴趣, 启发学生思维, 给以足够的时间, 引导学生集体讨论、自我展示、及时反馈、及时调控, 使师生、生生合作和谐默契, 以实现课堂教学的优化[2]。

以《选择排序算法》为例, 整个教学活动思路可以由以下六个环节组成:问题导入、明确学习目标、自主学习、疑难点拨、课堂小结、课堂拓展。

环节一:问题导入

在课堂的开始, 可以设计一些问题的导入。通过一连串问题的回答既起到温故而知新的作用, 使学生明白排序的作用, 也促使学生积极思考, 主动建构知识体系。

如老师可设计以下问题来让同学们回答: (1) 前面我们学习了哪几种查找算法? (2) 为什么要引入对半查找算法?它的使用条件是什么? (3) 怎样使数据变得有序? (4) 我们曾经在哪里学习过排序?

环节二:明确学习目标

通过明确学习目标, 使学习更有针对性更有效, 同时也培养学生一种良好的习惯, 做什么事都有一个明确的目标。向同学们展示本课的学习目标: (1) 掌握和理解选择排序的算法思想。 (2) 会用选择排序算法编程解决具体问题。

环节三:自主学习

通过自主学习可以更好地培养学生的自主学习能力;在课堂上的随机点名, 可以促使学生更主动学习;老师可以通过游戏和观看Flash动画, 使学生更好地理解选择排序算法的思想, 也能活跃课堂气氛, 激发学生的学习兴趣, 达到事半功倍的效果。

以本课为例, 老师首先向学生展示自学任务: (1) 阅读教材125页, 了解选择排序算法的思想。 (2) 随机请5位学生到教室前面以游戏的形式模拟用选择排序算法对5位学生手持的数据进行排序。

然后播放选择排序算法的Flash动画, 让学生更好去理解选择排序思想。

环节四:疑难点拨

这个环节主要是培养学生勤于思考的良好习惯, 提高善于思考的能力;充分发挥学生的主体性和教师的主导性, 把大问题分解为一个个小问题, 一步步突破教学难点, 然后通过动手实践, 掌握使用排序算法设计程序解决问题的方法。

此课首先让学生完善选择排序算法流程图的绘制, (1) 选择排序算法中要完成哪几个关键步骤? (2) 怎样从n个数据中选出最小的一个数? (3) 怎样交换两个变量的值? (4) 对n个数据进行排序要重复多少次?

然后编程与调试, 根据流程图应用选择排序算法对5位学生手中的数据进行排序。

环节五:课堂小结

通过课堂小结, 可以让学生养成反思与总结的良好习惯, 而这个过程不由老师完成, 而是请学生小结本节课的学习收获, 然后抽一位同学讲出来。

环节六:课堂拓展

通过课堂拓展, 让学生明了算法优缺点, 为下节课的插入排序算法打下铺垫。而这个环节是以提问思考的方式进行, 提问:教材上的选择排序程序有什么不足之处?怎样修改该程序从而优化该算法?

3. 教师要做好课堂的调控者

要让学生在课堂上把自己预习的成果或自己学习小组共同完成的学习成果进行展示, 老师要做好导演的角色。高效课堂要关注学生的全员参与。一节课的成功与否不是老师讲得成功, 也不是老师在课堂上提问几个好学生让他们获得成就感, 而是要让全体学生都能参与其中, 体现出学生参与的全员性。

二、学生与高效课堂

1. 激发学生的学习兴趣

兴趣是求知的内在动力。激发起学生的兴趣, 学习就会积极主动, 学得轻松而有成效。但是学习兴趣不是天生的, 主要在于教师如何引导学生, 充分调动学生对学习的积极性和主动性, 进而能创造性地学, 最终达到优化课堂教学和提高教学效率的目的。

课程改革的今天, 应多方面激发学生学习的兴趣, 挖掘学生兴趣的潜在因素。做到一上课就紧紧地抓住学生的注意力, 激起学生的兴趣, 使他们很快进入“最佳学习状态”, 这是上好课的第—步。教师应成为教学活动的组织者, 引导者与合作者。教师的角色便是调动学生主动思维和主动参与的积极性。因此, 教师应根据学生的认知规律创设条件, 引导学生主动学习、探究, 成为学生学习过程中的组织者、引导者和协助者。例如《选择排序算法》中, 老师可以从原有基础上来进行引导, 学生基本都学过了电子表格EXCEL, 其中的“排序”功能能把一组数据按照一定的顺序排列好, 由老师提供一组“世界七大洲最高峰”的数据, 请一个学生利用EXCEL对表格从高到低排好序。显而易见, 这项任务对于熟悉EXCEL的同学很容易完成, 但这个时候爱思考、会动脑筋的学生会提出疑问, 电脑到底是怎么把数据按照顺序排列好的, 我们能否不用EXCEL, 自己编写一个程序实现表格的排序呢?学生为了知道这个编程的方法, 学习排序算法的兴趣就上来了, 对学习好这一课打下了坚实的基础。

2. 调动学生自主学习的积极性

教学中往往存在教师用足了劲却收效甚微的现象。这时常常会抱怨学生脑子笨, 基础差, 学习态度不端正。究其原因, 学不得法才是症结所在。教育家品淑湘先生曾言:“教学, 教学, 就是‘教’学生‘学’而不是把现成的知识教给学生, 而是把学习方法教给学生, 学生就可受用一辈子。”这是很精辟的见解。例如:在《选择排序算法》教学中, 首先由学生阅读教材内容, 了解选择排序算法的思想。再选5位同学到教室前面以游戏的形式模拟用选择排序算法对5位学生手持的数据进行排序。对5位同学采用比赛的形式进行, 看哪位同学最先完成。学生之间有这种比较, 学生就会有更多的学习积极性。有了这样的学习经验, 今后学生再学习新的内容时, 就会主动的去学习新的知识点了。这样, 即可以大大的提高学生学习的主动性和积极性, 又对学生进行了知识的积累, 更培养了学生敢于探索、勇于实践的精神。

教师在这个过程中要为学生创建有利于自主性学习的环境及资源, 培养学生的自主学习能力。利用现代信息技术来学习信息技术课程。在组织安排教学过程中, 不是把大量的时间用于组织讲解教案上, 而是放在为学生提供学习所需要的各种资源上, 把精力放在简化利用资源所经历的实际步骤上。利用CD-ROM光盘提供形式生动活泼、内容丰富、信息量大、具有交互功能的学习资源。可以利用网络系统, 共享资源, 让学生学习如何从多媒体教学软件中, 从局域网络或互联网络中获取信息, 得到多种学习材料, 培养学生自主进行学习的能力, 让学生通过查询、检索、探究并解决问题。把学习资源作为学生进行分析、思考、探究、发现的对象, 以帮助学习者理解原理, 并掌握分析和解决问题的步骤, 培养学生自主学习能力。学习如何从资源中获取信息、分析信息的能力, 培养学生善于发现问题、提出问题, 学会如何进行问题探究, 并利用资源材料解决问题。

3. 动手实践

实践是创新精神与自学能力的集中体现, 是训练自学能力和创新能力的最佳途径, 教学中给予学生充分的时间进行实践操作, 能强化学生自主学习的成功体验。由于信息技术课的教学环境不同于其它课程, 教学大部分都是在学校的网络机房里面开展的, 并且大纲规定学生上机时间不少于总学时的70%, 把大部分的课堂时间留给学生自己上机操作实践是非常有必要的, 因为很多具体的操作并非教师的讲解就能使学生明白的, 必须通过学生亲自上机练习实践。在设计教学的时候, 应当注意针对学习内容明确相应的任务, 在每次的上机实践课中, 教师给学生定一个目标, 再由学生自行思考和上机操作, 通过不同的方法来实现和解决。

在信息技术课的教学中充分地调动学生的主观能动性, 打破传统的教学模式, 要形成以学生为中心的生动活泼的学习局面, 使学生学习由要我学变为我要学, 这样就容易激发学生的创新激情, 培养学生的创新能力, 为未来的高层次创造活动打下良好的坚实基础。中小学信息技术课是崭新的素质教育课程, 并且对比于其他传统科目, 信息技术课有着本身的一些特殊之处, 要尽力避免传统课程的缺陷 (如片面追求学科体系化, 教学内容偏深而不实用等) , 使信息技术课成为亲切易学的实用课程。作为信息技术教师, 我们要高举素质教育大旗, 使本课程真正为基础教育注入生机与活力[3]。

参考文献

[1]王跃.高效课堂的101个细节[M].广州:广东高等教育出版社.2009:13-24

[2]高铁刚.信息技术环境下课堂教学模式的理论与方法[M].北京:清华大学出版社.2011:9-20

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

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.

最简单的排序算法 篇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.