对于n个元素组成的线性表进行快速排序 所需的比较次数依赖于这 n个元素的初始排列。 （1)n=7
元素,排列,次数
已帮助 人
对于n个元素组成的线性表进行快速排序，所需的比较次数依赖于这，n个元素的初始排列。 (1)n=7时，在最好情况下需进行多少次比较？请说明理由。 (2)对n=7，给出一个最好情况的初始排列的实例。
请帮忙给出正确答案和分析，谢谢！
-
正确答案：(1)n=7在最好的情况下需进行10次比较。 第一次通过一个元素进行6次比较可以把线性表分为等长的两组每组为3个元素；对于每一组经过两次比较可以再次分成等长的两组每组为一个元素则排序结束。 (2)n=7时给出一个最好情况的初始排列的例子：5243768。 初始状态：5243768。 第一趟排序(比较6次)后：[324]5[768]； 第二趟排序(比较两次)后：[2]3[4]5[768]； 第三趟排序(比较两次)后：[2]3[4]5[6]7[8]。 共比较10次排序结果为：2345678。
(1)n=7,在最好的情况下需进行10次比较。第一次通过一个元素进行6次比较可以把线性表分为等长的两组,每组为3个元素；对于每一组,经过两次比较可以再次分成等长的两组,每组为一个元素,则排序结束。(2)n=7时,给出一个最好情况的初始排列的例子：5,2,4,3,7,6,8。初始状态：5,2,4,3,7,6,8。第一趟排序(比较6次)后：[3,2,4],5,[7,6,8]；第二趟排序(比较两次)后：[2],3,[4],5,[7,6,8]；第三趟排序(比较两次)后：[2],3,[4],5,[6],7,[8]。共比较10次,排序结果为：2,3,4,5,6,7,8。