线性时间复杂度排序算法探究和应用

《线性时间复杂度排序算法探究和应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、线性时间复杂度排序算法探究和应用　　摘要：算法在程序设计中起着至关重要的作用，一个好的算法可以让程序变得高效。排序作为数据处理最基本的工作之一，在程序中需要大量使用。常见的几种排序算法的平均时间复杂度最优为O（nlog2n），为从根本上提高程序的运行效率，对能够在线性时间解决数据排序的算法进行了研究，并在实际问题中对桶排序算法加以了应用。关键词：排序算法；线性时间复杂度；基数排序；桶排序中图分类号：TP301.6文献标识码：A文章编号：1672-7800（2013）006-0035-02作者简介：郭威（1

2、993-），男，中南财经政法大学信息与安全工程学院学生，研究方向为信息系统。0引言算法是完成特定任务的有限指令集[1]，程序的核心是算法。衡量一个算法好坏的性能指标有3个，即时间复杂度、空间复杂度和稳定性[2]。本文从算法时间复杂度的角度出发去寻找合适的算法。7排序是把一个无序的数据元素序列整理成有规律的、按排序关键字递增（或递减）排列的有序序列的过程。在许多程序中都要进行大量重复的数据处理，而对数据进行排序是许多数据处理的前提，所以一个好的排序算法往往能够大幅提高程序的效率。因此，需要寻找一种最优的排序

3、算法，来解决大量数据排序的问题。1常见排序算法排序算法根据排序数据是否一次读入内存分为内排序和外排序，本文主要讨论内排序算法。而内排序算法主要分为如下几大类：插入排序、交换排序、选择排序、归并排序这四大类[3]。插入排序是一种由初始的空集合开始，不断地通过比较数据的关键字把数据插入到合适位置的排序方法，主要有直接插入排序、折半插入排序和希尔排序。交换排序根据序列中两个记录键值的比较结果来交换两个记录在序列中的位置，直到最终完成所有交换，主要有冒泡排序和快速排序。选择排序是指每一趟从待排序的数据元素中选出最

4、小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完，主要有直接选择排序和堆排序。归并排序是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的，然后再把有序子序列合并为整体有序序列，常见的主要是二路归并算法。7这些常见的排序算法由于采取的思想和策略不同，因此各自的时间复杂度也不尽相同。而且，随着数据初始时顺序的不同，时间复杂度也会因此而变化。这些常见排序算法的时间复杂度如表1所示。根据表1可知，这些常见排序算法的平均时间复杂度最

5、优为O（nlog2n），没有在线性时间复杂度内完成排序，因而需要去寻找其它排序算法，从而达到在线性时间完成排序的目的。2线性时间复杂度排序算法常见排序算法的最优平均时间复杂度只能达到O（nlog2n），不能满足在线性时间完成排序的目的。时间和空间对于计算机来说是两个重要指标，彼此之间相互制衡。在一些特定环境中，可以牺牲某一个指标来换取另一个指标的效率。从这个角度出发，可以大胆猜想，是否在某些特定条件下，能够通过以空间换取时间的方法来达到最优线性时间复杂度的目的。经过探究和寻找，发现了基数排序[4-6]和桶

6、排序这两种排序算法，在待排序数据满足一定条件时，可以通过空间换取时间的方法来实现在线性时间完成排序这一目的。基数排序和桶排序都能满足要求，本文选择桶排序进行研究。2.1桶排序核心思想7桶排序假设输入的数据是在一个较小的范围内，而且在这个范围内数据基本是分布均匀。桶排序的核心思想就是对这些数据进行分析，建立模型，通过构造“桶”这个元素，将需要排序的数据依次放入对应的桶内，等到所有数据全部放入桶中后，按桶的顺序对数据进行输出就可以得到排序之后的结果。假设待排序的数据个数为n，而且是在区间[a，b）上均匀分布的

7、实数。桶排序将区间[a，b）划分成n个大小相等的子区间，也就是n个桶，每个桶的大小为1/（b-a）。将n个数据根据分布位置分配到对应的桶中，接着对每个桶中的数据进行排序[7，8]，最后按照桶的顺序对数据进行输出即可得到排序之后的数据。2.2桶排序实例现有1.4、5.3、3.4、6.7、3.6、8.7、4.9、2.3这8个数据需要排序，由于这些数据全部分布在区间[1.0～9.0）内，因此可以将区间等分为8个，从[1.0，2.0）到[8.0～9.0），分别编号为0、1…8，然后将数据放入对应的区间内。当桶内数

8、据不只一个时，需要对桶内数据采用常规排序方法进行排序。排序过程如图1所示。排序完成之后数据的顺序是：1.4、2.3、3.4、3.6、4.9、5.3、6.7、8.7，说明桶排序能够正确地解决排序问题。2.3桶排序时间复杂度分析7现对桶排序算法的时间复杂度进行分析，当数据在所处区间绝对分布均匀时，由于每个桶里最多只有一个数据，这样桶内的数据不需要排序，只需要将n个数据放入对应的桶内就可以了，这种条件下算法的时间复杂度为O（n）；而