快速排序算法

一、快速排序算法的基本特性
时间复杂度：O（n*lgn）
最坏：O（n^2）
空间复杂度：O（n*lgn）
不稳定。

快速排序是一种排序算法，对包含n个数的输入数组，平均时间为O（nlgn），最坏情况是O（n^2）。
通常是用于排序的最佳选择。因为，排序最快，也只能达到O（nlgn）。

二、快速排序算法的描述
算法导论，第7章
快速排序时基于分治模式处理的，
对一个典型子数组A[p...r]排序的分治过程为三个步骤：
1.分解：
A[p..r]被划分为俩个（可能空）的子数组A[p ..q-1]和A[q+1 ..r]，使得
A[p ..q-1] <= A[q] <= A[q+1 ..r]
2.解决：通过递归调用快速排序，对子数组A[p ..q-1]和A[q+1 ..r]排序。
3.合并。

QUICKSORT(A, p, r)
1 if p < r
2    then q ← PARTITION(A, p, r)   //关键
3         QUICKSORT(A, p, q - 1)
4         QUICKSORT(A, q + 1, r)


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

 微软等数据结构+算法面试100题全部答案集锦

http://blog.csdn.net/v_july_v/article/details/6870251