文档库 最新最全的文档下载
当前位置:文档库 › 数据结构之各种排序的实现与效率分析

数据结构之各种排序的实现与效率分析

数据结构之各种排序的实现与效率分析
数据结构之各种排序的实现与效率分析

各种排序的实现与效率分析

一、排序原理

(1)直接插入排序

基本原理:这是最简单的一种排序方法,它的基本操作是将一个记录插入到已排好的有序表中,从而得到一个新的、记录增1的有序表。

效率分析:该排序算法简洁,易于实现。从空间来看,他只需要一个记录的辅助空间,即空间复杂度为O(1).从时间来看,排序的基本操作为:比较两个关键字的大小和移动记录。当待排序列中记录按关键字非递减有序排列(即正序)时,所需进行关键字间的比较次数达最小值n-1,记录不需移动;反之,当待排序列中记录按关键字非递增有序排列(即逆序)时,总的比较次数达最大值(n+2)(n-1)/2,记录移动也达到最大值(n+4)(n-2)/2.由于待排记录是随机的,可取最大值与最小值的平均值,约为n2/4.则直接插入排序的时间复杂度为O(n2).由此可知,直接插入排序的元素个数n越小越好,源序列排序度越高越好(正序时时间复杂度可提高至O(n))。插入排序算法对于大数组,这种算法非常慢。但是对于小数组,它比其他算法快。其他算法因为待的数组元素很少,反而使得效率降低。插入排序还有一个优点就是排序稳定。

(2)折半插入排序

基本原理:折半插入是在直接插入排序的基础上实现的,不同的是折半插入排序在将数据插入一个有序表时,采用效率更高的“折半查找”来确定插入位置。

效率分析:由上可知该排序所需存储空间和直接插入排序相同。从时间上比较,折半插入排序仅减少了关键字间的比较次数,为O(nlogn)。而记录的移动次数不变。因此,折半查找排序的时间复杂度为O(nlogn)+O(n2)

= O(n2)。排序稳定。

(3)希尔排序

基本原理:希尔排序也一种插入排序类的方法,由于直接插入排序序列越短越好,源序列的排序度越好效率越高。Shell 根据这两点分析结果进行了改进,将待排记录序列以一定的增量间隔dk 分割成多个子序列,对每个子序列分别进行一趟直接插入排序, 然后逐步减小分组的步长dk,对于每一个步长dk 下的各个子序列进行同样方法的排序,直到步长为1 时再进行一次整体排序。因为不管记录序列多么庞大,关键字多么混乱,在先前较大的分组步长dk下每个子序列的规模都不大,用直接插入排序效率都较高。尽管在随后的步长dk 递减分组中子序列越来越大,但由于整个序列的有序性也越来越明显,则排序效率依然较高。这种改进抓住了直接插入排序的两点本质,大大提高了它的时间效率。

效率分析:希尔排序有以下几个关键特性:

(1) 希尔排序的核心是以某个增量dk 为步长跳跃分组进行插入排序,由于分组的步长dk 逐步缩小,所以也叫“缩小增量排序”插入排序。其关键是如何选取分组的步长序列才能使得希尔方法的时间效率最高;

(2) 待排序列记录的个数n 、跳跃分组步长逐步减小直到为1时所进行的扫描次数T、增量的和、记录关键字比较的次数以及记录移动的次数或各子序列中的反序数等因素都影响希尔算法的时间复杂度:其中记录关键字比较的次数是重要因素,它主要取决于分组步长序列的选择;

(3) 希尔方法是一种不稳定排序算法,因为其排序过程中各趟的步长不同,在第k 遍用dk 作为步长排序之后,第k +1 遍排序时可能会遇到多个逆序存在,影响排序的稳定性。

(3)冒泡排序

基本原理:冒泡排序分为若干趟进行,每一趟排序从前往后比较每两个相邻的元素的大小(因此一趟排序要比较n-1对位置相邻的数)并在每次发现前面的那个数比紧接它后的数大时交换位置;进行足够多趟直到某一趟跑完后发现这一趟没有进行任何交换操作(最坏情况下要跑n-1趟,这种情况在最小的数位于给定数列的最后面时发生)。事实上,在第一趟冒泡结束后,最后面那个数肯定是最大的了,于是第二次只需要对前面n-1个数排序,这又将把这n-1个数中最大的数放到整个数列的倒数第二个位置。这样下去,冒泡排序第i 趟结束后后面i个数都已经到位了,第i+1趟实际上只考虑前n-i个数(需要的比较次数比前面所说的n-1要小)。

效率分析:冒泡排序在给出的序列为正序排列时是最好的情况,这时每一次比较都不需要要进行交换操作。因此冒泡排序最好情况下需要交换0次。给出的序列逆序排列是最坏的情况,这时每一次比较都要进行交换操作。一次交换操作需要3次赋值实现,因此冒泡排序最坏情况下需要赋值3n(n-1)/2次。比较次数方面,无论数据如何,每次排序均要比较n(n-1)/2次。

(4)快速排序

基本原理:快速排序是对冒泡排序的一种改进,它的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

快速排序采用了分治法的思想,把大的问题分解为同类型的小问题。一般分如下步骤:(1)选择一个中枢元素(有很多选法,我的实现里使用第一个元素为中枢的简单方法)(2)以该中枢元素为基准点,将小于中枢的元素放在中枢后集合的前部分,比它大的在集合后部分,待集合基本排序完成后(此时前部分元素小于后部分元素),把中枢元素放在合适的位置。

(3)根据中枢元素最后确定的位置,把数组分成三部分,左边的,右边的,枢纽元素自己,对左边的,右边的分别递归调用快速排序算法即可。

这里的重点与难点在于第二步,这一步的方法是以第一个元素为中枢元素,刚开始时使用低指针指向中枢元素。当中枢元素在低指针位置时,此时我们判断高指针指向的元素是否小于中枢元素,如果大于中枢元素则高指针继续向头移动,如果小于则与中枢元素交换,此时中枢元素被移到了高指针位置;当中枢元素在高指针位置时,我们此时判断低指针指向的元素是否大于中枢元素,如果小于中枢元素则低指针继续向尾移动,如果大于则与中枢元素交换,此时中枢元素又回到了低指针位置;这时是拿高还是低指针所指向的元素与中枢比较时根据前面逻辑来处理,直到高低指针指向同一位置则完成一轮排序,然后再对中枢元素两边的序列进行同样的操作直到排序完成

效率分析:快速排序的平均时间为kn ln(n),其中n为待排时间中记录的个数,k为某个常数,经验证明,在所有同数量级的此类排序方法中,快速排序的常数因子k最小。因此,就平均时间而言,快速排序时最好的一种内部排序。快速排序在最好的情况时是正序,比较次数和移动次数均为O(n ln(n)),最坏状况下,比较次数和移动次数均为n(n-1)/2次。

(5)简单选择排序

基本原理:每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。

选择排序不像冒泡排序算法那样先并不急于调换位置,第一轮(i=1)先从array[i]开始逐个检查,看哪个数最小就记下该数所在的位置于min中,等一轮扫描完毕,如果找到比array[i-1]更小的元素,则把array[min]和a[i-1]对调,这时array[i]到最后一个元素中最小

的元素就换到了array[i-1]的位置。如此反复进行第二轮、第三轮…直到循环至最后一元素效率分析:选择排序在第i次选择时赋值和比较都需要n-i次(在n-i+1个数中选一个出来作为当前最小值,其余n-i个数与当前最小值比较并不断更新当前最小值),然后需要一次赋值操作。总共需要n(n-1)/2次比较。交换次数与序列的初始排列有关。交换在最好状况下是待排数据为正序,交换为0次。最坏情况是每一趟都要进行交换,总的对象移动次数为3(n-1)直接选择排序是一种不稳定的排序方法。

(6)堆排序

基本原理:堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。堆排序其实最主要的两个过程:第一步,创建初始堆;第二步,交换根节点与最后一个非叶子节

第一步:从最后一个非叶子节点为开始向前循环每个会支节点,比较每个分支节点与他左右子节点,如果其中某个子节点比父节点大,则与父节点交换,交换后原父节点可能还小于原子节点的子节点,所以还需对原父节点进行调整,使用原父节点继续下沉,直到没有子节点或比左右子节点都大为止,调用过程可通过递归完成。当某个非叶子节点调整完毕后,再处理下一个非叶子节点,直到根节点也调整完成,这里初始堆就创建好了,这里我们创建的是大顶堆,即大的元素向树的根浮,这样排序最后得到的结果为升序,因为最大的从树中去掉,并从数组最后往前存放。第二步:将树中的最后一个元素与堆顶元素进行交换,并从树中去掉最后叶子节点。交换后再按创建初始堆的算法调整根节点,如此下去直到树中只有一个节点为止。

效率分析:堆排序对n较大的文件还是有效的,对记录较少的文件效率较低。因为堆排序其主要运行时间都耗费在建初始对和调整建新堆时进行的反复筛选上。对深度为k的对,筛选中关键字比较次数最多为2(n-1)次,则在建含n个元素、深度为h的堆时,总进行的关键字比较次数不超过4n。由此,堆排序在最坏的情况下,其时间复杂度为O(n ln(n))。

(7)归并排序

基本原理:归并排序分两步操作:第一步将数组分解成更小的数组,直到数组只有一个元素为止,每次划分点为(len – 1)/2=mid,将数组分成[from,mid]和[mid+1,to],第二步就是将分解的数组两两合并,合并后的数组是有序的,直到合并成一个数组为止,合并过程中会用到一个临时数组,用来存储合并后的结果。每次合并后,将数组的数据传给原数组对应的位置。

二、测试数据

(2)当n = 100时的一组随机数据的测试结果:

(4)当n = 500时的一组随机数据的测试结果:

(5)具体有序数据的(数组元素为1~10)的测试结果:

三、分析

前面所述的各种方法各有优点适用场合也不同。通常选择排序方法的是考虑的因素有如下4点:

(1)待排序的记录数目n的大小

(2)记录本身数据量的大小,即记录中除关键字外其他信息量的大小

(3)关键字结构及其分布情况

(4)堆排序的稳定性要求

从以上实验结果可观察的结论如下:

(1)如果待排记录的个数n较小,则可采用直接插入排序或折半插入排序

(2)如果待排记录的个数n较大,应该选择时间复杂度为O(n ln(n))的排序方法,如快速排序,堆排序或归并排序。

<1>快速排序是处理大量数据的最好方法。当待排序序列的关键字是随机分布时,

快速排序的平均时间复杂度最优,但是在待排序序列基本有序时,将蜕化为冒泡排序,其时间性能将不如堆排序或归并排序。

<2>堆排序所需的辅助空间少于快速排序,并且在最坏的情况下时间复杂度不会变

化。

<3>归并排序所需的时间比堆排序省,但是它所需的辅助存储空间最多

(3)快速排序、堆排序、希尔排序和直接选择排序都是不稳定的排序法,直接插入排序法、冒泡排序法、归并排序法都是稳定的排序法。

(4)如果待排序列记录的厨师状态已按关键字基本有序,则选择直接插入排序或冒泡排序。

实验总结:排序算法的性能分析和选择是一个复杂而又实际的问题,文中讨论的仅仅是这6 种排序算法的平均时间性能. 在实际应用中,应根据经验和实际情况合理选择算法. 例如, 从平均时间性能而言,快速排序无疑是最优的,其所需时间最省,但快速排序在最坏情况下的时性能却不如堆排序和归并排序. 又比如,在插入排序、冒泡排序和选择排序中,以直接插入排为最简单,当序列中的记录“基本有序”或问题规模n 较小时,它是最佳的排序方法. 因此常将它和其他的排序方法,诸如快速排序、归并排序等结合在一起使用.

计算机专业基础综合数据结构(排序)-试卷2

计算机专业基础综合数据结构(排序)-试卷2 (总分:56.00,做题时间:90分钟) 一、单项选择题(总题数:16,分数:32.00) 1.单项选择题1-40小题。下列每题给出的四个选项中,只有一个选项是最符合题目要求的。(分数: 2.00)__________________________________________________________________________________________ 解析: 2.采用简单选择排序,比较次数与移动次数分别为( )。 (分数:2.00) A.O(n),O(log 2 n) B.O(log 2 n),O(n 2 ) C.O(n 2 ),O(n) √ D.O(nlog 2 n),O(n) 解析:解析:简单选择排序的关键字比较次数KCN与对象的初始排列无关。第i趟选择具有最小关键字对象所需的比较次数总是n—i—1次(此处假定整个待排序对象序列有n个对象)。因此,总的关键字比较次 最坏情况是每一趟都要进行交换,总的对象移动次数为RMN=3(n一1)。 3.就排序算法所用的辅助空间而言,堆排序、快速排序、归并排序的关系是( )。 (分数:2.00) A.堆排序<快速排序<归并排序√ B.堆排序<归并排序<快速排序 C.堆排序>归并排序>快速排序 D.堆排序>快速排序>归并排序 解析:解析:此题考查的知识点为排序的空间复杂性。堆排序辅助空间为O(1),快速排序为O(log 2 n),归并排序为O(n)。应选A。 4.一组记录的关键码为(25,48,16,35,79,82,23,40,36,72),其中,含有5个长度为2的有序表,按归并排序的方法对该序列进行一趟归并后的结果为( )。 (分数:2.00) A.16,25,35,48,23,40,79,82,36,72 √ B.16,25,35,48,79,82,23,36,40,72 C.16,25,48,35,79,82,23,36,40,72 D.16,25,35,48,79,23,36,40,72,82 解析:解析:对于(25,48,16,35,79,82,23,40,36,72),(25,48)和(16,35)归并的结果为(16,25,35,48)。(79,82)和(23,40)归并后的结果为(23,40,79,82),余下的两个记录不归并,所以一趟归并后的结果为(16,25,35,48,23,40,79,82,36,72),本题答案为A。 5.已知10个数据元素为(54,28,16,34,73,62,95,60,26,43),对该序列按从小到大排序,经过一趟冒泡排序后的序列为( )。 (分数:2.00) A.16,28,34,54,73,62,60,26,43,95 B.28,16,34,54,62,73,60,26,43,95 √ C.28,16,34,54,62,60,73,26,43,95 D.16,28,34,54,62,60,73,26,43,95 解析:解析:冒泡排序每趟经过比较、交换,从无序区中产生一个最大的元素,所以选B。 6.用某种排序方法对线性表(25,84,21,47,15,27,68,35,20)进行排序时,元素序列的变化情况如下: (1)25,84,21,47,15,27,68,35,20 (2)20,15,21,25,47,27,68,35,84 (3)15,20,21,25,35,27,47,68,84 (4)15,20,21,25,27,35,47,68,84 其所采用的排序方法是( )。(分数:2.00) A.直接选择排序√

数据结构课程设计(内部排序算法比较_C语言)

数据结构课程设计 课程名称:内部排序算法比较 年级/院系:11级计算机科学与技术学院 姓名/学号: 指导老师: 第一章问题描述 排序是数据结构中重要的一个部分,也是在实际开发中易遇到的问题,所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决!该系统通过对各种内部排序算法如直接插入排序,冒泡排序,简单选择排序,快速排序,希尔排序,堆排序、二路归并排序等,以关键码的比较次数和移动次数分析其特点,并进行比较,估算每种算法的时间消耗,从而比较各种算法的优劣和使用情况!排序表的数据是多种不同的情况,如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。

第二章系统分析 界面的设计如图所示: |******************************| |-------欢迎使用---------| |-----(1)随机取数-------| |-----(2)自行输入-------| |-----(0)退出使用-------| |******************************| 请选择操作方式: 如上图所示该系统的功能有: (1):选择1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并 打印出结果。 (2)选择2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 (3)选择0 打印“谢谢使用!!”退出系统的使用!! 第三章系统设计 (I)友好的人机界面设计:(如图3.1所示) |******************************| |-------欢迎使用---------| |-----(1)随机取数-------| |-----(2)自行输入-------| |-----(0)退出使用-------|

数据结构排序习题

07排序 【单选题】 1. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较,然后将其放在已排序序列的合适位置,该排序方法称为(A)排序法。 A、直接插入 B、简单选择 C、希尔 D、二路归并 2. 直接插入排序在最好情况下的时间复杂度为(B)。 A、O(logn) B、O(n) C、O(n*logn) D、O(n2) 3. 设有一组关键字值(46,79,56,38,40,84),则用堆排序的方法建立的初始堆为(B)。 A、79,46,56,38,40,80 B、84,79,56,38,40,46 C、84,79,56,46,40,38 D、84,56,79,40,46,38 4. 设有一组关键字值(46,79,56,38,40,84),则用快速排序的方法,以第一个记录为基准得到的一次划分结果为(C)。 A、38,40,46,56,79,84 B、40,38,46,79,56,84 C、40,38,46,56,79,84 D、40,38,46,84,56,79 5. 将两个各有n个元素的有序表归并成一个有序表,最少进行(A)次比较。 A、n B、2n-1 C、2n D、n-1 6. 下列排序方法中,排序趟数与待排序列的初始状态有关的是(C)。 A、直接插入 B、简单选择 C、起泡 D、堆 7. 下列排序方法中,不稳定的是(D)。 A、直接插入 B、起泡 C、二路归并 D、堆 8. 若要在O(nlog2n)的时间复杂度上完成排序,且要求排序是稳定的,则可选择下列排序方法中的(C)。 A、快速 B、堆 C、二路归并 D、直接插入 9. 设有1000个无序的数据元素,希望用最快的速度挑选出关键字最大的前10个元素,最好选用(C)排序法。 A、起泡 B、快速 C、堆 D、基数 10. 若待排元素已按关键字值基本有序,则下列排序方法中效率最高的是(A)。 A、直接插入 B、简单选择 C、快速 D、二路归并 11. 数据序列(8,9,10,4,5,6,20,1,2)只能是下列排序算法中的(C)的两趟排序后的结果。 A、选择排序 B、冒泡排序 C、插入排序 D、堆排序 12. (A)占用的额外空间的空间复杂性为O(1)。 A、堆排序算法 B、归并排序算法 C、快速排序算法 D、以上答案都不对

数据结构第十章习题课

1.下列排序算法中,其中()是稳定的。 A. 堆排序,冒泡排序 B. 快速排序,堆排序 C. 直接选择排序,归并排序 D. 归并排序,冒泡排序 2.若需在O(nlog2n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是()。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序3.排序趟数与序列的原始状态有关的排序方法是( )排序法。 A.插入 B. 选择 C. 冒泡 D. 快速4.对一组数据(84,47,25,15,21)排序,数据的排列次序在排序的过程中 的变化为(1)84 47 25 15 21 (2)15 47 25 84 21 (3)15 21 25 84 47 (4) 15 21 25 47 84 则采用的排序是( )。 A. 选择 B. 冒泡 C. 快速 D. 插入5.对序列{15,9,7,8,20,-1,4}进行排序,进行一趟后数据的排列变为{4,9,-1,8,20,7,15};则采用的是()排序。 A. 选择 B. 快速 C. 希尔 D. 冒泡6.若上题的数据经一趟排序后的排列为{9,15,7,8,20,-1,4},则采用的 是()排序。 A.选择 B. 堆 C. 直接插入 D. 冒泡 7.在文件“局部有序”或文件长度较小的情况下,最佳内部排序的方法是()A.直接插入排序B.冒泡排序C.简单选择排序 8.下列排序算法中,()算法可能会出现下面情况:在最后一趟开始之前,所有元素都不在其最终的位置上。 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 插入排序 9. 下列排序算法中,占用辅助空间最多的是:( ) A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序10.用直接插入排序方法对下面四个序列进行排序(由小到大),元素比较次数 最少的是()。 A.94,32,40,90,80,46,21,69 B.32,40,21,46,69,94,90,80 C.21,32,46,40,80,69,90,94 D.90,69,80,46,21,32,94,40 11. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序,需进行()次比较。 A. 3 B. 10 C. 15 D. 25 12.对n个记录的线性表进行快速排序为减少算法的递归深度,以下叙述正确

数据结构各种排序方法的综合比较

数据结构各种排序方法的综合比较 结论: 排序方法平均时间最坏时间辅助存储 简单排序O(n2) O(n2) O(1) 快速排序O(nlogn)O(n2)O(logn) 堆排序O(nlogn)O(nlogn)O(1) 归并排序O(nlogn)O(nlogn)O(n) 基数排序O(d(n+rd))O(d(n+rd))O(rd) PS:直接插入排序、冒泡排序为简单排序,希尔排序、堆排序、快速排序为不稳定排序 一、时间性能 按平均的时间性能来分,有三类排序方法: 时间复杂度为O(nlogn)的方法有:快速排序、堆排序和归并排序,其中以快速排序为最好;时间复杂度为O(n2)的有:直接插入排序、起泡排序和简单选择排序,其中以直接插入为 最好,特别是对那些对关键字近似有序的记录序列尤为如此; 时间复杂度为O(n)的排序方法只有,基数排序。 当待排记录序列按关键字顺序有序时,直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言,这是最不好的情况,此时的时间性能蜕化为O(n2),因此是应该尽量避免的情况。简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。 二、空间性能 指的是排序过程中所需的辅助空间大小。 1. 所有的简单排序方法(包括:直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1); 2. 快速排序为O(logn),为栈所需的辅助空间; 3. 归并排序所需辅助空间最多,其空间复杂度为O(n ); 4.链式基数排序需附设队列首尾指针,则空间复杂度为O(rd)。 三、排序方法的稳定性能 1. 稳定的排序方法指的是,对于两个关键字相等的记录,它们在序列中的相对位置,在排序之前和经过排序之后,没有改变。 2. 当对多关键字的记录序列进行LSD方法排序时,必须采用稳定的排序方法。 3. 对于不稳定的排序方法,只要能举出一个实例说明即可。 4. 快速排序和堆排序是不稳定的排序方法

数据结构实验八内部排序

实验八内部排序 一、实验目的 1、掌握内部排序的基本算法; 2、分析比较内部排序算法的效率。 二、实验内容和要求 1. 运行下面程序: #include #include #define MAX 50 int slist[MAX]; /*待排序序列*/ void insertSort(int list[], int n); void createList(int list[], int *n); void printList(int list[], int n); void heapAdjust(int list[], int u, int v); void heapSort(int list[], int n); /*直接插入排序*/ void insertSort(int list[], int n) { int i = 0, j = 0, node = 0, count = 1; printf("对序列进行直接插入排序:\n"); printf("初始序列为:\n"); printList(list, n); for(i = 1; i < n; i++) { node = list[i]; j = i - 1; while(j >= 0 && node < list[j]) { list[j+1] = list[j]; --j; } list[j+1] = node; printf("第%d次排序结果:\n", count++); printList(list, n); } } /*堆排序*/ void heapAdjust(int list[], int u, int v)

数据结构(本)期末综合练习

数据结构(本)期末综合练习 综合练习一 一、单项选择题 1.设有头指针为head的带有头结点的非空单向循环链表, 指针p指向其尾结点, 要删除头结点,并使其仍为单向循环链表,则可利用下述语句head =head->next ;()。 A.p =head; B.p=NULL; C.p->next =head; D.head=p; 2.在一个单链表中p指向结点a, q指向结点a的直接后继结点b,要删除结点b,可执行()。 A.p->next=q->next ; B.p=q->next; C.p->next=q; D.p->next=q; 3. 以下说法不正确的是 A. 线性表的链式存储结构不必占用连续的存储空间 B.一种逻辑结构只能有唯一的存储结构 C. 一种逻辑结构可以有不同的存储结构 D.线性表的顺序存储结构必须占用连续的存储空间 4.在一个单向链表中,在p所指结点之后插入一个s所指的结点时,可执行();和p->next=s; A.p= s; B.p->next=s->next; C.p=s->next; D.s->next=p->next; 5.把数据存储到计算机中,并具体体现( )称为物理结构。 A. 数据元素间的逻辑关系 B.数据的处理方法 C.数据的性质 D.数据的运算 6.设有一个长度为23的顺序表,要删除第8个元素需移动元素的个数为()。 A.16 B.14 C.15 D.13 7.链表所具备的特点之一是()。 A.可以随机访问任一结点B.需要占用连续的存储空间 C.插入元素的操作不需要移动元素D.删除元素的操作需要移动元素 8.设一棵有8个叶结点的二叉树,度数为1的结点有3个,则该树共有() 个结点。 A.20 B.18 C.17 D.16 9.图状结构中数据元素的位置之间存在()的关系。 A.一对一B.多对多 C.一对多D.每一个元素都有一个直接前驱和一个直接后继 10.一棵具有5层的完全二叉树,最后一层有4个结点,则该树总共有()个结点。 A.14 B.15 C.19 D.18 11.元素15,9,11,13按顺序依次进栈,则该栈的不可能输出序列是() (进栈出栈可以交替进行)。 A.13,11,9,15 B.15,9,11,13 C.13,11,15,9 D.9,15,13,11 12.设主串为“FABcCDABcdEFaBc”,以下模式串能与主串成功匹配的是()。 A. EFaBc B. ABCdE C. DABCC D .FAbcC 13.设有一个14阶的对称矩阵A(第一个元素为a1,1),采用压缩存储的方式,将其下三角部分以行序为主序存

数据结构中的内部排序算法及性能分析

数据结构中的排序算法及性能分析 一、引言 排序(sorting )是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。为了查找方便通常希望计算机中的表是按关键字有序的。因为有序的顺序表可以使用查找效率较高的折半查找法。 在此首先明确排序算法的定义: 假设n 个记录的序列为 { 1R ,2R ,…n R } (1) 关键字的序列为: { 1k ,2k ,…,n k } 需要确定1,2,…,n 的一种排列:12,n p p p ,…,使(1)式的序列成为一个按关键字有序的序列: 12p p pn k k k ≤≤≤… 上述定义中的关键字Ki 可以是记录Ri (i=1,2,…,n )的主关键字,也可以是记录i R 的次关键字,甚至是若干数据项的组合。若在序列中有关键字相等的情况下,即存在i k =j k (1,1,i n j n i j ≤≤≤≤≠),且在排序前的序列中i R 领先于j R 。若在排序后的序列中Ri 仍领先于j R ,则称所用的排 序方法是稳定的;反之若可能使排序后的序列中j R 领先于i R ,则称所用的排序方法是不稳定的。 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法的时间与算法中语句执行次数成正比,那个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度,记为T(n)。 在刚才提到的时间频度中,n 称为问题的规模,当n 不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。 一般情况下,算法中基本操作重复执行的次数是问题规模n 的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n 趋近于无穷大时,T (n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。

数据结构各种排序算法的时间性能

HUNAN UNIVERSITY 课程实习报告 题目:排序算法的时间性能学生姓名 学生学号 专业班级 指导老师李晓鸿 完成日期

设计一组实验来比较下列排序算法的时间性能 快速排序、堆排序、希尔排序、冒泡排序、归并排序(其他排序也可以作为比较的对象) 要求 (1)时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时间性能等。 (2)实验数据应具有说服力,包括:数据要有一定的规模(如元素个数从100到10000);数据的初始特性类型要多,因而需要具有随机性;实验数据的组数要多,即同一规模的数组要多选几种不同类型的数据来实验。实验结果要能以清晰的形式给出,如图、表等。 (3)算法所用时间必须是机器时间,也可以包括比较和交换元素的次数。 (4)实验分析及其结果要能以清晰的方式来描述,如数学公式或图表等。 (5)要给出实验的方案及其分析。 说明 本题重点在以下几个方面: 理解和掌握以实验方式比较算法性能的方法;掌握测试实验方案的设计;理解并实现测试数据的产生方法;掌握实验数据的分析和结论提炼;实验结果汇报等。 一、需求分析 (1) 输入的形式和输入值的范围:本程序要求实现各种算法的时间性能的比 较,由于需要比较的数目较大,不能手动输入,于是采用系统生成随机数。 用户输入随机数的个数n,然后调用随机事件函数产生n个随机数,对这些随机数进行排序。于是数据为整数 (2) 输出的形式:输出在各种数目的随机数下,各种排序算法所用的时间和 比较次数。 (3) 程序所能达到的功能:该程序可以根据用户的输入而产生相应的随机 数,然后对随机数进行各种排序,根据排序进行时间和次数的比较。 (4)测试数据:略 二、概要设计

数据结构综合练习题

数据结构综合练习题

数据结构(一) 一、选择题 1.组成数据的基本单位是( C )。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2.设数据结构A=(D,R),其中D={1,2,3,4},R={r},r={<1,2>,<2,3>,<3,4>,<4,1>},则数据结构A 是( C )。 (A) 线性结构(B) 树型结构(C) 图型结构(D) 集合 3.数组的逻辑结构不同于下列( D )的逻辑结构。(A) 线性表(B) 栈(C) 队列(D) 树 4.二叉树中第i(i≥1)层上的结点数最多有(C )个。 (A) 2i (B) 2i(C) 2i-1(D) 2i-1 5.设指针变量p指向单链表结点A,则删除结点A的后继结点B需要的操作为(A )。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 6.设栈S和队列Q的初始状态为空,元素E1、E2、E3、E4、E5和E6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出列的顺序为E2、E4、E3、E6、E5和E1,则栈S的容量至少应该是( C )。 (A) 6 (B) 4 (C) 3 (D) 2

7.将10阶对称矩阵压缩存储到一维数组A中,则数组A 的长度最少为( C )。 (A) 100 (B) 40 (C) 55 (D) 80 8.设结点A有3个兄弟结点且结点B为结点A的双亲结点,则结点B的度数数为( B )。 (A) 3 (B) 4 (C) 5 (D) 1 9.根据二叉树的定义可知二叉树共有( B )种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10.设有以下四种排序方法,则( B )的空间复 杂度最大。 (A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序 11、以下说法正确的是( A ) A.连通图的生成树,是该连通图的一个极小连通子图。 B.无向图的邻接矩阵是对称的,有向图的邻接矩阵一定是不对称的。 C.任何一个有向图,其全部顶点可以排成一个拓扑序列。 D.有回路的图不能进行拓扑排序。 12、以下说法错误的是 ( D ) A.一般在哈夫曼树中,权值越大的叶子离根结点越近 B.哈夫曼树中没有度数为1的分支结点 C.若初始森林中共有n裸二叉树,最终求得的哈夫曼树

数据结构课程设计(内部排序算法比较 C语言)

课题:内部排序算法比较 第一章问题描述 排序是数据结构中重要的一个部分,也是在实际开发中易遇到的问题,所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决!该系统通过对各种内部排序算法如直接插入排序,冒泡排序,简单选择排序,快速排序,希尔排序,堆排序、二路归并排序等,以关键码的比较次数和移动次数分析其特点,并进行比较,估算每种算法的时间消耗,从而比较各种算法的优劣和使用情况!排序表的数据是多种不同的情况,如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。 第二章系统分析 界面的设计如图所示: |******************************| |-------欢迎使用---------| |-----(1)随机取数-------|

|-----(2)自行输入-------| |-----(0)退出使用-------| |******************************| 请选择操作方式: 如上图所示该系统的功能有: (1):选择 1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并打印出结果。 (2)选择 2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 (3)选择0 打印“谢谢使用!!”退出系统的使用!! 第三章系统设计 (I)友好的人机界面设计:(如图3.1所示) |******************************| |-------欢迎使用---------| |-----(1)随机取数-------| |-----(2)自行输入-------| |-----(0)退出使用-------| |******************************| (3.1) (II)方便快捷的操作:用户只需要根据不同的需要在界面上输入系统提醒的操作形式直接进行相应的操作方式即可!如图(3.2所示) |******************************| |-------欢迎使用---------| |-----(1)随机取数-------| |-----(2)自行输入-------| |-----(0)退出使用-------|

数据结构 各种排序算法

数据结构各种排序算法总结 2009-08-19 11:09 计算机排序与人进行排序的不同:计算机程序不能象人一样通览所有的数据,只能根据计算机的"比较"原理,在同一时间内对两个队员进行比较,这是算法的一种"短视"。 1. 冒泡排序 BubbleSort 最简单的一个 public void bubbleSort() { int out, in; for(out=nElems-1; out>0; out--) // outer loop (backward) for(in=0; in a[in+1] ) // out of order? swap(in, in+1); // swap them } // end bubbleSort() 效率:O(N2) 2. 选择排序 selectSort public void selectionSort() { int out, in, min; for(out=0; out

swap(out, min); // swap them } // end for(out) } // end selectionSort() 效率:O(N2) 3. 插入排序 insertSort 在插入排序中,一组数据在某个时刻实局部有序的,为在冒泡和选择排序中实完全有序的。 public void insertionSort() { int in, out; for(out=1; out0 && a[in-1] >= temp) // until one is smaller, { a[in] = a[in-1]; // shift item to right --in; // go left one position } a[in] = temp; // insert marked item } // end for } // end insertionSort() 效率:比冒泡排序快一倍,比选择排序略快,但也是O(N2) 如果数据基本有序,几乎需要O(N)的时间

数据结构第九、十章 作业答案

第九章 查找 一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找(线性查找) 。 2. 线性有序表(a 1,a 2,a 3,…,a 256)是从小到大排列的,对一个给定的值k ,用二分法检索 表中与k 相等的元素,在查找不成功的情况下,最多需要检索 8 次。设有100个结点,用二分法查找时,最大比较次数是 7 。 3. 假设在有序线性表a[1..20]上进行折半查找,则比较一次查找成功的结点数为1;比较两次查找成功的结点数为 2 ;比较四次查找成功的结点数为 8 ,其下标从小到大依次是1,3,6,8,11,13,16,19______,平均查找长度为 3.7 。 解:显然,平均查找长度=O (log 2n )<5次(25)。但具体是多少次,则不应当按照公式 )1(log 12++=n n n ASL 来计算(即(21×log 221)/20=4.6次并不正确!)。因为这是在假设n =2m -1 的情况下推导出来的公式。应当用穷举法罗列: 全部元素的查找次数为=(1+2×2+4×3+8×4+5×5)=74; ASL =74/20=3.7 !!! 4.折半查找有序表(4,6,12,20,28,38,50,70,88,100),若查找表中元素20,它 将依次与表中元素 28,6,12,20 比较大小。 5. 在各种查找方法中,平均查找长度与结点个数n 无关的查找方法是 散列查找 。 6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。 7. 有一个表长为m 的散列表,初始状态为空,现将n (n

计算机专业基础综合数据结构(排序)历年真题试卷汇编1

计算机专业基础综合数据结构(排序)历年真题试卷汇编1 (总分:72.00,做题时间:90分钟) 一、单项选择题(总题数:15,分数:30.00) 1.下列序列中,( )是执行第一趟快速排序后所得的序列。【福州大学1998一、9(2分)】 A.[68,11,18,69] [23,93,73] B.[68,11,69,23] [18,93,73] C.[93,73][68,11,69,23,18] √ D.[68,11,69,23,18] [93,73] 枢轴是73。 2.适合并行处理的排序算法是( )。【西安电子科技大学2005一、8(1分)】【电子科技大学2005一、8(1分)】 A.选择排序 B.快速排序√ C.希尔排序 D.基数排序 3.一组记录的关键字为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为( )。【北京交通大学2005一、8(2分)【燕山大学2001一、4(2分)】 A.(38,40,46,56,79,84) B.(40,38,46,79,56,84) C.(40,38,46,56,79,84) √ D.(40,38,46,84,56,79) 如何对一趟快速排序的结果在最短的时间内做出正确判断,这里给出建议:首先84应该不动,所以D排除了;接着40应调到序列首,所以A排除了;接着79应调到移走40的空位上,B排除了。选择答案C,不必再继续做了(假定确有唯一正确答案)。 4.下列排序算法中,( )算法可能会出现下面的情况:初始数据有序时,花费的时间反而最多。【中南大学2005一、4(2分)】 A.快速排序√ B.堆排序 C.希尔排序 D.冒泡排序 5.将一组无序的数据重新排列成有序序列,其方法有:( )。【武汉理工大学2004一、8(3分)】 A.拓扑排序 B.快速排序√ C.堆排序√ D.基数排序√ 6.就平均性能而言,目前最好的内排序方法是( )排序法。【西安电子科技大学1998一、9(2分)】 A.冒泡 B.希尔插,A C.交换 D.快速√ 7.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列,用( )方法最快。【清华大学1998一、2(2分)】 A.起泡排序 B.快速排列 C.Shell排序 D.堆排序√ E.简单选择排序

数据结构-各类排序算法总结

数据结构-各类排序算法总结 原文转自: https://www.wendangku.net/doc/6e98866.html,/zjf280441589/article/details/38387103各类排序算法总结 一. 排序的基本概念 排序(Sorting)是计算机程序设计中的一种重要操作,其功能是对一个数据元素集合或序列重新排列成一个按数据元素 某个项值有序的序列。 有n 个记录的序列{R1,R2,…,Rn},其相应关键字的序列是{K1,K2,…,Kn},相应的下标序列为1,2,…,n。通过排序,要求找出当前下标序列1,2,…,n 的一种排列p1,p2,…,pn,使得相应关键字满足如下的非递减(或非递增)关系,即:Kp1≤Kp2≤…≤Kpn,这样就得到一个按关键字有序的记录序列{Rp1,Rp2,…,Rpn}。 作为排序依据的数据项称为“排序码”,也即数据元素的关键码。若关键码是主关键码,则对于任意待排序序列,经排序后得到的结果是唯一的;若关键码是次关键码,排序结果可

能不唯一。实现排序的基本操作有两个: (1)“比较”序列中两个关键字的大小; (2)“移动”记录。 若对任意的数据元素序列,使用某个排序方法,对它按关键码进行排序:若相同关键码元素间的位置关系,排序前与排序后保持一致,称此排序方法是稳定的;而不能保持一致的排序方法则称为不稳定的。 二.插入类排序 1.直接插入排序直接插入排序是最简单的插入类排序。仅有一个记录的表总是有序的,因此,对n 个记录的表,可从第二个记录开始直到第n 个记录,逐个向有序表中进行插入操作,从而得到n个记录按关键码有序的表。它是利用顺序查找实现“在R[1..i-1]中查找R[i]的插入位置”的插入排序。

南邮数据结构上机实验四内排序算法的实现以及性能比较

实验报告 (2015 / 2016学年第二学期) 课程名称数据结构A 实验名称内排序算法的实现以及性能比较 实验时间2016 年 5 月26 日 指导单位计算机科学与技术系 指导教师骆健 学生姓名耿宙班级学号B14111615 学院(系) 管理学院专业信息管理与信息系统

—— 实习题名:内排序算法的实现及性能比较 班级 B141116 姓名耿宙学号 B14111615 日期2016.05.26 一、问题描述 验证教材的各种内排序算法,分析各种排序算法的时间复杂度;改进教材中的快速排序算法,使得当子集合小于10个元素师改用直接插入排序;使用随即数发生器产生大数据集合,运行上述各排序算法,使用系统时钟测量各算法所需的实际时间,并进行比较。系统时钟包含在头文件“time.h”中。 二、概要设计 文件Sort.cpp中包括了简单选择排序SelectSort(),直接插入排序InsertSort(),冒泡排序BubbleSort(),两路合并排序Merge(),快速排序QuickSort()以及改进的快速排序GQuickSort()六个内排序算法函数。主主函数main的代码如下图所示: 三、详细设计 1.类和类的层次设计 在此次程序的设计中没有进行类的定义。程序的主要设计是使用各种内排序算法对随机 生成的数列进行排列,并进行性能的比较,除此之外还对快速排序进行了改进。下图为主函 数main的流程图:

——

main() 2.核心算法 1)简单选择排序: 简单选择排序的基本思想是:第1趟,在待排序记录r[1]~r[n]中选出最小的记录,将它与r[1]交换;第2趟,在待排序记录r[2]~r[n]中选出最小的记录,将它与r[2]交换;以此类推,第i趟在待排序记录r[i]~r[n]中选出最小的记录,将它与r[i]交换,使有序序列不断增长直到

目前最完整的数据结构1800题包括完整答案 第十章 排序

第10章排序 一、选择题 1.某内排序方法的稳定性是指( )。【南京理工大学 1997 一、10(2分)】A.该排序算法不允许有相同的关键字记录 B.该排序算法允许有相同的关键字记录 C.平均时间为0(n log n)的排序方法 D.以上都不对 2.下面给出的四种排序法中( )排序法是不稳定性排序法。【北京航空航天大学 1999 一、 10 (2分)】 A. 插入 B. 冒泡 C. 二路归并 D. 堆积 3.下列排序算法中,其中()是稳定的。【福州大学 1998 一、3 (2分)】 A. 堆排序,冒泡排序 B. 快速排序,堆排序 C. 直接选择排序,归并排序 D. 归并排序,冒泡排序 4.稳定的排序方法是()【北方交通大学 2000 二、3(2分)】 A.直接插入排序和快速排序 B.折半插入排序和起泡排序 C.简单选择排序和四路归并排序 D.树形选择排序和shell排序 5.下列排序方法中,哪一个是稳定的排序方法?()【北方交通大学 2001 一、8(2分)】 A.直接选择排序 B.二分法插入排序 C.希尔排序 D.快速排序6.若要求尽可能快地对序列进行稳定的排序,则应选(A.快速排序 B.归并排序 C.冒泡排序)。 【北京邮电大学 2001 一、5(2分)】 7.如果待排序序列中两个数据元素具有相同的值,在排序前后它们的相互位置发生颠倒,则称该排序算法是不稳定的。()就是不稳定的排序方法。【清华大学 1998 一、3 (2分)】 A.起泡排序 B.归并排序 C.Shell排序 D.直接插入排序 E.简单选择排序 8.若要求排序是稳定的,且关键字为实数,则在下列排序方法中应选()排序为宜。 A.直接插入 B.直接选择 C.堆 D.快速 E.基数【中科院计算所 2000 一、5(2分)】 9.若需在O(nlog2n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是()。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序【中国科技大学 1998 二、4(2分)】【中科院计算所 1998 二、4(2分)】 10.下面的排序算法中,不稳定的是()【北京工业大学 1999 一、2 (2分)】 A.起泡排序 B.折半插入排序 C.简单选择排序 D.希尔排序 E.基数排序 F.堆排序。 11.下列内部排序算法中:【北京工业大学 2000 一、1 (10分每问2分)】A.快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序F. 堆排序 (1)其比较次数与序列初态无关的算法是()(2)不稳定的排序算法是()(3)在初始序列已基本有序(除去n个元素中的某k个元素后即呈有序,k<

数据结构课程设计之综合排序代码及使用方法

题目1: 利用随机函数产生N个随机整数(20000以上),对这些数进行多种方法进行排序。 要求: 1)至少采用三种方法实现上述问题求解(提示,可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序)。并把排序后的结 果保存在不同的文件中。 2)统计每一种排序方法的性能(以上机运行程序所花费的时间为准进行对比),找出其中两种较快的方法。 代码如下: #include //标准输入输出头文件 #include //定义杂项函数及内存分配函数 #include //字符串处理 #include //定义关于时间的函数 #define N 20000 clock_t Start,Now;//时钟 void Wrong()//错误输出 { printf("\n*****按键错误!请重新输入*****\n"); getchar();//从标准输入获取字符并返回下一个字符 } void change(int a[])//十个一行输出 { int i; system("cls");//清除之前的操作 for(i=0;i

数据结构第10章 内部排序习题

第10章内部排序 一、单项选择题 1.若要尽可能地完成对实数数组得排序,且要求排序是稳定的,则应选______。 A.快速排序 B.堆排序 C.归并排序 D.基数排序 2.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列,用______方法最快。 A.冒泡排序 B.快速排序 C.希尔排序 D.堆排序 E.简单选择排序 3.将两个各有N个元素的有序表归并成一个有序表,其最小的比较次数是______。 A.N B.2N-1 C.2N D.N-1 4.就平均性能而言,目前最好的内排序方法是______排序法。 A.冒泡排序 B.希尔排序 C.插入排序 D.快速排序 5.若需要在O(nlog2n)的时间内完成对数据的排序,且要求排序是稳定的,则可选择的排序方法是______。 A.快速排序 B.堆排序 C.归并排序 D.直接插入排序 6.下面给出的四种排序方法中,排序过程中的比较次数与排序方法无关的是______。 A.选择排序法 B.插入排序法 C.快速排序法 D.堆排序法 7.数据序列{8,9,10,4,5,6,20,1,2}只能是下列排序算法中的()的两趟排序后的结果。

A.选择排序 B.冒泡排序 C.插入排序 D.堆排序 8.对一组数据{84,47,25,15,21}排序,第一趟的排序结果为15,47,25,84,21;第二趟排序的结果为15,21,25,84,47;第三趟排序的结果为15,21,25,47,84,则采用排序的方法是______。 A.选择排序 B.冒泡排序 C.快速排序 D.插入排序 9.下列排序算法中______排序在一趟结束后不一定能选出一个元素放在其最终位置上。 A.选择排序 B.冒泡排序 C.归并排序 D.堆排序 10.在下面的排序方法中,辅助空间为O(n)的是______。 A.希尔排序 B.堆排序 C.选择排序 D.归并排序 11.直接插入排序在最好的情况下的时间复杂度为______。 A.O(log2n) B.O(n) C. O(nlog2n) D.O(n2) 12.若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序,需进行______次比较。 A.3 B.10 C.15 D.25 13.对序列{15,9,7,8,20,-1,4}用希尔排序方法排序,经过一趟后序列变为{15,-1,4,8,20,9,7},则该次采用的增量是 ______。 A.1 B.4 C.3 D.2 14.对下列关键字序列用快速排序法进行排序,速度最快的情形是

相关文档
相关文档 最新文档