6.2 插入排序

6.2 插入排序

6.2 插入排序

　　考试大纲涉及本节的知识点有：直接插入排序、折半插入排序、希尔排序和二路归并排序。

选择题

　　1．选择题题目部分
　　● 从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法称为 （1） 。
　　（1）A．插入排序 B．选择排序 C．希尔排序 D．归并排序
　　● 折半插入排序的时间复杂度是 （2） 。
　　（2）A．O(n) B．O(n²) C．O(log(n)) D．O(nlog(n))
　　2．选择题练习的答案与分析
　　题号 （1）
　　答案 　A
　　习题分析：
　　从未排序的序列中每次取出一个元素与已排序的元素比较，然后将其放在已排序的序列中的合适位置，这种方法是直接插入排序。
　　题号 （2）
　　答案 　B
　　习题分析：
　　从时间上来说，折半插入排序只是减少了关键字间比较的次数，而记录的移动次数不变。因此，其时间复杂度为O(n²)。
　　3．训练自测表（如表6-2所示）

表6-2 选择题练习自测表

题    号	考  查  点	得    分
（1）	插入排序的概念
（2）	折半插入排序的时间复杂度

6.2 插入排序