张帅 方欢 丁飞

摘要：排序算法是算法中最为基础的算法，其在很多的领域中都得到了相当的重视，在对于大量数据的处理方面，排序算法有着极其重要的作用。排序算法的种类有很多，为找出一种效率较高的排序算法，基于Java语言对10种经典排序算法进行实现和测试，通过对结果的分析，判断每种排序算法的运行时间及效率，对10种经典排序算法的运行效率进行排序。

关键词：排序算法;Java语言;运行效率;运行时间;数据处理

中图分类号：TP311文献标识码： A

文章编号：1009-3044（2020）25-0223-03

开放科学（资源服务）标识码（OSID）：

排序算法作为算法中的基础算法在各领域中都有着至关重要的作用，一种排序算法的效率程度往往影响着数据分析的效率和时间，因此一个优秀的排序算法，不仅仅是实现对数据的排序功能，还要能够在较短的时间内，对大量的数据进行排序[1]。本文基于Java语言对10种经典排序算法，并编写相关程序对其时间效率进行分析。

1十种经典排序算法

1.1冒泡排序

冒泡排序作为排序算法中最为基础，最为简单的算法，它重复的遍历需要排序的数组，每一次比较相邻的两个元素，并根据顺序进行交换，直到无须交换为止。实现代码如1-1。

1.2选择排序

选择排序则是遍历一次数组，从中找出最大（小）元素，放到数组的末尾（开头），将剩余的元素再次遍历，继续寻找最大（小）元素，知道所有元素排序均排序完毕。实现代码如1-2。

1.3插入排序

插入排序是一种重要的排序算法，其原理是最容易理解的排序算法，可以将其形象地比喻为摸扑克牌，每次加入一个元素，将加入的元素插入到有序序列的适当位置，并再加入一个新元素，重复操作，直到所有元素均有序。

1.4希尔排序

希尔排序是插入排序的一种改进版本，希尔排序是将整个待排序的组数分割成为若干个子序列，并在子序列中使用插入排序，并不断扩大子序列的长度，最终实现全体有序[3]。

1.5归并排序

归并排序体现出了分治法的思想[4]，其思想为先划分，在合并，将待排序列每次分为两个大小相等的子序列，并将子序列排序，使用两个指针，将两个序列中较小的元素放入到合并空间中，并移动指针到下一个元素，直到合并完毕。

1.6快速排序

与归并排序相类似，归并排序注重合并，而快速排序则注重划分，从数组中挑选一个元素作为基准，在划分时，将比基准小的元素放到左边，将比基准大的元素放到右边，然后递归地把两个子序列排序，直到所有元素全部排序完毕。

1.7堆排序

堆排序利用了堆的数据结构，其性质为子节点的值总是小于或大于其父节点，堆排序正式利用了此性质来进行排序。

1.8计数排序

计数排序是一特殊的排序算法，其核心为开辟一个额外的数组，统计待排序数组中每个元素值i出现的次数，计入额外数组的第i项，再根据额外数组没项的值反向输出，便可完成排序，计数排序常常用来解决对数字的排序。

1.9桶排序

桶排序相当于计数排序的升级版。它增强了函数的映射关系，使得算法能够更加的高效，它将每一个元素都通过映射函数映射到桶中，再将其排序，最后将每个桶按序输出。

1.10基数排序

基数排序也是桶排序的一种变型，其原理是将每个数字按照位数切割，并按照每个位数进行排序操作。其相当于按照位数来分配桶[5]。

2实际效率测试

对于此10种经典排序算法，我们将基于java语言设计程序来测试每种排序算法针对不同规模的数据的运行时间，并对其运行时间数据进行统计和分析。

2.1设计测试程序

利用java语言设计测试程序，使得每种排序算法能够在不同的数据规模统计其排序所使用的时间。程序代码展示如下：

2.2测试结果

由于基数排序受到数据位数的限制，导致基数排序的数组需要重新获得，中间随机数较多，并且数据位数越大所需时间越多，因此基数排序只选择到500000条。

2.3结论

从表格中可以看出，在数据量较小时，10种排序算法的时间相差不大，但随着数据量的不断增加，冒泡排序，选择排序，插入排序，希爾排序的时间增长迅速，且当数据大于10000000时，处理此规模所需要的时间会更长，因此无法做出有效的统计。而归并排序、快速排序、堆排序可以处理大规模的数据，但所需时间也较长。而计数排序、桶排序可以有效地解决大规模数据的问题，但是其缺点为需要开辟大量的额外空间来对数据进行统计。

参考文献：

[1]RebertSedgewick，KevinWanyne.算法[M].谢路云，译.北京：人民邮电出版社，2012.

[2] 吴光生，范德斌.排序算法研究[J].软件导刊，2007（4）：97-98.

[3] 刘齐锐.基本排序算法研究[J].通讯世界，2018（5）：295-296.

[4] 肖建华，寻大勇，赵艳红.排序算法中的分治策略[J].湖南工程学院学报（自然科学版），2001，11（1）：9-12.

[5]https：//www.runoob.com/w3cnote/ten-sorting-algorithm.html.2018.

【通联编辑：梁书】