快速排序中的比较次数

Question

我想从理论上问（不考虑循环中的比较）在排序数组的情况下比较次数有何不同。假设有一个选择最后一个元素作为枢轴元素的实现。现在给出了一个长度为 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> 10 comp = 8 ( pivot 是 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> 10 comp = 4 + 3 = 7 ...等等。

我没发现这两个有太大区别。

Answer 1

问题在于递归的深度，而不是每层递归的比较次数。假设pivot被排除在进一步递归之外，第一种情况是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

快速排序中的比较次数

Number of comparison in Quick Sort

quicksort