当前位置：文档之家 › 数据结构 第9章 内部排序(作业)

数据结构 第9章 内部排序(作业)

  • 格式：ppt
  • 大小：972.00 KB
  • 文档页数：53

下载文档原格式

  / 53

合集下载

中国农业大学_821数据结构_《数据结构》习题(9)

中国农业大学_821数据结构_《数据结构》习题(9)

第9章内部排序一、问答题1. 什么是内部排序？什么是排序方法的稳定性？2. 对于本章介绍的内部排序方法，哪几种是稳定的？哪几种是不稳定的？对不稳定的排序方法试举例说明。

3. 对于给定的一组记录的关键字：23，13，17，21，30，60，58，28，30，90。

试分别写出用下列排序方法对其进行排序时，每一趟排序后的结果：(1)直接插入排序；(2)希尔排序；(3)冒泡排序；(4)直接选择排序；(5)快速排序(6)堆排序(7)归并排序。

4. 对长度为n的记录序列进行快速排序时，所需要的比较次数依赖于这n个元素的初始序列。

(1)n = 8时，在最好的情况下需要进行多少次比较？试说明理由。

(2)给出n = 8时的一个最好情况的初始排列实例。

5 试为下列各种情况选择合适的排序方法：(1)n = 30，要求在最坏的情况下，排序速度最快；(2)n = 30，要求排序速度既要快，又要排序稳定。

6. 判别以下序列是否为堆（所有的非叶子结点的关键字值k i均不大于其左右两个分支结点的关键字值k2和k2i+1。

），如果不是，则把它调整为堆。

(1)( 100, 86, 48, 73, 35, 39, 42, 57, 66, 21 )；(2)( 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 )；(3)( 103, 97, 56, 38, 66, 23, 42, 12, 30, 52, 06, 20 )；(4) ( 05, 56, 20, 03, 23, 40, 38, 29, 61, 05, 76, 28, 100 )。

7. 一组待排序记录的关键字是：986，321，123，432，500，654，018，765，987，210。

按照LSD方法写出基数排序的过程和结果。

8. 试证明：如果对于一个长度为n的任意文件进行排序，则至少需进行nlog2n次比较。

9. 试构造对5个整数元素进行排序，最多只用7次比较的算法思想。

数据结构第九章排序习题与答案

数据结构第九章排序习题与答案

习题九排序一、单项选择题1．下列内部排序算法中：A．快速排序 B.直接插入排序C. 二路归并排序D.简单选择排序E. 起泡排序F.堆排序（1）其比较次数与序列初态无关的算法是（）（2）不稳定的排序算法是（）（3）在初始序列已基本有序（除去n 个元素中的某 k 个元素后即呈有序， k<<n）的情况下，排序效率最高的算法是（）（4）排序的平均时间复杂度为O(n?logn)的算法是（）为 O(n?n) 的算法是（）2．比较次数与排序的初始状态无关的排序方法是( )。

A．直接插入排序B．起泡排序C．快速排序D．简单选择排序3．对一组数据（ 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.插入4．下列排序算法中 ( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。

A. 选择B.冒泡C.归并D.堆5．一组记录的关键码为（46，79，56， 38，40， 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。

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)6．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是()排序。

A．冒泡 B. 希尔C. 快速D. 堆7.就平均性能而言，目前最好的内排序方法是() 排序法。

A. 冒泡B.希尔插入C.交换D.快速8.下列排序算法中，占用辅助空间最多的是：()A. 归并排序B.快速排序C.希尔排序D.堆排序9.若用冒泡排序方法对序列 {10,14,26,29,41,52}从大到小排序，需进行（）次比较。

数据结构——第9章内排序(C#)

数据结构——第9章内排序(C#)
n 1
总的平均比较和移动次数约为
n 1 i i (n 1)( n 4) O( n2) ( 2 2 2) (i 2) 2 i 1 i 1 n 1
9.2.2 折半插入排序
查找采用折半查找方法，称为二分插入排序或折半插入排序。
public void BinInsertSort() //对R[0..n-1]按递增有序进行折半插入排序 { int i,j,low,high,mid;RecType tmp; for (i=1;i<length;i++) { tmp=R[i]; //将R[i]保存到tmp中 low=0;high=i-1; while (low<=high) //在R[low..high]中折半查找有序插入的位置 { mid=(low+high)/2; //取中间位置 if (tmp.key<R[mid].key) high=mid-1; //插入点在左半区 else low=mid+1; //插入点在右半区 } for (j=i-1;j>=high+1;j--) //元素后移 R[j+1]=R[j]; R[high+1]=tmp; //插入原来的R[i] } }
关键字最大位数用于基数排序radixnode用于基数排序的单链表头指针int关键字的位数用于基数排序publicint关键字的进制用于基数排序publicintersortclass构造函数用于顺序表等初始化rnewrectypemaxsize
第9章 内排序
9.1 排序的基本概念
所谓排序，是要整理表中的记录，使之按关键字递增 （或递减）有序排列。其确切定义如下： 输 入 ： n 个 记 录 ,R0,R1,…,Rn-1, 其 相 应 的 关 键 字 分 别 为 k0,k1,…,kn-1。 输 出 ： Ri,0,Ri,1,…,Ri,n-1, 使 得 ki,0≤ki,1≤…≤ki,n-1 ( 或

数据结构教程 第九章 排序

数据结构教程 第九章 排序
2 插入排序


9.2.3 希尔排序
3.算法



void ShellSort() { gap=n/2;//初次增量取序列元素个数n的一半为步长 while(gap>0) { for(i=gap+1;i<=n;i++) { j=i-gap; while(j>0) { if(r[j]>r[j+gap]) { x=r[j];r[j]=r[j+gap];r[j+gap]=x; j=j-gap; }//对子序列作直接插入排序 else j=0; } } gap=gap/2;}//每次减半，直至步长为1 上一页 }
上一页
下一页
9.3 快速排序法


9.3.2 快速排序
3【例9-5】对数据序列:70, 75, 69, 32, 88, 18, 16, 58进行快速排序如图9-3所示。 4.算法


void QuickSort(int low, int high)//递归形式的快速排序 { int pivotpos; if(low<high) { pivotpos=Partition(low,high); QuickSort(low,pivotpos-1);//对低子表递归排序 QucikSort(pivotpos+1,high);//对高子表递归排序 } }
9.2 插入排序


9.2.2 二分插入排序
3.算法



void BinsSort() { for(i=2;i<=n;i++) { r[0]=r[i];low=1;high=i-1;//将r[i]暂存到r[0] while(low<=high) //在r[low..high]中折半查找有序插入的位置 { m=(low+high)/2;//折半 if(r[0].key<r[m].key) high=m-1;//插入点在低半区 else low=m+1;//插入点在高半区 } for(j=i-1;j>high+1;--j) r[j+1]=r[j];//记录后移 r[high+1]r[0];//插入 } 上一页 下一页

数据结构-9-内部排序

数据结构-9-内部排序

49 2
25* 3 25*
16
4
08 5
i=1
gap = 3
0
21
49
16
08
21
25
49
25*
16
08
21
25
49
25*
16
08
21
16
1
08 2
25* 3
25 4
49 5
i=2
gap = 2
0
21
16
08
25*
25
49
21
16
08
25*
25
49
08
16
21
25*
25
49
08
16
1
21 2
25* 3
排序之前，对象r[i]排在r[j]前面。如果在排序
之后，对象r[i]仍在对象r[j]的前面，则称这个 排序方法是稳定的，否则称这个排序方法是不 稳定的。


内排序与外排序: 内排序是指在排序期间数据 对象全部存放在内存的排序；外排序是指在排 序期间全部对象个数太多，不能同时存放在内 存，必须根据排序过程的要求，不断在内、外 存之间移动的排序。 排序的时间开销: 排序的时间开销是衡量算法 好坏的最重要的标志。排序的时间开销可用算 法执行中的数据比较次数与数据移动次数来衡 量。各节给出算法运行时间代价的大略估算一 般都按平均情况进行估算。对于那些受对象关 键字序列初始排列及对象个数影响较大的，需 要按最好情况和最坏情况进行估算。

希尔排序方法又称为“缩小增量”排序。
该方法的基本思想是：先将整个待排对象序列 按照一定间隔分割成为若干子序列，分别进行 直接插入排序，然后缩小间隔，对整个对象序 列重复以上的划分子序列和分别排序工作，直 到最后间隔为1，此时整个对象序列已 “基本 有序”，进行最后一次直接插入排序。

数据结构第9章 排序

数据结构第9章 排序

数据结构第9章排序数据结构第9章排序第9章排名本章主要内容：1、插入类排序算法2、交换类排序算法3、选择类排序算法4、归并类排序算法5、基数类排序算法本章重点难点1、希尔排序2、快速排序3、堆排序4.合并排序9.1基本概念1.关键字可以标识数据元素的数据项。

如果一个数据项可以唯一地标识一个数据元素，那么它被称为主关键字；否则，它被称为次要关键字。

2．排序是把一组无序地数据元素按照关键字值递增（或递减）地重新排列。

如果排序依据的是主关键字，排序的结果将是唯一的。

3.排序算法的稳定性如果要排序的记录序列中多个数据元素的关键字值相同，且排序后这些数据元素的相对顺序保持不变，则称排序算法稳定，否则称为不稳定。

4.内部排序与外部排序根据在排序过程中待排序的所有数据元素是否全部被放置在内存中，可将排序方法分为内部排序和外部排序两大类。

内部排序是指在排序的整个过程中，待排序的所有数据元素全部被放置在内存中；外部排序是指由于待排序的数据元素个数太多，不能同时放置在内存，而需要将一部分数据元素放在内存中，另一部分放在外围设备上。

整个排序过程需要在内存和外存之间进行多次数据交换才能得到排序结果。

本章仅讨论常用的内部排序方法。

5.排序的基本方法内部排序主要有5种方法：插入、交换、选择、归并和基数。

6.排序算法的效率评估排序算法的效率主要有两点：第一，在一定数据量的情况下，算法执行所消耗的平均时间。

对于排序操作，时间主要用于关键字之间的比较和数据元素的移动。

因此，我们可以认为一个有效的排序算法应该是尽可能少的比较和数据元素移动；第二个是执行算法所需的辅助存储空间。

辅助存储空间是指在一定数据量的情况下，除了要排序的数据元素所占用的存储空间外，执行算法所需的存储空间。

理想的空间效率是，算法执行期间所需的辅助空间与要排序的数据量无关。

7.待排序记录序列的存储结构待排序记录序列可以用顺序存储结构和和链式存储结构表示。

在本章的讨论中（除基数排序外），我们将待排序的记录序列用顺序存储结构表示，即用一维数组实现。

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

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

第九章查找一、填空题1.在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找(线性查找) 。

2.线性有序表(a i，a2，a3,…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索_8 次。

设有100个结点，用二分法查找时，最大比较次数是_7_ ____________ 。

3•假设在有序线性表a[1..2O]上进行折半查找，则比较一次查找成功的结点数为1;比较两次查找成功的结点数为_2 ___________ ;比较四次查找成功的结点数为8 ,其下标从小到大依次是1,3,6,8,11,13,16,19 _ ，平均查找长度为 3.7 。

解：显然，平均查找长度二0( log 2n) <5次(25)。

但具体是多少次，则不应当按照公式ASL =U|°g2(n⑴来计算(即(21 X log 221) /20 = 4.6次并不正确！)。

因为这是在假设n = 2m-1 n 的情况下推导出来的公式。

应当用穷举法罗列：全部元素的查找次数为=(1 + 2X 2+ 4X 3+ 8X 4+ 5X 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<m)个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。

如果这n个关键码的散列地址都相同，贝U探测的总次数是n(n-1)/2= ( 1 土2+…+ n-1 )。

(而任一元素查找次数 < n-1)&设一哈希表表长M为100，用除留余数法构造哈希函数，即H( K) =K MOIP ( P<=M ,为使函数具有较好性能，P应选(97 )9、在各种查找方法中，平均查找长度与结点个数无关的是哈_______10、对线性表进行二分查找时，要求线性表必须以顺序方式存储，且结点按关键字有序排列。

数据结构 第9章(内排序)

数据结构 第9章(内排序)

3. 将R[j+1]=R[0] 实现整个序列的排序。
North China Electric Power University
排序算法如下：
void insort(List r, int n) {//r为给定的表，其记录为r[i]，i=0，1，…，n，x为暂存单元。 for (i=2; i<=n; i++) { r[0]=r[i]; //r[0]作为标志位 j=i-1; while (r[0].key<r[j].key) { r[j+1]=r[j]; j--; } //j从i-1至0，r[j].key与r[i].key进行比较 r[j+1]=r[0]; } }//insort
North China Electric Power University
例如：
第二趟希尔排序，设增量d = 3
第三趟希尔排序，设增量d = 1
North China Electric Power University
希尔排序的算法描述如下:
void ShellInsert (List r,int d) //本算法对直接插入算法作了以下修改： // 1. 前后记录位臵的增量是d，而不是1； // 2. r[0]只是暂存单元，不是哨兵。当j<=0时，插入位臵已找到。 for (i=2;i<= n ; i++) { { r[0]=r[i]; for(i=d+1;i<=n;i++) j=i-1; if ( r[i] < r[i-d]) //需将r[i]插入有序增量子表 while ( r[0].key<r[j].key) { r[0] = r[i]; //暂存在R[0] { r[j+1]=r[j]; j=i-d ; j=j-1; while ((j>0) and (r[0] < r[j])) } { r[j+d] = r[j]; //记录后移，查找插入位臵 r[j+1]=r[0]; j=j-d; } } r[j+d] = r[0];//插入 } }

数据结构 第9章 内部排序(作业)

数据结构 第9章 内部排序(作业)
void BInsertSort(SqList &L) { // 对顺序表L作折半插入排序。算法10.2 for(i=2;i<=L.length;++i) { L.r[0]=L.r[i]; // 将L.r[i]暂存到L.r[0] low=1; high=i-1; while(low<=high) { // 在r[low..high]中折半查找有序插入的位置 m=(low+high)/2; // 折半 if LT(L.r[0].key,L.r[m].key) high=m-1; //插入点在低半区 else low=m+1; // 插入点在高半区 } for(j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j]; // 记录后移 L.r[high+1]=L.r[0]; // 插入 } }
第9章 内部排序
为了讨论方便，假设待排记录的关键字均为整数，均从 数组中下标为1的位置开始存储，下标为0的位置存储监视哨， 或空闲不用。 typedef int KeyType; typedef struct { KeyType key; OtherType other-data; } RecordType;
类: 一类是整个排序过程完全在内存中进行，称为内部排序； 另一类是由于待排序记录数据量太大，内存无法容纳全部数 据， 排序需要借助外部存储设备才能完成，称为外部排序。
第9章 内部排序
假设Ki=Kj(1≤i≤n，1≤j≤n，i≠j)， 若在排序前的序列中Ri
领先于Rj(即i<j)，经过排序后得到的序列中Ri仍领先于Rj， 则 称所用的排序方法是稳定的；反之，当相同关键字的领先关系 在排序过程中发生变化，则称所用的排序方法是不稳定的。 无论是稳定的还是不稳定的排序方法，均能排好序。在应 用排序的某些场合，如选举和比赛等，对排序的稳定性是有特 殊要求的。

数据结构(内部排序)习题与答案

数据结构(内部排序)习题与答案

一、单选题1、对关键字序列（21,19,37,5,2），经直接插入排序法由小到大排序，第一趟后所得结果为（）。

A.(19，21，5，2，37)B.(19，21，37，5，2)C.(19，21，2，5，37)D.(19，21，5，37，2)正确答案：B2、对关键字序列（21,19,37,5,2），经冒泡排序法由小到大排序，第一趟后所得结果为（）。

A.(19，21，37，5，2)B.(19，21，2，5，37)C.(19，21，5，37，2)D.(19，21，5，2，37)正确答案：D3、对关键字序列（149,138,165,197,176,113,127），采用基数排序的第一趟之后所得结果为（）。

A.(113，165，176，197，127，138，149)B.(113，165，176，127，197，138，149)C.(113，127，138，149，165，176，197)D.(149，138，165，197，176，113，127)正确答案：A4、下列各项键值（）序列不是堆的。

A.(5，23，68，16，94)B.(5，23，16，94，68)C.(5，16，23，68，94)D.(5，23，16，68，94)正确答案：A5、假设一组待排序的关键字序列为（24,62,36,19），要求从小到大进行排序，（）是归并排序的过程。

A.(24，62，36，19)(24，36，62，19)(19，24，36，62)B.(24，62，19，36)(19，24，36，62)C.(62，24，36，19)(19，24，36，62)D.(24，19，36，62)(24，19，36，62)(19，24，36，62)正确答案：B6、在第一趟排序之后，不能确保将数据表中某一个元素放在其最终位置上的排序算法是（）。

A.归并排序B.快速排序C.冒泡排序D.选择排序正确答案：A7、对于下列排序，（）的时间效率与关键字初始序列有直接关系。

《数据结构(C／C++描述)》-第9章 内排序

《数据结构(C／C++描述)》-第9章 内排序
中国水利水电出版社
15
16 物料管理
Data Structures: Chapter 9
9.2
插入排序
0 1 10 50 2 20 40 3 30 30 4 40 20 5 50 10
直接插入排序算法分析：
分析: 移动、比较次数可作为衡量时间复杂性的标准 O(n2)
正序时：比较次数
∑
n-1
1 = n-1 j=1
定的。
中国水利水电出版社
5
6 物料管理
Data Structures: Chapter 9
插入排序的数据类型定义如下：
typedef struct elemtype //待排序的数据记录类型
{ keytype key; //数据记录的关键字
anytype otherelem; //数据记录中的其他成份 }datatype;
3. 希尔排序－－缩小增量排序
基本思想： 对待排记录序列先作“宏观”调整，再作 “微观”调整。 所谓“宏观”调整，指的是 “跳跃式”的 插入排序。具体做法为：
中国水利水电出版社
21
22 物料管理
Data Structures: Chapter 9
将记录序列分成若干子序列，分别对每个子序列进 行插入排序。 例如：将 n 个记录分成 d 个子序列： { R[1]，R[1+d]，R[1+2d]，…，R[1+kd] } { R[2]，R[2+d]，R[2+2d]，…，R[2+kd] } … { R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d] }
中国水利水电出版社
7
9.2
8 物料管理
Data Structures: Chapter 9

数据结构习题及答案（3）

数据结构习题及答案（3）

数据结构习题及答案（3）第九章排序⼀、选择题1.在所有排序⽅法中，关键字⽐较的次数与记录得初始排列次序⽆关的是（）（A）希尔排序（B）起泡排序（C）插⼊排序（D）选择排序参考答案：D2.设有1000个⽆序的元素,希望⽤最快的速度挑选出其中前10个最⼤的元素,最好（）排序法。

（A）起泡排序（B）快速排序（C）堆排序（D）基数排序参考答案：C3.在待排序的元素序列基本有序的前提下,效率最⾼的排序⽅法是（）（A）插⼊排序（B）选择排序（C）快速排序（D）归并排序参考答案：A4.⼀组记录的排序码为(46,79,56,38,40,84),则利⽤堆排序的⽅法建⽴的初始推为（）。

（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参考答案：B5.⼀组记录的关键码为(46,79,56,38,40,84),则利⽤快速排序的⽅法,以第⼀个记录为基准得到的⼀次划分结果为（）。

（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参考答案：C6.⼀组记录的排序码为(25,48,16,35,79,82,23,40,36,72),其中含有5个长度为2的有序表,按归并排序的⽅法对该序列进⾏⼀趟归并后的结果为（）。

（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参考答案：A7.排序⽅法中,从未排序序列中依次取出元素与⼰排序序列(初始时为空)中的元素进⾏⽐较,将其放⼊⼰排序序列的正确位置上的⽅法,称为（）（A）希尔排序（B）起泡排序（C）插⼊排序（D）选择排序参考答案：C8.排序⽅法中,从未排序序列中挑选元素并将其依次放⼊⼰排序序列(初始为空)的⼀端的⽅法,称为（）（A）希尔排序（B）归并排序（C）插⼊排序（D）选择排序参考答案：D9.⽤某种排序⽅法对线性表(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,845则所采⽤的排序⽅法是（）。

《数据结构》第九章习题 参考答案

《数据结构》第九章习题 参考答案

《数据结构》第九章习题参考答案一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）1、快速排序是一种稳定的排序方法。

（×）2、在任何情况下，归并排序都比简单插入排序快。

（×）3、当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。

（√）4、内排序要求数据一定要以顺序方式存储。

（×）5、直接选择排序算法在最好情况下的时间复杂度为O（n）。

( ×)6、快速排序总比简单排序快。

( ×)二、单项选择题1．在已知待排序文件已基本有序的前提下，效率最高的排序方法是（A）。

A．直接插入排序B．直接选择排序C．快速排序D．归并排序2．下列排序方法中，哪一个是稳定的排序方法？（B）A．直接选择排序B．折半插入排序C．希尔排序D．快速排序3、比较次数与排序的初始状态无关的排序方法是( B)。

A．直接插入排序B．起泡排序（时间复杂度O（n2））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)。

A. 选择B. 冒泡C. 快速D. 插入5、快速排序方法在（D）情况下最不利于发挥其长处。

A. 要排序的数据量太大B. 要排序的数据中含有多个相同值C. 要排序的数据个数为奇数D. 要排序的数据已基本有序6、用某种排序方法对线性表{25，84，21，47，15，27，68，35，20}进行排序，各趟排序结束时的结果为：（基准）20，21，15，25，84，27，68，35，47（25）15，20，21，25，47，27，68，35，84（左20右47）15，20，21，25，35，27，47，68，84（左35右68）15，20，21，25，27，35，47，68，84 ；则采用的排序方法为（C）。

《数据结构》习题汇编09-第九章-排序-试题

《数据结构》习题汇编09-第九章-排序-试题

《数据结构》习题汇编09-第九章-排序-试题数据结构课程（本科）第九章试题一、单项选择题1.若待排序对象序列在排序前已按其排序码递增顺序排列，则采用（）方法比较次数最少。

A. 直接插入排序B. 快速排序C. 归并排序D. 直接选择排序2.如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（）方法最快。

A. 起泡排序B. 快速排序C. 直接选择排序D. 堆排序3.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。

这样的排序方法是（）。

A. 直接选择排序B. 直接插入排序C. 快速排序D. 起泡排序4.对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较？A. 8B. 10C. 15D. 255.如果输入序列是已经排好顺序的，则下列算法中（）算法最快结束？A. 起泡排序B. 直接插入排序C. 直接选择排序D. 快速排序6.如果输入序列是已经排好顺序的，则下列算法中（）算法最慢结束？A. 起泡排序B. 直接插入排序C. 直接选择排序D. 快速排序7.下列排序算法中（）算法是不稳定的。

A. 起泡排序B. 直接插入排序C. 基数排序D. 快速排序8.假设某文件经过内部排序得到100个初始归并段，那么如果要求利用多路平衡归并在3 趟内完成排序，则应取的归并路数至少是（）。

A. 3B. 4C. 5D. 69.采用任何基于排序码比较的算法，对5个互异的整数进行排序，至少需要（）次比较。

A. 5B. 6C. 7D. 810.下列算法中（）算法不具有这样的特性：对某些输入序列，可能不需要移动数据对象即可完成排序。

A. 起泡排序B. 希尔排序C. 快速排序D. 直接选择排序11.使用递归的归并排序算法时，为了保证排序过程的时间复杂度不超过O(nlog2n)，必须做到（）。

A. 每次序列的划分应该在线性时间内完成B. 每次归并的两个子序列长度接近C. 每次归并在线性时间内完成D. 以上全是12.在基于排序码比较的排序算法中，（）算法的最坏情况下的时间复杂度不高于O(nlog2n)。

数据结构-9内部排序

数据结构-9内部排序

7
16
28
36
41
j=4
k=3
L[k]与L[j]比较
22:37
9.2.2 选择排序法
一趟排序算法：
void SelectPass(SqList &L,int i) { RcdType W; int j,k; k=i; // j指示无序序列中第一个记录的位置 for(j=i+1;j<=L.length;j++) if(L.r[k].key>L.r[j].key) k=j; //只记录位置 if(i!=k) // 交换R[j]和R[i]; { w=L.r[i]; L.r[i]=L.r[k]; L.r[k]= w; } // L.r[i]←→ L.r[j]; } // SelectPass

起泡排序 选择排序 插入排序 快速排序 归并排序 堆排序 基数排序
2. 外部排序（External Sort）：在排序进行的过程 中需要对外存进行访问的排序过程。
9.1.4 内排序的特点
大多数排序算法都有两个基本的操作：
（1）比较两个关键字的大小 （2）将记录从一个位置移动到另一个位置
13
27
38
492
491
65
76
22:37
9.2.2 选择排序法 时间复杂度：O(n2) 空间复杂度：O(1) 优点：
算法简单；辅助空间少。
缺点：
效率低；不稳定性排序（可以改进）。
22:37
9.2.3 插入排序
基本思想：依次将记录序列中的每一个记录插入到有序段中，使有 序段的长度不断地扩大。其具体的排序过程可以描述如下：首先将 待排序记录序列中的第一个记录作为一个有序段，将记录序列中的 第二个记录插入到上述有序段中，形成由两个记录组成的有序段， 再将记录序列中的第三个记录插入到这个有序段中，形成由三个记 录组成的有序段，…依此类推，每一趟都是将一个记录插入到前面 的有序段中。 假设当前欲处理第i个记录，则将R[i]这个记录插入到有序R[1..i-1] 段中，从而使有序序列长度增1，直到所有记录都插入到有序段中。 一共需要经过n-1趟就可以将初始序列的n个记录重新排列成按关键 字值大小排列的有序序列。 一趟排序开始 R[i]

数据结构与算法(C++语言版)》第9章 内部排序

数据结构与算法(C++语言版)》第9章 内部排序

插入排序
插入排序
• 以上述静态链表类型作为待排记录序列的存储结构，并设 数组中下标为0的分量为表头结点，并令表头结点记录的关 键码取最大整数MAXNUM。 • 表插入的排序过程是，首先将静态链表中数组下标为1的分 量（结点）和表头结点构成一个循环链表，然后依次将下 标为2～n的分量（结点）按记录关键码非递减有序插入到 循环链表中，算法如以下程序所示。
插入排序
例9-3
• 以关键码序列{52, 43, 68, 89, 77, 16, 24, 52*, 80, 31}为例，表 插入排序的过程如下列图所示。
插入排序
• 从上面的过程可看出，表插入排序与直接插入排序的不同 之处在于，表插入排序以修改2n次指针值来代替记录的移 动，但和关键码的比较次数相同，因此表插入排序的时间 复杂度仍为O(n2)。
i=n
交换排序
• 快速排序 • 快速排序（quick sort）是Hoare于1962年提出的一种分区交 换排序。它采用了一种分而治之的策略，是对冒泡排序的 一种改进。其算法思想是，首先将待排序记录序列中的所 有记录作为当前待排序区域，选取第一个记录的关键码值 为基准（轴值），从待排序记录序列左、右两端开始向中 间靠拢，交替与轴值进行比较，若左侧记录的关键码值大 于轴值，则将该记录移到基准记录的右侧，若右侧记录的 关键码值小于轴值，则将该记录移到基准记录的左侧，最 后让基准记录到达它的最终位置，此时，基准记录将待排 序记录分成了左右两个区域，位于基准记录左侧的记录都 小于或等于轴值，位于基准记录右侧的所有记录的关键码 都大于或等于轴值，这就是一趟快速排序。
例9-5
• 如图所示为冒泡排序的一个示例。冒泡排序的效率分析： ① 若初始序列为“正序”序列，则只需进行一趟排序，在 排序过程中进行n−1次关键码的比较，且不移动记录；② 若 初始序列为“逆序”序列，则需进行n−1趟排序，需进行 2 ∑ (i − 1) = n(n − 1) / 2次比较。因此，总的时间复杂度为O(n2)。

数据结构第九章 排序题库(40道)

数据结构第九章 排序题库(40道)

数据结构第九章排序1、内排序方法中,从未排序序列中依次取出元素与已排序序列中的元素进行比较,将其放入已排序序列的正确位置上的方法,称为( )。

——[单选题]A 希尔排序B 冒泡排序C 直接插入排序D 简单选择排序正确答案：C2、对有n个记录的表进行直接插入排序,在最坏情况下需进行( )次关键字比较。

——[单选题]A n-1B n+1C n/2D n(n-1)/2正确答案：D3、在下列算法中,( )算法可能出现下列情况:在最后一趟开始之前,所有的元素都不在其最终的位置上。

——[单选题]A 堆排序B 冒泡排序C 直接插入排序D 快速排序正确答案：C4、对数据序列{15,9,7,8,20,-1,4}进行排序,进行一趟后数据的排序变为{9,15,7,8,20,-1,4},则采用的是( )算法。

——[单选题]A 简单选择排序B 冒泡排序C 直接插入排序D 堆排序正确答案：C5、数据序列{5,4,15,10,3,1,9,6,2}是某排序方法第一趟后的结果,该排序算法可能是( )。

——[单选题]A 冒泡排序B 二路归并排序C 堆排序D 简单选择排序正确答案：B6、从未排序序列中挑选元素,并将其依次插入已排序序列的一端的方法,称为( )。

——[单选题]A 希尔排序B 归并排序C 直接插入排序D 简单选择排序正确答案：D7、在以下排序方法中,关键字比较的次数与元素的初始排列次序无关的是( )。

——[单选题]A 希尔排序B 冒泡排序C 插入排序D 简单选择排序正确答案：D8、对n个不同的关键字进行递增冒泡排序,在下列哪种情况下比较的次数最多( )。

——[单选题]A 元素无序B 元素递增有序C 元素递减有序D 都一样正确答案：C9、对数据序列(8,9,10,4,5,6,20,1,2)进行递增排序,采用每趟冒出一个最小元素的冒泡排序算法,需要进行的趟数至少是( )。

——[单选题]A 3B 4C 5D 8正确答案：C10、为实现快速排序法,待排序序列最好采用的存储方式是( )。

数据结构习题汇编09 第九章 排序 试题

数据结构习题汇编09 第九章 排序 试题

数据结构课程（本科）第九章试题一、单项选择题1.若待排序对象序列在排序前已按其排序码递增顺序排列，则采用（）方法比较次数最少。

A. 直接插入排序B. 快速排序C. 归并排序D. 直接选择排序2.如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（）方法最快。

A. 起泡排序B. 快速排序C. 直接选择排序D. 堆排序3.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。

这样的排序方法是（）。

A. 直接选择排序B. 直接插入排序C. 快速排序D. 起泡排序4.对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较？A. 8B. 10C. 15D. 255.如果输入序列是已经排好顺序的，则下列算法中（）算法最快结束？A. 起泡排序B. 直接插入排序C. 直接选择排序D. 快速排序6.如果输入序列是已经排好顺序的，则下列算法中（）算法最慢结束？A. 起泡排序B. 直接插入排序C. 直接选择排序D. 快速排序7.下列排序算法中（）算法是不稳定的。

A. 起泡排序B. 直接插入排序C. 基数排序D. 快速排序8.假设某文件经过内部排序得到100个初始归并段，那么如果要求利用多路平衡归并在3 趟内完成排序，则应取的归并路数至少是（）。

A. 3B. 4C. 5D. 69.采用任何基于排序码比较的算法，对5个互异的整数进行排序，至少需要（）次比较。

A. 5B. 6C. 7D. 810.下列算法中（）算法不具有这样的特性：对某些输入序列，可能不需要移动数据对象即可完成排序。

A. 起泡排序B. 希尔排序C. 快速排序D. 直接选择排序11.使用递归的归并排序算法时，为了保证排序过程的时间复杂度不超过O(nlog2n)，必须做到（）。

A. 每次序列的划分应该在线性时间内完成B. 每次归并的两个子序列长度接近C. 每次归并在线性时间内完成D. 以上全是12.在基于排序码比较的排序算法中，（）算法的最坏情况下的时间复杂度不高于O(nlog2n)。

数据结构第9章内部排序

数据结构第9章内部排序

算法步骤： （1）将整个待排序的记录序列划分成有序 区和无序区，初始时有序区为待排序记 录序列的第一个记录，无序区包括所有 剩余待排序的记录； （2）将无序区的第一个记录插入到有序 区的合适位置中，从而使无序区减少一 个记录，有序区增加一个记录； （3）重复执行（2），直到无序区中没有 记录为止。
希尔排序算法： void shell_sort(Sqlist *L, int dk[], int t)
/*按增量序列dk[0 … t-1],对顺序表L进行希尔排序*/
{ int m ; for (m=0; m<=t; m++) shell_pass(L, dk[m]) ; }
希尔排序可提高排序速度： (1) 分组后n值减小，n² 更小，而T(n)=O(n² ), 所以T(n)从总体上看减小了； (2) 关键字较小的记录可以以增量为单位跳 跃式前移，当进行最后一趟增量为1的插 入排序时，序列已基本有序。 增量序列取法： (1) 无除1以外的公因子； (2) 增量递减，最后一个增量值必须为1。
算法分析：
⑴ 最好情况：待排序记录按关键字从小到大排 列，算法中的内循环无须执行，每一趟排序时， 关键字比较1次，记录不需移动。所以整个排 序的关键字比较次数为n-1，记录移动次数为 0。 ⑵ 最坏情况：待排序记录按关键字从大到小排 列，每一趟排序时，算法中的内循环体执行i-1 次，关键字比较次数i次，记录移动次数i+1。 一般地，认为待排序的记录在各个位置的插入 概率相同，则取以上两种情况的平均值，作为 排序的关键字比较次数和记录移动次数，约为 n2/4，由此，直接插入排序的平均时间复杂度 为O(n2)。
插入排序
插入排序是一类借助“插入”操作进行 排序的方法，其主要思想是：每次将一 个待排序的记录按其关键字的大小插入 到一个已经排好序的有序序列中，直到 全部记录排好序。

数据结构数据内部排序

数据结构数据内部排序

数据结构09内部排序9.1 排序地基本概念9.2 插入排序9.3 交换排序9.4 选择排序9.5 归并排序9.6 基数排序车次出发站/到达站出发时间到达时间…G7031南京/上海5:517:42…G7033南京南/上海6:108:11…G7121南京南/上海南6:178:16…G7035南京南/上海6:318:31…G7037南京南/上海6:508:51…G7039南京南/上海虹桥6:599:03…G7001南京/上海7:008:39…G7197南京南/上海7:158:50………………按出发时间排序排序：设有记录序列{R1, R2,…, Rn},其相应地关键字序列为{K1,K2,…, Kn},若存在某种确定地关系 Kx≤Ky≤…≤Kz,其中 1≤x, y, z≤n 且x,y,z 各不相同,则将记录序列{R1, R2,…, Rn}排成按关键字有序地序列{Rx, Ry,…, Rz}地操作称为排序。

排序依据地关系是任意地,通常使用小于（递增）,大于（递减）等关系。

稳定与不稳定：若有一个待排序列为{R1, R2, …, Ri, …, Rn} (i ≠ 2),其对应地关键字序列为{K1, K2, …, Ki, …, Kn},若R2与Ri地关键字K2=Ki,如果排序前后,它们地相对位置保持不变,则这种排序方法是稳定地,否则是不稳定地。

正序与逆序：若待排序序列中地记录已按关键字排好序,则称此记录序列为正序;若待排序序列中记录地排列顺序与排序后地排列顺序正好相反,称此记录序列为逆序。

一趟：在排序过程中,将待排序地记录序列扫描一遍。

单关键字排序：根据一个关键字进行地排序。

多关键字排序：根据多个关键字进行地排序,主要针对关键字有重复地情况。

内部排序：在排序地整个过程中,待排序地所有记录全部被放置在内存中地排序方法,也简称为内排序。

外部排序：由于待排序地记录个数太多,不能同时放置在内存,而需求将一部分记录放置在内存中,另一部分记录放置在外存中,整个排序过程需求在内外存之间多次交换数据才能得到排序结果地排序方法,也简称为外排序。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第9章 内部排序
直接插入排序算法简便，比较适用于待排序记录数目较少
且基本有序的情况。当待排记录数目较大时，直接插入排序的
性能就不好， 为此我们可以对直接插入排序做进一步的改进。 在直接插入排序法的基础上，从减少“比较关键字”和“移动 记录”两种操作的次数着手来进行改进。
第9章 内部排序
9.2.2 折半插入排序
列中，将所有间隔为d2的记录分成一组，进行组内直接插入排序，
第9章 内部排序
49 38 65 97 76 13 27 49 55 04
d1 5
13 27 49 55 04 49 38 65 97 76
d2 3
d3 2
13 04 49 38 27 49 55 65 97 76 13 04 27 38 49 49 55 65 97 76 04 13 27 38 49 49 55 65 76 97
序，要求找出当前下标序列1，2，…， n的一种排列p1，p2， …，
pn，使得相应关键字满足如下的非递减（或非递增）关系，即：
Kp1≤Kp2≤…≤Kpn，这样就得到一个按关键字有序的记录序列{Rp1， Rp2，…，Rpn}。
第9章 内部排序
2. 内部排序与外部排序
根据排序时数据所占用存储器的不同，可将排序分为两
第9章 内部排序
49 38 65 97 76 13 27 49
初 始 关 键 字
第9章 内部排序
0
1
2
3
4
5
6
7
8
i7
Max 49 38 65 97 76 13 27 49
6
0
3
1
1 5 0 4 7 2
2
3
4
5
6
7
8
i 8
Max 49 38 65 97 76 13 27 49
6
8
1 5 0 4 7 2 3
第9章 内部排序
9.2.5 希尔排序(shell)
又称“缩小增量排序”。希尔排序的基本思想：先将待排序 记录序列分割成为若干个子序列，分别进行直接插入排序。待
第9章 内部排序
9.2.3 2-路插入排序 P267
引入：改进的折半插入排序，为减少移动记录的次数， 为此需n个记录的辅助空间。 做法：另设一个和L.r同类型的数组d，首先将L.r[1]赋 给d[1]，并将d[1]看成是在排好序的序列中处于中间位 置的记录，然后从L.r中第2个记录起依次插入到d[1]之
final
第9章 内部排序
9.2.4 表插入排序
采用链表存储结构进行插入排序。表插入排序的基本思 想是：先在待插入记录之前的有序子链表中查找应插入位置， 然后将待插入记录插入链表。由于链表的插入操作只修改指 针域，不移动记录，所以表插入排序可提高排序效率。在算 法的具体实现上，我们可以采用静态链表作为存储结构。
整个序列中的记录基本有序时，再对全部记录进行一次直接插入
排序。 具体实现时，首先选定两个记录间的距离d1，在整个待排序 记录序列中将所有间隔为d1的记录分成一组，进行组内直接插入 排序，然后再取两个记录间的距离d2<d1，在整个待排序记录序 直至选定两个记录间的距离dt=1为止，此时只有一个子序列，即 整个待排序记录序列。
已排好序的单元素子集合，然后将第2个记录插入到单元素子
集合中。i从2循环到n，即可实现完整的直接插入排序。
第9章 内部排序
例9.1 设有一组关键字序列｛55，22，44，11，33｝，这
里n=5，即有5个记录。如图9.1所示。请将其按由小到大的顺序 排序。
第一趟 第二趟 第三趟 第四趟 结 果 [55] [22 [22 [11 [11 22 55] 44 22 22 44 44 55] 44 33 11 11 11 55] 44 33 33 33 33 55]
前或之后的有序序列中。
第9章 内部排序
1
2
i 2 i 1
i
i 1
L.r
1
2
i 2 i 1
i
i 1
辅助空间d：
将d看成是一个循环向量，并设两个指针first和final指示 有序序列中第一个记录和最后 65 97 76 13 27 49
void BInsertSort(SqList &L) { // 对顺序表L作折半插入排序。算法10.2 for(i=2;i<=L.length;++i) { L.r[0]=L.r[i]; // 将L.r[i]暂存到L.r[0] low=1; high=i-1; while(low<=high) { // 在r[low..high]中折半查找有序插入的位置 m=(low+high)/2; // 折半 if LT(L.r[0].key,L.r[m].key) high=m-1; //插入点在低半区 else low=m+1; // 插入点在高半区 } for(j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j]; // 记录后移 L.r[high+1]=L.r[0]; // 插入 } }
第9章 内部排序
0
1
2
3
4
5
6
7
8
初始状态：
Max 49 38 65 97 76 13 27 49
key 域 next 域
1
0
0
1 2
3
4
5
6
7
8
i2
Max 49 38 65 97 76 13 27 49
2
0
0
1
1
2
3
4
5
6
7
8
i3
Max 49 38 65 97 76 13 27 49
2
3
1
0
记录序列，有三种常见的存储表示方法: · 向量结构：将待排序的记录存放在一组地址连续的存储单 元中。由于在这种存储方式中，记录之间的次序关系由其存储位 置来决定，所以排序过程中一定要移动记录才行。
第9章 内部排序
· 链表结构：采用链表结构时，记录之间逻辑上的相邻
性是靠指针来维持的，这样在排序时，就不用移动记录元素，
第9章 内部排序
为了讨论方便，假设待排记录的关键字均为整数，均从 数组中下标为1的位置开始存储，下标为0的位置存储监视哨， 或空闲不用。 typedef int KeyType; typedef struct { KeyType key; OtherType other-data; } RecordType;
证明一种排序方法是稳定的，要从算法本身的步骤中加以
证明。 证明排序方法是不稳定的，只需给出一个反例说明。
第9章 内部排序
在排序过程中，一般进行两种基本操作： （1） 比较两个关键字的大小；
（2） 将记录从一个位置移动到另一个位置。
其中操作（1）对于大多数排序方法来说是必要的，而操作
（2）则可以通过采用适当的存储方式予以避免。对于待排序的
类: 一类是整个排序过程完全在内存中进行，称为内部排序； 另一类是由于待排序记录数据量太大，内存无法容纳全部数 据， 排序需要借助外部存储设备才能完成，称为外部排序。
第9章 内部排序
假设Ki=Kj(1≤i≤n，1≤j≤n，i≠j)， 若在排序前的序列中Ri
领先于Rj(即i<j)，经过排序后得到的序列中Ri仍领先于Rj， 则 称所用的排序方法是稳定的；反之，当相同关键字的领先关系 在排序过程中发生变化，则称所用的排序方法是不稳定的。 无论是稳定的还是不稳定的排序方法，均能排好序。在应 用排序的某些场合，如选举和比赛等，对排序的稳定性是有特 殊要求的。
图9.1 直接插入排序示例
第9章 内部排序
假设待排序记录存放在r[1..n]之中，为了提高效率，我们 附设一个监视哨r[0]，使得r[0]始终存放待插入的记录。监视 哨的作用有两个：一是备份待插入的记录，以便前面关键字 较大的记录后移；二是防止越界，具体算法描述如下：
第9章 内部排序
void InsertSort(SqList *L) { // 对顺序表L作直接插入排序。算法10.1 for(i=2;i<=L.length;++i) if (LT(L.r[i].key,L.r[i-1].key) // "<",需将L.r[i]插入有序子表 {
第9章 内部排序
0
1 2
3
4
5
6
7
8
i4
Max 49 38 65 97 76 13 27 49
2
0
3
1
1 4 0
2
3
4
5
6
7
8
i5
Max 49 38 65 97 76 13 27 49
2
0
3
1
1 5 0 4
2
3
4
5
6
7
8
i6
Max 49 38 65 97 76 13 27 49
6
3
1 5 0 4 2
i 1: i 2: i 3: i 4: i 8:
first first
（49）
first
final
(38) (49)
final final final
(38) (49) (65)
first
first
(38) (49) (65) (97)
(13 27 38 49 49 65 76 97 )
第9章 内部排序
9.2.1 直接插入排序
直接插入排序是一种最基本的插入排序方法。其基本操作
是将第i个记录插入到前面i-1个已排好序的记录中，具体过程 为： 将第i个记录的关键字Ki顺次与其前面记录的关键字Ki-1， Ki-2，…, K1进行比较，将所有关键字大于Ki的记录依次向后移 动一个位置，直到遇见一个关键字小于或者等于Ki的记录Kj， 此时Kj 后面必为空位置，将第i个记录插入空位置即可。完整 的直接插入排序是从i=2开始的，也就是说，将第1个记录视为