niusouti.com
对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为（62）；若采用快速排序算法，则时间和空间复杂度分别为（63）。A.O（n2）和O（n）B.O（n）和O（n）C.O（n2）和O（1）D.O（n）和O（1）
题目
对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为（62）；若采用快速排序算法，则时间和空间复杂度分别为（63）。
A.O（n2）和O（n）
B.O（n）和O（n）
C.O（n2）和O（1）
D.O（n）和O（1）
相似考题
更多“对n个基本有序的整数进行排序,若采用插入排序算法,则时间和空间复杂度分别为(62);若采用快速排序 ”相关问题
-
第1题：
若待排序序列已基本有序，要使它完全有序，为减少关键码的比较次数和移动次数，应当采用的排序方法是( )。
A．直接插入排序
B．快速排序
C．希尔排序
D．冒泡排序
正确答案：A
解析：直接插入排序是将一个记录插入到已经有序的顺序表中，形成一个新的记录数增加1的有序表。 -
第2题：
采用插入排序算法对n个整数排序，其基本思想是：在插入第i个整数时，前i-1个整数已经排好序，将第i个整数依次和第i-1，i-2，…个整数进行比较，找到应该插入的位置。现采用插入排序算法对6个整数{5，2，4，6，1，3}进行从小到大排序，则需要进行（请作答此空）次整数之间的比较。对于该排序算法，输入数据具有（ ）特点时，对整数进行从小到大排序，所需的比较次数最多。A. 9
B. 10
C. 12
D. 13答案：C解析：采用插入排序算法对6个整数{5，2，4，6，1，3}进行从小到大排序的过程如表所示。
综上，元素间共比较12次。从上表中的第4步可看出，当待插入的元素比已排序部分的所有元素都要小时，需要比较和移动的元素最多，因此当输入数据序列正好从大到小排列，而需要将其从小到大排序时，元素间的比较次数最多。 -
第3题：
采用插入排序算法对n个整数排序，其基本思想是：在插入第i个整数时，前i-1个整数己经排好序，将第i个整数依次和第i-1,i-2,...个整数进行比较，找到应该插入的位置。现采用插入排序算法对6个整数{5，2，4，6，1，3}进行从小到大排序，则需要进行（ ）次整数之间的比较。A.9
B.10
C.12
D.13答案：C解析：这种排序法思想很简单，例如这6个数，先用2和之前的数比较一次，得出序列{2,5}，然后再用4和5,2分别比较一次，得出序列{2,4,5}，当6插入时只需要和5比一次即可，得到新序列{2,4,5,6}，以此类推，最终共比较12次，得到从小到大的最终序列{1，2，3，4，5，6}，故正确答案为C。 -
第4题：
若待排序记录按关键字基本有序，则直采用的排序方法是（ ）。
A. 直接插入排序 B. 堆排序C. 快速排序 D. 简单选择排序
正确答案：A
-
第5题：
若待排序记录按关键字基本有序，则宜采用的排序方法是( )。A.直接插入排序
B.堆排序
C.快速排序
D.简单选择排序答案：A解析：本题考查数据结构基础知识。
根据直接插入排序、堆排序、快速排序和简单选择排序各种方法的排序过程可知，在关键码序列基本有序的情况下，直接插入排序法最为适宜。