试题出自试卷《02331《数据结构》真题及答案解析（2021.10）》

问题1选项
A.直接插入排序
B.快速排序
C.归并排序
D.基数排序

B

【考点】本题考查排序-交换排序-快速排序
【解析】决速排序（QuickSort）又称为划分交换排序。快速排序是对冒泡排序的一种改进法，在冒泡排序中，进行记录关键字的比较和交换是在相邻记录之间进行，记录每次交换只能上移或下移一个相邻位置，因而总的比较和移动次数较多，不宜在链表上使用，插入排序、归并排序、基数排序易于在链表上实现。故本题选B。
【希赛点拨】快速排序的基本思想是：首先在当前无序区R[low..high]中任取一个记录作为排序比较的基准（不妨设为x），用此基准将当前无序区划分为两个较小的无序区R[low..i-1]和R[i+1..high]，并使左边的无序区中所有记录的关键字均小于等于基准的关键字，右边的无序区中所有记录的关键字均大于等于基准的关键字，而基准记录x则位于最终排的位置i上，即R[low..i-1]中关键字=<x.key=<R[i+1..high]中的关键字。这个过程称为一趟快速排序（或一次划分）。当R[low..i-1]和R[i+1..high]均非空时，分别对它们进行上述划分，直到所有的无序区中的记录均已排好序为止