我想从理论上问(不考虑循环中的比较)在排序数组的情况下比较的次数是如何不同的。假设有一个实现，它选择最后一个元素作为枢轴元素。现在给出了一个长度为10的数组。这里我只讨论索引。1比;如果数组排序为:10，则元素为枢轴，总比较为9。(对于特定的实现):a)1 2 3 4 5 6 7 8 9 <10>comp = 9(考虑到第9元素)b)1 2 3 4 5 6 7 8 <9> 10comp = 8(枢轴为9)....等等......所以总比较数= 9 + 8 + 7 +…1 ~ n^2
2比;如果我们给定某种排列使得每次我们把主元放在数组的中间。a)1 2 3 4 5 6 7 8 9 <10>comp = 9 (pivot = 10)现在让它在中间被分割b)我们得到这两个分区1 2 3 4 <5>6 7 8 <9> 10comp = 4 + 3 = 7…等等。
我看不出这两者有多大区别。
问题在于递归的深度，而不是每个递归级别的比较次数。假设枢轴排除进一步递归，第一种情况是9级递归，45比较，第二种情况是3级递归，19比较:
1 2 3 4 <5> 6 7 8 9 10 - 9 compares
1 <2> 3 4 6 7 <8> 9 10 - 7 compares
1 <3> 4 <6> 7 <9> 10 - 3 compares
------------
19 compares
快速排序的理想大小是2^k-1个元素。考虑15个元素(以十六进制显示)。第一种情况是14级递归，105级比较。第二种情况是3级递归，34比较:
1 2 3 4 5 6 7 <8> 9 a b c d e f - 14 compares
1 2 3 <4> 5 6 7 9 a b <c> d e f - 12 compares
1 <2> 3 5 <6> 7 9 <a> b d <e> f - 8 compares
-------------
- 34 compares