考研-专业课part排序定义及相关概念

DataPAGEPAGE2 isforbiddento排序的定义及相关概稳定、外部排为排序，反之称为外部排序。基本操排其关键字大小到已有序的部分记录中的适当直接排直接排序是一种最基本的排序方初始关键字 i=2： i=3： i=4： i=5： i=6： i=7： i=8： 监视直接排序的时间复杂度为O(n2)，空间复杂直接排序是稳定的排序方法，它适合于待折半排用直接排序。由于在排序的基本操作是在一个有序表中进行查找和，而这个“查找”操作可利用“折半查找”来实现，称之为折半排序。采用折半排序法，可减少关键字的比较次。每一个元素，需要比较的次数最大为折半判定未改变移动元素的时间耗费，所以折半排序的总排的记录放在同一个组中，在各组内进行直接排序；然后，取第二个增量d2d1序，直至所取的增量dt=1（dt<dt-1<…<d2<d1），即所有记录放在用一组中进行直接排序排序是不稳定的排序方法初始关键字： 第一趟结果： 第二趟结果： 第三趟结果： 交换排。以此类推，直至第（n-1）个记录和第n个记录的关键初第第第第第第始—二三四五六关趟趟趟趟趟趟键排排排排排排字序序序序序序快速排枢轴关键字

46 60 3 75 53 133 9675 53 133 96

60 33 75 53 133 96

333333

12 一次划分后：{ 33}

{ 96分别对前后两序{12}33{33 53{ 96

{60}75{96无序区的长度大致相等，其时间复杂度为O(nlogn)。而对快速排序平均时间而言，其时间复杂度也是O(nlogn)。通常，快速排序被认为是在所有同O(nlogn)序列中的记录进行排序，则栈的最多深度为O(logn)。另选择排i+1）个记录中选出关键字最小的记录，并与第i（第一趟排序第七趟排序最后排序

堆排若将此序列所有的向量看作是一棵完全二叉（a）逻辑结 （b）结（a）逻辑结 （b）结n/2的结点都序号

/

首先筛（a）初始序列对应的完全二叉 （b）筛选75准备准备筛准备筛（c）筛选33 （d）筛选60 （e）筛选46后，得到最终的重新调整堆的“筛选法（a）准备筛选46，46的左右子树均为 （b）移出46，准备上移 （c）上移96后，准备上移（d）上移75，准备上移 （e）上移60后，准备将46移入空位 （f）将46移入空位置后，筛选得到堆排序过12 33堆12 33 堆（a）初始大根

堆

（g）将前5个元素重新调整

（h）堆顶与堆尾元素交

（i）将前4个元素重新调整 （j）堆顶与堆尾元素交 （k）将前3个

（l）堆顶与堆尾元素交堆堆 （m）将前2个元素重新调整

（n）堆顶与堆尾元素交换成为最终的大根堆排序在情况下，其时间复杂度也O(nlogn)。相对于快速排序来说，这是堆排归并排2-路归得到n/2长度为2的有序子序列。接着再对长度为2的有序。如此重复，直至得到一个长度为n初始关键字第一趟归并第二趟归并第三趟归并是O(nlogn)。在实现归并时，需要与待排记链式基数排值进行进一步排序。以此类推，由低位到，每一趟是一趟基础上，根据关键字的某一位对所有记录进行排序，直至最，这样就完成了基数排序的 （e）第二趟收集之 （f）第三趟分配之第于需要链表作为结构，则相对于其它以顺序结构记录的排序方法而言，还增加了n个直接稳直接选不稳冒泡排稳排不稳快速排不稳堆排不稳2-路归并排稳基数排稳各种排几个结论接排序是最佳的排序方法。因此常将它与复杂度均为O(nlogn)，就平均时间而言，快但是快速排序在情况下的时间性能为O(n2)。堆排序和归并排序的时间复杂度仍为O(nlogn)，当n较大时，归并排序的时间性能优于法中，排序、快速排序、堆排序都是不稳外排序的两个阶，称为归并段或顺串；再对归并段进行归2、设有序列15，9，12）。给出下面结建立二叉排序树对d=3执行一次 排序建立堆顶最大的初始堆执行一次快速排序结果(1二叉排序树如下图（2）(2)一次s排序结果为15，17，23(3初始大顶堆如下图（1）(4快速排序第一趟结果为952595259 A、起泡B、直接C、归并D、简单选择4、对下面4个线性表分别进行快速排序，中 的排序速度最快。A1，2，3，4，5，6，7，8B4，1，3，2，6，5，7，8C4，3，2，1，6，5，7，8D、5、排序趟数与序列的原始状态有关的排序法 。A、排 B、选择排C、起泡排 D、快速排6、数据序列 A、快速排 B、冒泡排C、选择排 D、排 A、选择排序 B、冒泡排序C、归并排 D、堆排（无交换（无交换9、给出如下关键字序列7（1）84472515（2）15472584（3）15212584（4）15212547 A、选择 B、冒泡 C、快速 D、 A、堆排 B、快速排C、排 D、归并排Key:C、 A、75,65,30,15,25,45,20,10B、C、D、 A、要排序的数据量太B要排序的数据中含有多个相同C、要排序的数据个数为奇D、要排序的数据已基本有算法设一般来说，数据结构中稍微复杂一些的下面就考研中算法设计考题，并结合本 算法，这是最为的一类题目。用计算机解决实际问题大致过程如下原问题―分析―定义―设计算法―实―编译调1、分分析阶段需要把握的有数据结构是什么。有时会明确地告诉你需要用顺序实现或链式实现；有时并未给出要求，那么你要根据你的实际选择合适的结构。对于链式非常容易，否则就。实上，平时习时2定实际上是规格定义。定义数据结：顺序的数组大小、类型、维数等，式的结点结构；参数的类型及个数；输3、设计算另外，有几点提醒，希望引起注意算法应该以一个完整的函数形式。，速度放慢实例：结点的单向链表就地逆置[分析]空表时不必逆置，判定的条件h->next==NULL当有两个结点时，指针的图示P1P1342 ③：h->next->next=p;④：p-当有三个结点时 hq引入：指向结点；s引入：索引未结点实际上，就地逆置是在链表的头结点后不断未的节点LinkList*reverse(LinkList{ListNodep,q,ifh->next==NULLreturnelseifh->next->next==NULLreturnelse{p=h- q=p-s=q- p-q-p=h-/*p始终指向第1个元素结点s=s-}q-p=h-/*p始终指向第1个元素结点s=s-}/*q和s向右移动}until}return一些应当掌握的基本算法单链表上的和删除运算顺序表上的和删除运算一些应当掌握的基本算法二树排序树的、、删除运算！一、单项选择逻辑上通常可以将数据结构分为 第i个元素的前驱（1

在第i个元后一个新元素(1

n删除第i个元素(1

假设结点的单向循环链表的头指针为head，则该链表为空的判定条件是（）A.head==NULLB.head–>next==NULLD.head–>next==head已知栈的最大容量为4。若进栈序列为 A.B.C.D.1，4，6，5，2，3树的先根序列等同于与该树对应的二叉 先序序 B.中序序 A. B.C.2e D.n edabedabc下列排序方法中，稳定的排序方法为（A.排 B.堆排C.快速排 D.直接排 A.关键字的个 B.树的形 二、填空数据的结构是其逻辑结 Key:在内存中的映输入线性表的n个元素建立结点的单链 元素占2个单元,元素A[0][0]的地址为100,则元素A[4][5]的地址为 在快速排序、堆排序和归并排序中，时 Key:快速排H(key)=key%7,若用线性探测处理, 三、解答画出该二叉树的二叉链表表示;依次读入给定的整