6.4 快速排序

6.4 快速排序

选择题

　　1．选择题题目部分
　　● 一组记录的排序码为{46,79,56,38,40,84}，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 （1） 。
　　（1）A．38,40,46,56,79,84 B．40,38,46,79,56,84
　　　　 C．40,38,46,56,79,84 D．40,38,46,84,56,79
　　● 在内部排序中，通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和（时间）复杂性。对给定的整数序列(541,132,984,746,518,181,946,314,205,827)进行从小到大的排序时，采用快速排序（以中间元素518为基准）的第一趟扫描结果是 （2） 。
　　（2）A．(181,132,314,205,541,518,946,827,746,984)
　　　 　B．(541,132,827,746,518,181,946,314,205,984)
　　　　 C．(205,132,314,181,518,746,946,984,541,827)
　　　　 D．(541,132,984,746,827,181,946,314,205,518)
　　2．选择题练习的答案与分析
　　题号 （1）
　　答案 C
　　习题分析：
　　题目要求以第一个记录为基准所以首先程序会把第一个记录取出，存到关键字key中，如图6-1所示。
　　然后把j指针指向的数据与key比较，当前的j指向数据为84，它大于key，无需做操作，所以把j向左移一格，这样j指向40，40比key小，所以把j所指的数据40移动到i位置，并把i指针右移一格，如图6-2所示。

　　　　　图6-1 快速排序示意图（1） 　　　　　　　图6-2 快速排序示意图（2）

　　接下来判断79是否大于key，由于79大于key，所以把79移到j所指的位置，并把j左移一格，如图6-3所示。
　　接下来，把j所指的38移到i所指位置，并把i右移一格，如图6-4所示。
　　最后，i和j指向同一个空间，如图6-5所示。

　　　图6-3 快速排序示意图（3）　　　　　　 图6-4 快速排序示意图（4）
 

　　　　图6-5 快速排序示意图（5）

　　此时，将关键字key填入此空间，快速排序的第一趟也就完成了。排序序列应是：40,38,46,56,79,84，所以答案为C。
　　题号 （2）
　　答案 C
　　习题分析：
　　根据习题1中给出的快速排序的基本过程，可得出本题的答案为C。单按上面的做法一一写出快速排序的序列，要浪费很多时间。这里教大家快速判别的方法：以518为中间，进行一趟快速排序后的结果，最大的特点是“518前面的数，都小于518，518后面的数都大于518”，把这个规则一用，马上就得到答案，因为备选答案中只有C序列满足这个要求，所以此题答案为C。
　　3．训练自测表（如表6-4所示）

表6-4 选择题练习自测表