为什么我们说快速排序的最佳情况是每次执行分区时，我们会将列表分为几乎相等的两个部分"?以及如何证明这正是所谓的最佳案例"?
Why we say the bestcase for quicksort is that "each time we perform a partition we divide the list into two nearly equal pieces"? And how to prove this is exactly the so called "best case"?
推荐答案我创建了一个程序，而不是尝试进行分析.我比较了1/2、1/2(50％50％)分割与1/4、3/4(25％75％)分割的情况，随着n变大，似乎要多花22％的运算.代码设置为1/4,3/4分割:对于1/2,1/2分割，将行从左=(n + 3)/4更改为左=(n + 1)/2.向上舍入的目的是确保left> = 1，以避免无限递归.
I created a program rather than trying to do an analysis. I compared the case of 1/2, 1/2 (50% 50%) split versus 1/4, 3/4 (25% 75%) split, which appears to approach taking 22% more operations as n becomes large. The code is set for the 1/4,3/4 split: for 1/2,1/2 split, change the line from left = (n+3)/4 to left = (n+1)/2. The point of rounding left up is to make sure left >= 1, to avoid infinite recursion.
#include <stdio.h> typedef unsigned long long uint64_t; static uint64_t sum; void qsa(uint64_t n) { uint64_t left, right; if(n < 2) return; sum += n; left = (n+3)/4; /* or left = (n+1)/2 */ right = n - left; qsa(left); qsa(right); } int main() { qsa(1024*1024); printf("%llu\n", sum); return(0); }结果
n = 1024*1024 20971520 1/2 1/2 n log2(n) 25331387 1/4 3/4 ~1.208 n log2(n) n = 16*1024*1024 402653184 1/2 1/2 n log2(n) 488049677 1/4 3/4 ~1.212 n log2(n) n = 1024*1024*1024 32212254720 1/2 1/2 n log2(n) 39180282211 1/4 3/4 ~1.216 n log2(n) n = 16*1024*1024*1024 584115552256 1/2 1/2 n log2(n) 711608157825 1/4 3/4 ~1.218 n log2(n)