内部排序算法的时间复杂度分析
时间:2019-08-20 13:01 来源:毕业论文 作者:毕业论文 点击:次
| 摘 要：调度是一个最重要的内容是经常遇到的计算机程序设计，一般来说，它是收集数据，最重要的是重新排列成一个有序的序列.许多计算机排序方法多，因而有区别比较大的时间复杂度.本文从理论上探究了线性，对比和急速这些种常常利用的排序算法，以及对它们的的时间复杂度的解析.38910 毕业论文关键词：排序；算法；时间复杂度；解析 Analysis of Internal Sorting Algorithm Time Complexity Abstract：Sort is an important content, is often encountered in computer programming in general, it is the collection of data, the key re arranged in a sequence, and orderly. Many computer sorting method, the difference to the time complexity . This paper studies the linear ordering from the theory, several kinds of sort and quick sort and other commonly used sorting algorithm of linear time complexity. Key words：Sort; Algorithm;The Time Complexity; Analysis 目 录 摘 要 1 引言 2 1预备知识 3 1.1时间复杂度 3 2算法简介 3 2.1线性排序 3 2.1.1选择排序 4 2.1.2冒泡法 5 2.1.3计数法 5 2.2快速排序 6 2.3堆排序 7 2.4 比较排序 8 2.5快速分类 8 3算法分析 9 3.1排序算法比较 9 3.2排序方法的性能比较及选择 10 3.3算法性能评价 12 4总结 12 参考文献 13 致谢 15 内部排序算法的时间复杂度分析 引言 我们都知道，排序是计算机研究领域的一个重要的基础性课题，那么排序问题又是现实生活中经常出现的问题.凡是来讲，排列顺序有在内部排序和在外部排序的区分.文献[1]-[7]介绍的内部排序，是指对电脑存储器中尚未排序的数据，展开排序.这些算法的差异比较大，所以实现起来比较困难，而时间复杂度和空间复杂度是我们通常用来衡量算法的效能. 因为空间复杂度太过简便，因此在电脑储存空间逐渐变大的形势下，对于算法的时间复杂度的关注就更多了.就现在来看，电脑运行速率虽然很高，可是一旦算法不能被很好地设计，那么程序运转的效率也就不能从本质上变更. 于是，在提高电子设备运行速率的同时，我们也不能不看重探究程序的算法. 排序作为一种最常见的数据操作，通常排序操作的数据量都非常的大，为了节省排序的时间，对排序算法的速度要求通常来说都比较高.特别是一些大型数据库，由于它数据量很大，那么如何选择一个高效的排序算法就变得非常重要了. 文献[8]-[14]介绍在数据量小的时候，大多排序算法的性能都相差不多，但在数据量很大的时候，一些好的排序算法的优点就相当的明显了.衡量排序算法优劣的标准有很多，最常用的为时间复杂度和空间复杂度.对于内排序来说，我们通常不考虑空间复杂度，原因无非有两个：一是各种内排序算法的空间复杂度都相差不多，二是随着大规模集成电路的飞速地发展，存储器的价格在不断下降，空间复杂度已经不是主要的问题.而现有的计算机特别是用户数量最多的桌面微机，其计算能力相当有限，时间复杂度就成为一个核心问题. 对于内部排序来讲咱们能够用很多种方式实现.本文着重介绍一下几类算法. 1预备知识 1.1时间复杂度 一般来说，一个算法的执行时间，理论上是不可计算的.咱们根本就没有需要去每个测试算法，是以仅仅须要了解哪一类算法会花费更多的功夫，花更少的时间在它的求解上.花在算法的执行时间的算法的时间成正比，该算法执行多次，它需要更多的时间.我们把一个陈述中，算法的执行时间称为时间频率.在频率的时候，刚才提到的，当问题规模的变化，时间的频率也会不断变化.但我们想知道可能发生的变化规律.因此，在这里我们引入了时间复杂度的概念.人们在度量算法的效率时，往往会选择空间的复杂度和时间的复杂度. 因为空间复杂度太过简便，因此在电脑储存空间逐渐变大的形势下，对于算法的时间复杂度的关注就更多了. 排序算法的标准测量有诸多优点，最常用的就是时间复杂度. (责任编辑：qin) |