设有字符序列(Q,H,C,Y,P,A,M,S,R,D,F,X),问新序列(F,H,C,D,P,A,M,Q,R,S,Y,X)是下列哪一个排序算

Question

设有字符序列（Q，H，C，Y，P，A，M，S，R，D，F，X），问新序列（F，H，C，D，P，A，M，Q，R，S，Y，X）是下列哪一个排序算法一趟扫描的结果？

A．起泡排序

B．初始步长为4的希尔排序

C．二路归并排序

D．以第一元素为分界元素的快速排序

Answer 1

正确答案：D
解析：起泡排序的基本思想是将表中两个相邻元素依次比较，若不符合排序要求，则交换位置，这样经 过n-1次比较后，将确定出最大(或最小)元素的位置，这称为一趟扫描。经过n-1次扫描后， 就完成了整个表的排序。希尔(Shell)排序法的基本思想是第一步是将数据分成n1(n1为初始步长)个组，所有距离为n 的倍数的元素分在一个组中，各组内用插入法排序。然后让第二个步长n2(n2快速排序的基本思想是把表中某元素作为基准，将表划分为大于该值和小于该值的两部分，然 后用递归的方法处理这两个子表，直到完成整个表的排序。不难看出，上述的新序列是按快速排序的思想扫描的结果。