快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想--分治法也确实实用，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个，还有大大小的程序方面的考试如软考，考研中也常常出现快速排序的身影。

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法

该方法的基本思想是：

  1. 先从数列中取出一个数作为基准数。
  2. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
  3. 再对左右区间重复第二步，直到各区间只有一个数。

对挖坑填数进行总结

  1. i =L; j = R; 将基准数挖出形成第一个坑a[i]。
  2. j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
  3. i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
  4. 再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

照着这个总结很容易实现挖坑填数的代码：

//快速排序
void quick_sort(int s[], int l, int r)
{
    if (l < r)
    {
        //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
        int i = l, j = r, x = s[l];
        while (i < j)
        {
            while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
            {
                j--;  
            }
            if(i < j)
            {
                s[i++] = s[j];
            }

            while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
            {
                i++;  
            }
            if(i < j)
            {
                s[j--] = s[i];
            }
        }
        s[i] = x;
        quick_sort(s, l, i - 1); // 递归调用 
        quick_sort(s, i + 1, r);
    }
}

快速排序还有很多改进版本，如随机选择基准数，区间内数据较少时直接用另的方法排序以减小递归深度。有兴趣的筒子可以再深入的研究下。

参考资料http://blog.csdn.net/morewindows/article/details/6684558