读书笔记之快速排序（三）

时间：2020-12-05 22:08:26

在读书笔记之快速排序（一）和读书笔记之快速排序（二）中对快速排序算法进行了各种变换，当然每一种变换的侧重点都不同。那么，对于大小为 n 的随机数组来说，Quicksort算法平均需要进行多少次的比较呢？

  • 1-7 统计Quicksort的平均比较次数
  
 
 
    

  1. float c(int n) 
    2. 
   
  
  
  2. { 
    3. 
   
  
  
  3.     if(n <= 1)     
    4. 
   
  
  
  4.         return 0; 
    5. 
   
  
  
  5.     for(m = 1;m <= n;m++) 
    6. 
   
  
  
  6.         sum += n-1 + c(m-1) + c(n-m); 
    7. 
   
  
  
  7.     return sum/n 
    8. 
   
  
  
  8. } 
    9.

从上面的代码中可以看到，如果在输入的数组中最多只有一个元素，那么Quicksort将不会进行比较。

当然上面的代码需要更多的时间开销，因为它重复计算了中间结果，对于这种情况，可以使用动态变成来存储中间结果，从而程序重复计算。用 N 来表示  n 的最大值，也就是进行排序数组的大小。如代码 1-8

  • 1-8 在Quicksort中使用动态编程来计算平均比较次数
   
  
  
    

  1. t[0] = 0; 
    2. 
    
   
   
  2. for(n = 1;n <= N ; n++) 
    3. 
    
   
   
  3.      sum = 0; 
    4. 
    
   
   
  4.      for(i = 1; i <= n; i++) 
    5. 
    
   
   
  5.            sum += n-1 +t[i-1] + t[n-i] ; 
    6. 
    
   
   
  6.      t[n] = sum/n ; 
    7.

上述代码中用t[n]来替换代码1-7中的c(n)，与1-7相比，缩短了时间。改程序的另外一个优点就是：在程序执行结束时，数组t 中包含数组中从元素 0 到 元素N的真实平均值。

下面对程序做进一步的简化，第一步就是把 n-1 移到循环的外面。如代码1-9

  • 1-9 在Quicksort中把代码移到循环外面来计算。
   
  
  
    

  1. t[0] = 0; 
    2. 
    
   
   
  2. for(n = 1; n <= N ;n++) 
    3. 
    
   
   
  3.      sum = 0; 
    4. 
    
   
   
  4.      for(i = 1;i <= n ; i++) 
    5. 
    
   
   
  5.            sum += t[i-1] + t[n-1]; 
    6. 
    
   
   
  6.      t[n] = n-1 + sum/n 
    7.

现在就可以利用对称性来对循环做进一步的调整，例如，当n 为4是，内部循环计算总和为：

t[0]+t[3] + t[1]+t[2] + t[2]+t[1] + t[3]+t[0]

在上面这些数组对中，第一个元素增加而第二个元素减少。因此，我们可以把总和改写为：

2 * (t[0] + t[1] + t[2] + t[3]),根据对称性，可以得到1-10的代码。

  • 1-10 Quicksort中利用了对称性来计算平均比较次数。
   
  
  
    

  1. t[0] = 0; 
    2. 
    
   
   
  2. for(n = 1 ; n <= N ;n++) 
    3. 
    
   
   
  3.      sum =0; 
    4. 
    
   
   
  4.      for(i = 0 ;i <= n ; i++) 
    5. 
    
   
   
  5.           sum += 2 * t[i]; 
    6. 
    
   
   
  6.      t[n] = n-1 + sum/n; 
    7.

显然上面这段代码页存在运行时间的浪费，因为重复计算了相同的总和。因此，可以不把前面所有的元素加在一起，而是在循环外部初始化总和并且加上下一个元素，如代码1-11。

  • 1-11 在Quicksort中删除了内部循环来计算。
   
  
  
    

  1. sum = 0； 
    2. 
    
   
   
  2. t[0] = 0; 
    3. 
    
   
   
  3. for(n = 1; n <= N ;n++) 
    4. 
    
   
   
  4.      sum += 2 * t[n-1]; 
    5. 
    
   
   
  5.      t[n] = n-1 + sum/n; 
    6.

这个仅仅几行的代码确实很有用，程序的运行时间与N成正比，对于每个从1 到N 的整数，程序将生成一张Quicksort的估计运行时间表。

通过以上的不断修该，可以得到下面的Quicksort的最终版本。

  • 1-12 Quicksort计算——最终版本
   
  
  
    

  1. sum = 0; 
    2. 
    
   
   
  2. t = 0; 
    3. 
    
   
   
  3. for(n = 1; n <= N;n ++) 
    4. 
    
   
   
  4.      sum += 2*t; 
    5. 
    
   
   
  5. 
     t = n-1 + sum/n; 
    

    6.

可以上面的这段代码非常精炼，而功能却完善。我们应该学习这样的代码，用更少的代码实现功能，并且不断的完善，如此，我们才会写出自己的完美的代码。

本文出自 “花开花落” 博客，请务必保留此出处http://020618.blog.51cto.com/6098149/1179595

标签：

相关文章