选择题 25.  用某种排序方法对关键字序列(25,84,21,47,15,27,68,35,20)进行排序,序列的变化情况如下所示:
    (1)20,15,21,25,47,27,68,35,84
    (2)15,20,21,25,35,27,47,68,84
    (3)15,20,21,25,27,35,47,68,84
    则采用的排序方法是______。
【正确答案】 B
【答案解析】 读者要想解答出本题,必须对各种排序算法的原理有着较为深刻的认识。以下将分别对这几种排序算法进行介绍与分析。
   对于选项A,选择排序是一种简单直观的排序算法,它的基本原理如下:对于给定的一组记录,经过第一轮比较后得到最小的记录,然后将该记录与第一个位置的记录进行交换;接着对不包括第一个记录以外的其他记录进行第二轮比较,得到最小的记录并与第二个记录进行位置交换;重复该过程,直到进行比较的记录只有一个时为止。
   对于选项B,快速排序是一种非常高效的排序算法,它采用“分而治之”的思想,把大的拆分为小的,小的再拆分为更小的。其原理为:对于一组给定的记录,通过一趟排序后,将原序列分为两部分,其中前部分的所有记录均比后部分的所有记录小,然后再依次对前后两部分的记录进行快速排序,递归该过程,直到序列中的所有记录均有序为止。
   对于选项C,希尔排序也称为“缩小增量排序”,它的基本原理如下:首先,将待排序的元素分成多个子序列,使得每个子序列的元素个数相对较少,对各个子序列分别进行直接插入排序,待整个待排序序列“基本有序后”,再对所有元素进行一次直接插入排序。希尔排序也是形成部分有序的序列。
   对于选项D,归并排序是利用递归与分治技术将数据序列划分成越来越小的子序列(子序列指的是在原来序列中找出一部分组成的序列),再对子序列排序,最后再用递归步骤将排好序的子序列合并成为越来越大的有序序列。归并排序会在第一趟结束后,形成若干个部分有序的予序列,并且长度递增,直到最后的一个有序的完整序列。
   本题中,很容易发现,第一个序列前4个数都小于等于25,而后5个数都大于25,很显然满足快速排序的方法,而且根据以上对各种排序算法的分析可知,选项B正确。