内部排序..doc

各种内部排序算法的实现及性能比较 5.1 背景知识 排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。 学习和研究各种排序方法是计算机领域的重要课题之一。从第6章的有哪些信誉好的足球投注网站（查找）算法中可以看出，顺序表的查找时间复杂度为O（n），而建立在有序表基础上的折半查找的时间复杂度为O(log2n)。 内部排序是指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。 1.2.排序方法 内部排序的方法很多，但就其全面性而言，很难提出一种被认为是最好的方法，每一种方法都有其各自的优缺点，适合在不同的环境（如记录的初始排列状态等）下使用。如果按排序过程中依据的不同原则对内部排序方法进行分类，则排序大致可分为插入排序、交换排序、选择排序、归并排序、基数排序等5类；如果按内部排序过程中所需要的工作量（时间复杂度）来区分，则可分为以下3类： 1）简单的排序方法，时间复杂度为O(n2)的排序例如直接插入、直接选择和冒泡排序； 2）先进的排序方法，时间复杂度为O(nlogn)的排序快速、堆和归并排序3）基数排序：这是一种并非基于比较的排序，它借助多关键字的排序思想，通过“分配”和“收集”的方法来完成排序，时间复杂度为O（n）。 通常（除了上面的基数排序），在排序过程中需要进行下列两种基本操作： 1）比较两个记录关键字的大小 2）将记录从一个位置移动至另一个位置。 前一个操作对大多数排序方法来说是必要的，而后一个操作可以通过改变记录的存储方式来予以避免。 可以从不同的角度描述排序算法的性能，主要有如下几个： 1）排序算法的时间复杂度和空间复杂度 2）排序算法的稳定性 3）排序算法的简单性（代码编写的难易程度） 3.排序表数据结构 排序表是待排序记录的集合。在本次实验中，待排序的一组记录存放在地址连续的一组存储单元上。类似于线性表的顺序存储结构。 每个排序算法的实现都采用模板函数的方式，把实验中所有的排序算法都放在SortAlgorithm.h文件中。 5.2 实验目的 1）掌握常见的排序方法和实现排序的算法。 2）能根据待排序记录的关键字的初始状态选择合适的排序方法。 3）学会分析算法的基本方法，并计算算法的时间复杂度。 4）学会比较排序算法的性能。 5.3 工具/准备工作 在开始实验前，请回顾教科书中有关排序的定义及常见的内部排序算法。 需要一台计算机，其中装有Microsoft Visual C++6.0开发环境或DevCpp集成开发环境。 5.4 实验内容与步骤 5.4.1基础知识 1）三种计算时间为O(n2)的排序priority_queue是大顶堆。） 同学们可以自己编程序进行测试。 有关STL中的栈和队列的相关内容请参考： /eizi/blog/item/1e0c7c61fcec42d18db10df5.html 堆排序的基本思想如下： 第一步：为了得到非递减的排序序列，首先构造一个大顶堆。 第二步：for (i=n-1;i0;i--) //每循环一次进行一个根叶交换 交换a[i]和a[0] 使用向下调整算法，把a[0]～a[i-1]重新调整成大顶堆 具体的算法实现请参考教科书P196的程序10.7和程序10.8。 该算法的最好、最坏和平均情况的时间复杂度为O（nlog2n）。且为不稳定的排序方法。 3）树排序 我们可以利用二叉查找树完成排序，把这种排序方法称为树排序。只需要把列表元素插入到初始为空的二叉查找树BSTree中，然后使用中序遍历来把元素复制到列表中。 算法描述如下： template class T void TreeSort(T A[],int n) { BSTreeT tree; //构造一棵空树 for(int i=0;in;i++) tree.Insert(A[i]); int i=0; tree.InOrder(int i) //对中序遍历进行适当修改， //对某个结点访问也就是把结点的值赋给A[i]后再i++ } 同学们可以自己编程序进行测试。 2、插入排序 1）直接插入排序 直接插入排序的思想非常简单，将序列中第一个元素作为一个有序序列，然后将剩下的n-1个元素按关键字大小依次插入该有序序列，每插入一个元素后依然保持该序列有序，经过n-1趟排序后即成为有序序列。 直接插入排序算法请参考P189的程序10.2。 直接插入排序算法的最坏情况出现在当列表按相反方向排列的时候。时间复杂为O(n2)。最好情况为序列已经有序，时间复杂度为O(n)。该排序算法是稳定的排序方法。 对于短列表（包含20个左右的元素）和部分有序列表，在我们讨论的所有排序算法中，实验结果表明直接插入排序的性能最佳。 2