算法(1) -- 快排

从最基本的排序算法，一个一个来整理。算法老是学了就忘，这次
我记录下来，我看还能不能忘  -_-

伪码：

QUICKSORT(A,p,r)
   if p < r
      then  q <-- PARTITION(A,p,r)
         QUICKSORT(A,p,q-1)
         QUICKSORT(A,q+1,r)
PARTITION(A,p,r)
   x <-- A[r]
   i <-- p-1
   for j <-- p to r - 1
      do  if A[j] <= x
             then  i <-- i+1
                   exchange  A[i] <-->  A[j]
   exchange  A[i+1] <--> A[r]
   return i+1

这个没有什么说的，算法导论上的，刚开始看的时候，愣是没有看明白，而且还一度怀疑
这个伪码是不是写错了，因为我很怀疑  第12行
但是你的结论不能因为“你觉着”，它就自动成立的，这个是需要证据的，于是，自己
搞了一下
没有找到好的作图工具，graphviz不会表示数组，只能在这里用键盘画图了，:(

  

i p,j                                                    r
________________________________
| 2 | 8 | 7 | 3 | 1 | 9 | 10 | 4 |
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

  初始阶段  x = 4  j = p = 1    i = 0
  A[1] < 4, so i = 1, A[1] <-->  A[1] // 这里相当什么都没有做
 
  然后  j = 2  i = 1
  A[2] = 8 > 4,  循环里面什么都么有做

  然后  j = 3  i = 1
  A[3] = 7 > 4 , 循环里面还是什么都没有做

  然后  j = 4   i = 1
  A[4] = 3 < 4, 这个时候，i = 2, A[2] <--> A[4]
  调整后的图形是这样的

p        i      j                                 r
________________________________
| 2 | 3 | 7 | 8 | 1 | 9 | 10 | 4 |
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

  归根结底，快排是通过  i,j 两个游标将  数组A 分成 3份
  A[p, i]  都是 小于A[r]的
  A[i+1, j] 都是大于或等于 A[r]的
  A[j+1, r] 大，小关系不明的

  另外，可以看到  i是指向小于 A[r]的最后一个元素的，如果 i+1 的话，则A[i]就是
  大于A[r]了，这也就是为什么
  当A[j] < A[r] 的时候
  执行  i+1  A[i] <--> A[j] 的原因了，所以书上写的是对的