快速排序的问题

blueprint

这是算法引论中介绍的快速排序算法：

1. QUICKSORT(A,p,r)
   
2. 
   
3. 1  if p < r
   
4. 
   
5. 2      then q <-- PARTITION(A,p,r)
   
6. 
   
7. 3           QUICKSORT(A,p,q)
   
8. 
   
9. 4           QUICKSORT(A,q + 1,r)
   
10. 
    
11. 
    
12. PARTITION(A,p,r)
    
13. 
    
14. 1  x  <--- A[p]
    
15. 
    
16. 2  i <--- p - 1
    
17. 
    
18. 3  j <--- r + 1
    
19. 
    
20. 4  while TRUE
    
21. 
    
22. 5      do repeat j <--- j - 1
    
23. 
    
24. 6           until A[j] <=  x
    
25. 
    
26. 7         repeat i <--- i + 1
    
27. 
    
28. 8           until A[i] >= x
    
29. 
    
30. 9         if i < j
    
31. 
    
32. 10            then exchange A[i] <---> A[j]
    
33. 
    
34. 11            else return j
    

复制代码

从代码的PARTITION部分可以看出，每次调用PARTITION，数组A[]中的任意元素至多被交换一次，也就是说整个排序过程中，A[]中的任意元素至多只能交换 n-1 次(n个元素的数组)。我想构造一个某个元素交换了 n-1 次的序列，试了试但没能构造出来。3,1,2 这个太简单除外。也可能这个交换次数的确界不是 n-1？ 一时好奇，发出来问问。