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

Answer 2

快排有很多种，要看首先选出来用来作为参照值的那个数是在哪个位置，有的是取最后一个，有的是随机取一个。这个最好情况说不准，但是不管怎么样，比较的次数都不会变，即使情况好，也是不用做交换操作，比较是一定要进行的。