快速排序浅谈

          快速排序作为分治法的一种，也同样遵循分治法的基本步骤---分解、治之、合并。我们在分解之前得选一个元素元素作为分解的依据，相当于一个基本点。
          分解：以支点为界将序列分解为两个子序列，其中一个子序列里的元素小于等于支点，另一个子序列的元素大于支点。
          治之：对两个子序列进行快速排序（递归）。

          合并：将排好序的两个子序列合并成一个大序列。
例如有一个数组A[p,r]，p代表数组首元素的下标，而r则代表数组末元素的下标。则对其进行快速排序的过程为：

quick(A,p,r)
{
   if(p<r)
   {
      q = partition(A,p,r);
      quick(A,p,q-1);
      quick(A,q+1,r);
   }
}

上面这个排序过程的关键就是partion这个过程，它对数组A进行就地重排。下面我们来看看partion这个过程的实现：：

partition(A,p,r)
{
    x = A[r];
    i = p-1;     //i初始化为子序列第一个元素的下标减1
     for(j=p;j<r;j++)
     {
        if(A[j]<=x)
        {
          i++;
          exchange A[i]<-->A[j]
        }
     }
     exchange A[i+1]<-->A[r]
    return i+1;
}

在这里我们取子序列中最后一个元素作为支点元素：下面的图为上面算法过程的图示


在执行到 h 的时候循环已跳出，交换A[i+1] 与A[r] 。至此所有比支点小的元素都已放在了支点的左边，而所有比支点元素大的数也都放在了其右边，将i+1返回，partition函数的功能完成。则第一个子序列为 (2,1,3) 第二个子序列为(7,5,6,8)。下面对这两个子序列分别进行quick(),当p不小于 r 时递归结束，下面进行合并，由于我们这儿排序
是就地排序所以合并这个环节也就可以省去了。。