对n个关键码构成的序列采用直接插入排序法进行升序排序的过程是：在插入第i个关键码K<..

2017年下半年上午试卷综合知识

第 43 题


知识点	简单排序直接插入排序排序
关键词	插入排序关键码排序
章/节	常用算法

对n个关键码构成的序列采用直接插入排序法进行升序排序的过程是：在插入第i个关键码K_i时，其前面的i-1个关键码已排好序，因此令K_i与K_i-1、K_i-2、...，依次比较，最多到K₁为止，找到插入位置并移动相关元素后将K_i插入有序子序列的适当位置，完成本趟（即第i-1趟）排序。以下关于直接插入排序的叙述中，正确的是（）。

A. 若原关键码序列已经升序排序，则排序过程中关键码间的比较次数最少

B. 若原关键码序列已经降序排序，则排序过程中关键码间的比较次数最少

C. 第1趟完成后即可确定整个序列的最小关键码

D. 第1趟完成后即可确定整个序列的最大关键码

相关试题排序算法

第42题

2020年下半年

对于含有n个元素的关键码序列{k₁,k₂,...,k_n},当且仅当满足关系k_i≤k_2i且k_i≤k_2i+1(i=1,2,...,[n/2])时称为小根..

第39题

2016年下半年

若要求对大小为n的数组进行排序的时间复杂度为O(nlog2n)，且是稳定的（即如果待排序的序列中两个数据元素具有相同的值，在排序前后它们的相对位置不变），则可选择的排序方法是（39）。

第42题

2015年上半年

根据枢轴元素（或基准元素）划分序列而进行排序的是（42)。

知识点讲解

· 简单排序

· 直接插入排序

· 排序

简单排序

简单排序包括直接插入排序、冒泡排序、简单选择排序等方法。

1）直接插入排序

直接插入排序的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。

2）冒泡排序

首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序（即 r[1].key>r[2].key），则交换两个记录，接着比较第二个记录和第三个记录的关键字。依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。这个过程称为第一趟冒泡排序，使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，结果是使关键字次大的记录被安置到第n-1个记录的位置上。当进行完第n-1趟冒泡排序时，所有记录都已有序排列。

3）简单选择排序

简单选择排序的基本思想是：在进行每趟排序时，从无序的记录中选择出关键字最小（或最大）的记录，将其插入到有序序列（初始时为空）的尾部。

直接插入排序

若设R[1...n]为待排序的n个记录，R[1...i-1]已按照主关键字由小到大排序，则直接插入排序的主要思路如下。

（1）寻找R[i]在R[1…i-1]中的插入位置，确保R[i]插入后保持有序。

（2）i增1，若i小于等于m，则转到（1）执行，否则结束。

顺序线性存储结构下的直接插入排序算法如下：

【点评】

（1）对n个结点的线性表采用直接插入排序，当线性表已是从小到大排序时，内循环每执行一次，只需要进行1次比较，整个排序过程只进行n-1次比较。当线性表已是从大到小排序时，对外循环执行i次，内循环要进行i次比较，整个排序过程需要进行n(n-1)/2次比较。可见，对n个结点的线性表采用直接插入排序，最少比较次数为n-1，最多比较次数为n(n-1)/2。

（2）直接插入排序是在有序表的基础上进行的，所以排序效率较高且比较稳定。

排序

假设含n个记录的文件内容为｛R₁，R₂，…，R_n｝，其相应的关键字为｛k₁，k₂，…，k_n｝。经过排序确定一种排列｛R_j₁，R_j₂，…，R_jn｝，使得它们的关键字满足如下递增（或递减）关系：k_j₁≤k_j₂≤…≤k_jn（或k_j₁≥k_j₂≥…≥k_jn）。

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5