算法分析与设计——排序问题(c++版)new

《算法分析与设计——排序问题(c++版)new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析与设计——排序问题（C++版）内容提要：本文主要介绍了几种常用的排序方法，包括冒泡法排序、快速排序、直接插入排序、希尔排序、选择排序、直接选择排序、堆排序、基数排序和归并排序。排序问题不仅理论上有研究价值，而且有广泛的应用。许多数据处理和情报检索算法中的重要部分都要对大量数据排序。故排序是许多有效算法中不可缺少的部分。关键字：冒泡法排序、快速排序、直接插入排序、希尔排序、选择排序、基数排序、归并排序引言：对集合S中的元素排序（Sorting），是指将这个元素序列，按某种“序特性”重新排列成一个有序排列。例如一个集合中的元素是实数，可以按实数的大小把它们排成一个非递减序或非递增序。对

2、于数据处理工作，排序是其最基本的运算之一。在当今的计算机系统中，花费在排序上的时间占系统CPU运行时间的很大比重。资料表明，在一些商用计算机上，用在排序上的CPU时间达到20%至60%。为了提高计算机的工作效率，人们提出了各种各样的排序方法和算法。这些算法有力地发展、并充分地展示了算法设计的某些重要原则和高超技巧。正文：1排序的定义排序是计算机程序设计中的一种重要运算，其功能是将一组任意排列的数据元（在排序中称为记录）重新排列成一个按关键字有序的序列。确切定义为：排序输入是n个记录A1,A2,…,An，其相应的关键字分别为K1,K2,…,Kn。排序输出是Ail,Ai2,…,Ain，使得Ki

3、1≤Ki2≤…≤Kin。（或Ki1≥Ki2≥…≥Kin）。排序问题的输入是一个线性表，该线性表的元素属于一个偏序集；要求对该线性表的元素做某种重排，使得线性表中除表尾外的每个元素都小于等于（或大于等于）它的后继。由于记录的形式、数量和所存放的存储设备不同，排序所采用的方法也不同。按照排序过程涉及的存储设备的不同，排序可分为内部排序（internalsorting）和外部排序（externalsorting）两大类。内部排序是指在排序的整个过程中，数据全部存放在计算机的内存贮器中，并且在内存贮器中调整记录间的相对位置，它适用于记录个数不太多的小文件；外部排序是指在排序过程中，数据的主要部分存

4、放在外存贮器中，借助内存贮器逐步调整记录之间的相对位置，适用于记录个数很多，不能一次将其全部记录都放入内存的大文件。本文先集中讨论内部排序的各种典型方法和算法，最后再简单介绍一下外部排序。内部排序的方法很多，如果按排序过程中依据的不同原则对内部排序方法进行分类，则主要有：插入排序、交换排序、选择排序、归并排序等四类（另一类“分配排序”，本书略去）。为了比较各种排序算法的优劣，要分析算法的时间复杂性的另一个主要因素。评价排序的另一个主要标准是执行算法所需要的附加空间。在没有特别说明时，本文以下各种排序方法中，均按递增序列并且假定待排序的数据存放在如下定义的存储结构上：#definenl00/

5、/假设的文件长度，即待排序的记录数目typedefintKeyType;//假设的关键字类型typedefstruct{//记录类型KeyTypekey;//关键字项InfoTypeotherinfo;//其他数据项，类型InfoType依赖于具体应用而定义}RecType;typedefstruct{RedTyper[n+1];//r[0]闲置或作用哨兵单元intlength;//顺序表的长度※1※}SqList//顺序表类型其中，key是排序时的关键字，实际中其类型可以为整型、实型或者字符串等。n为文件中待排序记录的总数。那什么样的排序方法是稳定的呢？什么样的排序算法是性能优良的呢？当

6、待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不惟一。在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。还需要强调一点，排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。排序算法性能评价排序算法好坏的标准主要有两条：执行时间和所需的辅助空间；算法本身的复杂程度。若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间是O(1)，则称之为就地排序（

7、In-PlaceSou）。非就地排序一般要求的辅助空间为O(n)。大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。2交换排序所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。2.1冒泡法排序冒泡排序（bubblesort）是一