常见排序算法多线程实现与比较_范兴国.pdf

宝鸡文理学院学报（自然科学版），第 卷，第期，第 页，年 月 （），：常见排序算法多线程实现与比较范兴国，卫泽刚，张豪，张小丹，刘飞，钱郁（宝鸡文理学院 物理与光电技术学院，陕西 宝鸡 ）摘要：目的对目前常用排序算法进行多线程实现，并运用不同类型数据集进行比较研究，以充分利用现代计算机多核处理器优势，有效提高大规模数据排序操作。方法首先简要介绍目前常用的 种排序算法的基本原理，然后基于 语言采用多线程模式进行代码实现，最后用种不同类型测试数据进行详细比较，分析这些排序算法的优缺点及适用范围。结果对于同一个排序方法，多线程可以明显提高排序效率，但相同规模数据条件下，不同的数据类型影响排序效率。结论多线程排序能够充分利用计算机多核资源，提高排序效率。对于大规模数据，多数排序方法都可以快速得到排序结果。关键词：排序算法；多线程；快速排序；排序效率；数据处理中图分类号：文献标志码：文章编号：（），（，）：，：；随着信息技术的不断发展，数据采集设备日益增多，数据规模也在不断增加，如何高效处理数据成为研究的热门问题之一。在现实生活和实际软件开发过程中，由于数据种类较多、数量较大，从而导致处理起来会耗费大量的物力、财力和人力，因此，我们更希望处理有规则、有顺序的数据，可以极大方便后续的数据分析。在处理数据具体过程中，排序成为很多算法或软件的首要步骤，收稿日期：，修回日期：基金项目：陕西省自然科学基础研究计划一般项目（）；陕西省教育厅专项科学研究计划项目（）；陕西省自然科学基础研究计划重点项目（）；宝鸡文理学院 年研究生创新科研项目（）；宝鸡文理学院第十七批校级本科教学改革研究项目（）作者简介：范兴国（），男，山东淄博人，在读硕士研究生，研究方向：生物信息学 ：通讯作者：张小丹（），女，山西运城人，实验员，硕士，研究方向：计算生物学 ：已成为计算机科学领域中最基础的操作之一。排序就是通过一定的规则将无序数据重新排列的操作。排序后的数据有明显的顺序性，可以呈现一定的规律性。因此，经过排序处理后的数据便于筛选和处理，提高了后续分析效率。排序算法就是按照给定要求对无序数据进行排列的方法。研究者们已开发出一系列排序算法，每种排序算法各有优缺点，不同的排序算法适合不同的数据情况。针对处理数据的特点，如何选择合适的排序算法是每个数据分析师或软件开发者需要面对的首要问题。而且，随着芯片制造技术的发展，处理器生产工艺不断进步，如今的笔记本电脑、台式机乃至商用服务器都是多核处理器，多核处理器上的多线程能让多段程序逻辑同时工作，可以真正发挥出多核处理器的优势，而达到充分利用计算机处理器的目的。为此，本文详细阐述了常用经典排序算法的基本思想，并对每个算法进行多线程实现，然后采用不同的数据类型进行详细比较，分析了每种算法的排序效率和适用情况，希望对排序算法使用者提供参考依据。常见排序算法介绍 冒泡排序冒泡排序是排序算法中最为基础、最为简单的排序算法。排序思路是在一组待排序元素中，每次从第一个元素进行扫描，比较个相邻元素的大小，如果前一个数值大于后一个数值，就将两者进行交换。经过一趟比较后，整体上数值较大的元素往后移动，数值较小的元素往前移动。然后重复上述步骤，直到某一趟排序过程中没有任何数值发生交换，则排序结束。在排序过程中，数值较大的数据向下沉，数值小的数据往上浮，就像气泡漂浮一样，于是将这种排序算法形象地称为冒泡排序。由于排序过程中数值相等的元素不进行交换，相同元素的前后顺序仍未发生改变，因此冒泡排序是稳定排序。冒泡排序最小时间复杂度为（），即排序过程不发生浮动，待排序数据从小到大已排列好，扫描一次即可完成排序，平均时间复杂度和最大时间复杂度均为（）。快速排序快速排序是对冒泡排序法的一种改进，首先从数据中选择一个值作为参考值（通常取第一个数据），然后将其他数据与参考值进行比较，将小于或等于参考值的数据放在参考值的左边，大于参考值的数据放在参考值的右边，即完成一趟排序。然后再对左侧数据和右侧数据做同样操作，直到所有数据排序完毕。快速排序是不稳定的，平均时间复杂度和最小时间复杂度均为（），最大时间复杂度为（）。选择排序选择排序首先遍历所有数据，找到最小值并与第一个数据进行交换，然后将第二个数据与剩余数据的最小值进行交换，以此类推，直到所有数据排序完毕。选择排序是稳定排序，在排序过程中，无论数据顺序如何，都需从前往后遍历所有数据找到最小值，因此最小时间复杂度、最大时间复杂度和平均时间复杂度均为（）。堆排序堆排序（）是利用了堆数据结构而设计的一种排序算法。堆是一种完全二叉树，分为大顶推和小顶堆，大顶堆中每个结点的值都大于或等于其左右孩子结点的值，小顶堆中每个结点的值都小于或等于其左右孩子结点的值。堆排序的基本思想是：首先将所有待排序数据构造成一个大顶堆，此时，整个数据的最大值就是堆顶的根节点。然后将其与无序数据的最后一个元素进行交换，此时末尾就为最大值。再次调整除去最大元素后的无序序列为一个大顶堆，将堆顶元素与无序数据末尾元素交换，得到第二大元素。重复以上步骤，直到所有数据排序完毕。堆排序是是一种不稳定的排序算法，其平均时间复杂度为在排序过程中，无论原始数据顺序如何，堆排序都要对数据进行比较，因此最小时间复杂度、平均时间复杂度和最大时间复杂度均为（）。插入排序插入排序就是将数据插入到已经排好序的有序数据中从而完成对数据的排序。排序过程类似于对扑克牌进行排序，每次加入一个元素，将其插入到有序序列的适当位置，然后再加入一个新元素，重复上述操作，直到所有元素均为有序。插入排序是稳定排序，当待排序为序数组时，扫描一遍数据即可完成排序，因此最小时间复杂度为（），平均时间复杂度和最大时间复杂度均为（）。希尔排序希尔排序是对插入排序方法的改进，又称为“缩小增量排序”。希尔排序首先将原始数据按其索引位置，并根据一定的增量（初始增量一般为数据量大小的一半）进行两两分组，对每组数据使用插入排序算法进行排序。然后减小增量（增量第期范兴国 等常见排序算法多线程实现与比较一般为上一次增量的一半），重复以上步骤再次进行排序，直到增量为时，排序完毕。希尔排序是不稳定排序，其时间复杂度依赖于增量的选择，一般而言，其最小时间复杂度为（），最大时间复杂度为（）。对于平均和最大时间复杂度，因增量的取法不同而不同。归并排序归并排序体现了分治法的思想，即先划分数据，再合并数据。归并的含义就是将个或个以上的有序数据合并成一个新的有序数据。归并排序具体过程为：将原始数据分成诸多长度为二的数组，然后对其进行排序，再将个或个以上的有序数据序列合并 成 一个 新 的 有序数 据序列，直到所有数据合并完毕。归并排序是稳定排序，在排序过程中无论原始数据顺序如何，都需要进行划分与合并，因此最小时间复杂度、平均时间复杂度和最大时间复杂度均为（）。计数排序计数排序首先创建一个新数组作为计数数组，然后遍历原始数据，统计原始数据中每个元素值出现的次数，记录到计数数组第项。这样遍历一遍原始数据，便将数据中每个数值出现的次数有序的记录下来，然后将计数数组每一项的值按个数进行输出，即为排序结果。对于计数排序，无论原始数据顺序如何，都需要遍历一遍数组，因此最小时间复杂度、平均时间复杂度和最大时间复杂度均为（）。桶排序桶排序是计数排序的扩展版本，计数排序可以看成每个桶只存放相同的元素，而桶排序每个桶存放一定范围的元素，这里的“桶”可以理解为一个数据范围。桶排序具体过程为：将待排序数据分散放到多个桶里，其中前一个桶的最大值小于后一个桶的最小值。然后对每个桶中的元素进行排序，最后将每个桶按序输出，即可得到排序结果。桶排序的最大时间复杂度为（）。基数排序基数排序是桶排序的一种变型，其原理是将每个数字按照位数进行划分，相当于按照位数来分配桶，再对位数相同的数据进行排序操作。基数排序具体排序过程为：首先根据个位上数字的大小进行第一轮排序，得到第一轮排序结果，再按十位上的数字大小对其进行排序，以此类推，直到最高位排序完成后，即可得到最终的排序结果。假设原始数据最大位数为，无论数组顺序如何，都要对每个位数排序一遍，因此基数排序的最小时间复杂度、平均时间复杂度和最大时间复杂度均为（）。排序 排序 是一种面向真实数据稳定高效的排序算法，年由 设计 并使用 语言实现了 排序算法。现实中遇到的很多待排序数据，其中有部分连续数据已是有序序列，排序就是利用了这一特点，同时结合归并排序和插入排序而设计的一种混合排序算法。称这些已经有序（顺序或逆序）的数据块为“”，可以理解为个数据“分区”。首先分析待排序数据，根据其数据特点进行数据分区，同时针对数据分区，按规则进行合并，每次归并会将个分区合并为个分区，直到所有数据合并为个分区，即可完成排序。排 序 算 法 的 时 间 复 杂 度 最 小 情 况 为（），平均和最大时间复杂度均为（）。排序算法的多线程实现多线程排序是利用计算机的多核资源进行排序，如果将上述每个算法用单线程实现，一般情况下，在双核处理器上运行只利用了计算机 的性能，在四核处理器上运行只利用了 的性能。而多核处理器上的多线程模式可以同时让多段程序一起工作，进而真正发挥出多核处理器的优势，达到充分利用处理器的目的，极大提高了程序运行效率。因此，为充分利用现在的计算机多核资源，本文设计并实现了利用多线程来实现每个排序方法。排序算法的多线程实现主要分为个阶段，如图所示，第一阶段是划分数据，以线程为例，将数据划分为个数据块。然后采用某种排序方法对每块数据进行排序，此时利用多线程技术对每块数据进行同时排序。最后再采用多线程合并划分的数据，即可得到最终的排序结果。下面的代码展示了使用 语言实现多线程插入排序。首先定义插入排序函数（第 行代码），然后多线程调用时，在排序函数前面添加关键字 即可实现多线程排序（第 行代码）。本文创建了长度为 的待排序组数（第 行代码），然后通过多线程方式分别对前半部分数组（第 行代码）和后半部分数组（第 行代码）进行同时排序，最后有序合并数组（第 行代码），即可完成对整个数组的排序。本文中所有排宝鸡文理学院学报（自然科学版）年序算法的多线程实现代码下载链接为：。图多线程排序实现框架示意图 （）定义插入排序函数 ：（）：；：（，）定义合并函数，：，：（，），（）：，创建长度为 的随机数组 （：）线程排序前半部分数组 （：）线程排序后半部分数组，与线程同时执行 （，）合并 实验结果与讨论本文基于 编程语言对每种排序算法进行多线程实现，并采用不同类型、不同规模的数据进行详细比较。通过对实验结果的分析，判断每种排序算法在多线程情况下的运行时间。所有排序方法均在 系统下运行，系统详细配置为：操作版本系统，运 行（）内 存，英 特 尔 处理器（线程）。用种不同类型的测试数据（随机数据、有序数据与含有一定重复性的数据）进行比较。采用运行时间来分析不同排序算法的排序效率。随机数据比较假设数据个数为，则对到的所有整数随机打乱，即可产生个随机数。本次实验生成了数据规模为 的随机数据，然后分别对每种数据规模的随机数据采用 种排序算法进行排序，测出其排序时间，如表所示。可以看出，当待排序随机数据的规模小于等于 时，所有排序算法都会在 之内完成排序。当待排数组的规模大于 时，不同排序方法排序时间变化较大。比如冒泡排序、选择排序和插入排序的排序时间明显大于其他排序算法，其中冒泡排序方法的排序时间最长，比如对于规模大小为 的随机数据，需要 （），而快速排序与第期范兴国 等常见排序算法多线程实现与比较桶排序可以在多完成排序。当数据规模大于 时，冒泡排序、选择排序和插入排序由于排序时间太长而没有统计其排序时间。因此，当随机数据的规模大于 时，不建议选择冒泡排序、选择排序和插入排序，剩余的种排序方法均可以快速完成排序，其中快速排序方法在处理 规模以上的随机数据时排序最快，只需 即可完成排序。表随机数据不同排序方法的排序时间（单位：）（）排序方法随机数据规模（一万）（十万）（百万）（千万）（一亿）（十亿）冒泡排序 快速排序 选择排序 堆排序 插入排序 希尔排序 归并排序 计数排序 桶排序 基数排序 注：“”表示排序时间太长，之内得不到排序结果。表是不同排序方法的运行内存消耗，可以看出，同一数据规模下，不同排序方法的内存消耗相差较小。影响内存消耗的主要因素是数据规模，不同数据规模条件下，同一方法的内存消耗差别较大。从千万级别（）数据规模开始，内存消耗和数据规模同数量级增长，即数据规模增长 倍，内存消耗大约也增长 倍。表随机数据不同排序方法的内存消耗（单位：）（）排序方法随机数据规模（一万）（十万）（百万）（千万）（一亿）（十亿）冒泡排序 快速排序 选择排序 堆排序 插入排序 希尔排序 归并排序 计数排序 桶排序 基数排序 注：“”表示排序时间太长，之内得不到排序结果。表是不同规模随机小数的排序时间，与随机整数相比，每个方法的排序时间没有明显的变化，说明排序方法的排序时间主要受数据规模大小的影响。有序数据比较有序数据分为正序（从小到大排列）与逆序（从大到小排列）数据。数据规模为的正序数据即为从到的正整数，逆序数据则是从到的正整数。表是不同规模的正序数据排序结果，表是不同规模的逆序数据排序结果。宝鸡文理学院学报（自然科学版）年表随机小数不同排序方法的排序时间（单位：）（）排序方法随机数据规模（一万）（十万）（百万）（千万）（一亿）（十亿）冒泡排序 快速排序 选择排序 堆排序 插入排序 希尔排序 归并排序 计数排序 桶排序 基数排序 注：“”表示排序时间太长，之内得不到排序结果。表正序数据不同排序方法的排序时间（单位：）（）排序方法正序数据规模（一万）（十万）（百万）（千万）（一亿）（十亿）冒泡排序 快速排序 选择排序 堆排序 插入排序 希尔排序 归并排序 计数排序 桶排序 基数排序 注：“”表示排序时间太长，之内得不到排序结果。表逆序数据不同排序方法的排序时间（单位：）（）排序方法逆序数据规模（一万）（十万）（百万）（千万）（一亿）（十亿）冒泡排序 快速排序 选择排序 堆排序 插入排序 希尔排序 归并排序 计数排序 桶排序 基数排序 注：“”表示排序时间太长，之内得不到排序结果。第期范兴国 等常见排序算法多线程实现与比较从表中可以看出，对于正序数据，与表随机数据结果类似，当随机数据的规模小于等于 时，所有排序算法都会在 之内完成排序。当正序数据规模大于 时，不同排序方法排序时间变化较大，冒泡排序、快速排序和选择排序这种方法的排序时间明显大于其他排序算法。比如对于 规模的正序数据，冒泡排序、快速排序和选择排序所用时间均超过了 ，而其他种排序算法所用时间均不到。根据表和表也可以得出，快速排序方法在处理正序数据时的效率远低于随机数据，说明快速排序方法更适合处理随机数据。整体来看，随着正序数据规模的增大，方法排序效率最高，表明 更适合处理大规模正序数据的排序。从表中可以看出，对于逆序数据，当逆序数据的规模小于等于 时，所有排序算法都会在 之内完成排序。当逆序数据规模大于 时，不同排序方法排序时间变化较大，冒泡排序、快速排序、选择排序和插入排序这种方法的排序时间明显大于其他排序算法。比如对于 的逆序数据，冒泡排序、快速排序、选择排序和插入排序所用时间超过了 ，而其他种排序算法所用时间均不到。根据表和表也可以得出，当数据规模大于 时，插入排序方法在处理逆序数据时的效率远低于随机数据，说明插入排序方法更适合处理随机数据。整体来看，随着逆序数据规模的增大，方法排序效率最高，表明 更适合处理大规模逆序数据的排序。含有重复数据的比较以上实验的所有测试数据均不包含重复数据，但现实生活中统计得到的数据有可能包含很多含有重复的数据，为了比较不同方法在含有重复数据的排序效率，本实验针对 随机数据，设 计 了 种 重 复 数 据（，和 ），表示在 随机数据里面，其中，和 的数据是重复数据。表是不同排序方法对含有重复数据的测试结果。可以看出，对于含有重复的数据，冒泡排序、快速排序、选择排序、插入排序、桶排序这种方法受重复数据的影响较大。比如对于插入排序方法，在 的重复数据下，排序时间需要 ，对于 的重复数据则需要 ，说明重复数据比例越大，插入排序方法所用时间越长。而其他种方法的排序结果不受重复数据的影响，排序时间没有太大的变化。整体来看，随着重复数据比例的增大，排序方法的排序时间变短，比如对于 的重复数据只需要 左右，说明该方法更适合处理含有重复的数据。表含有重复数据不同排序方法的排序时间（单位：）（）排序方法数据重复百分比 冒泡排序 快速排序 选择排序 堆排序 插入排序 希尔排序 归并排序 计数排序 桶排序 基数排序 多线程与单线程排序时间比较为了比较多线程排序的时间优势，用规模为 的随机数据，通过设定不同的线程数，观察不同排序方法的排序时间，结果如表所示。可以看出，对于同一组待排序数据，线程情况下的插入排序所用时间约为 ，而单线程情况下所用的排序时间约为 ，排序效率提高了近 倍。与插入排序结果类似，线程条件下的冒泡排序与选择排序也比相应的单线程快了近 倍，说明对于复杂度较高的排序方法，线程数越多，越能提高排序效率。多线程条件下，其他排序方法的排序时间也比对应的单线程排序效率宝鸡文理学院学报（自然科学版）年高，因此，借助于现在计算机 的多线程配置，通过增加设定的线程数，可以充分利用多线程资源，从而达到提高排序效率的目的。整体来看，冒泡排序、选择排序和插入排序这种算法的时间复杂度明显高于其他排序算法，因此，当数据量较大时，建议选择其他种排序方法。表不同线程数条件下的排序时间（单位：）（）排序方法线程数 冒泡排序 快速排序 选择排序 堆排序 插入排序 希尔排序 归并排序 计数排序 桶排序 基数排序 总结排序成为很多算法或软件处理数据的首要步骤，已成为计算机科学领域中最基本的操作之一。排序后的数据有明显的顺序性，可以呈现一定的规律性。因此，经过排序处理后的数据便于筛选和处理，提高了海量数据分析效率。针对 种常用经典排序算法，概述了各种排序算法的基本思想，并基于 语言对每种算法进行多线程实现，采用多种数据类型对比了不同类型数据、不同数据规模下的排序时间。结果表明，除了计数排序方法，其他 种排序方法均可通过多线程方式显著提高排序效率；对于规模为十亿级别（）的随机数据、正序数据和逆序数据，堆排序、希尔排序、归并排序、计数排序、基数排序和 种排序方法均可在 之内完成排序，且排序效率基本不受数据重复率的影响。因此，这些量化的排序执行时间有利于选择合理的排序算法。参考文献：时天元排序算法对比研究通讯世界，（）：王锦坤浅析基于语言的常用排序算法比较信息通信，（）：秦玉平，马靖善一种改进的计数排序算法渤海大学学报（自然科学版），（）：刘齐锐基本排序算法研究通讯世界，（）：贾思禹一种基于划分与归并的并行快速排序算法计算机与数字工程，（）：张帅，方欢，丁飞基于 语言对 种经典排序算法的 研 究 电 脑 知 识 与 技 术，（）：，张端 基于 语言常用排序算法的比较与研究电子世界，（）：张静常用排序算法的分析与比较河西学院学报，（）：翁子盛常见排序算法及其主要应用科学技术创新，（）：肖建华，寻大勇，赵艳红 排序算法中的分治策略 湖南工程学院学报，（）：王莉 各种内部排序算法的比较 黑龙江科技信息，（）：赵林洁，肖英，张宇 应用于大数据的 树排序算法 计算机工程与设计，（）：郭程远，陈鸿昶，王庚润，等复杂网络节点重要性排序算 法 及 应 用 综 述 信 息 工 程 大 学 学 报，（）：，（编校：李宗红）第期范兴国 等常见排序算法多线程实现与比较