若待排序的记录较少，可采用直接插入排序和简单选择排序。
- 直接插入排序所需的记录移动操作较简单选择排序多，因而当记录的信息较大时，用简单选择排序方法较好。
若待排序的记录基本有序，采用直接插入排序或冒泡排序。
若排序记录很多且关键字位数较少时，采用基数排序较好。
若排序记录较多，则应采用时间复杂度为O(nlog2n)的排序方法，例如快速排序、堆排序或归并排序：
- 快速排序和堆排序都是不稳定的排序方法，若要求排序稳定，可选择归并排序。
- 快速排序目前被认为是内部排序中最好的方法，当待排序的关键字为随机分布时，快速排序的平均运行时间最短；
- 堆排序只需要一个辅助空间，并且不会出现快速排序中可能出现的最快情况。
现需要对一个基本有序的数组进行排序。此时最适宜采用的算法为（64）排算法，时间复杂度为（65）。
(64) A.插入 B.快速 C.归并 D.堆
(65) A.O(n) B.O(nlgn) C.O(n²) D.O(n²lgn)
【答案】A A
【解析】插入排序对基本有序的数组排序速度快；若数据基本有序，对插入排序算法而言，直接插入排序过程中元素比较的次数较少，则可以在近似线性时间内完成排序。即O(n)。
在某应用中，需要先排序一组大规模的记录，其关键字为整数。若这组记录的关键字基本上有序，则适宜采用（64）排序算法。若这组记录的关键字的取值均在0到9之间（含），则适宜采用（65）排序算法。
(64) A.插入 B.归并 C.快速 D.计数
(65) A.插入 B.归并 C.快速 D.计数
【答案】A D
【解析】本题考查算法设计和排序的基础知识。
排序是一类最基本的操作，因此要求考生熟悉一些典型的排序算法，包括其算法思想、时空复杂度以及应用场合。若数据基本有序，插入排序应该是最佳选择，输入数据是否有序对归并和计数排序算法并没有影响。对传统的快速排序算法，输入数据有序反而使其效率最低。若关键字取值范围较小，则计数排序是最佳选择，因为在该情况下，该算法的时间复杂度为线性时间。
