试题出自试卷《02331《数据结构》真题及答案解析（2021.04）》

问题1选项
A.选择排序
B.冒泡排序
C.直接插入排序
D.快速排序

C

【考点】本题考查排序-插入排序-直接插入排序
【解析】直接插入排序是一种比较简单的排序方法，它的基本操作是：假设待排序的记录存储在数组R[1..n]中，在排序过程的某一时刻，R被划分成两个子区间，R[1..i-1]和R[i..n]，其中前一个为已排好序的有序区，而后一个为无序区，开始时有序区中只含有一个元素R[1]，无序区为R[2..n]。排序过程中，只需要每次从无序区中取出第一个元素，把它插入到有序区的适当位置，使之成为新的有序区，依次这样经过n-1次插入后，无序区为空，有序区中包含了全部n个元素，至此排序完毕。故本题选C。
【希赛点拨】直接插入排序算法有两重循环：外循环表才示要进行n-1趟排序，内循环表明完成一趟排序所进行的记录关键字间的比较和记录的后移。在每一趟排序中，最多可能进行i次比较，移动i-1+2=i+1个记录（内循环前后作两次移动）。所以，在最坏情况下（反序），插入排序的关键字之间比较次数和记录移动次数达最大值。