快速排序最好情况是什么快速排序最好情况下的比较次数,个数n=7,举例说明

Question

快速排序最好情况是什么
快速排序最好情况下的比较次数,个数n=7,举例说明

Answer 1

最好的情况是每次都能均匀的划分序列.
例如 4,1,3,2,6,5,7,每次使用序列的第一个元素做枢轴.比较总次数为10次,交换3次,具体如下：
第一次枢轴为4,序列划分为{2,1,3},4,{6,5,7}
比较6次（4与每个元素比较一次）,交换1次（4与2交换）
第二次的两个序列枢轴分别为2和6,此时划分序列得{1},2,{3},4,{5},6,{7}
比较4次（两个序列各比较两次）,交换两次（1和2,6和5）
第三次由于各个序列的元素都为1,因此排序完成得1,2,3,4,5,6,7