什么是快速排序？
快速排序由C. A. R. Hoare在1962年提出。
它的基本思想是:
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小.
然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
实现思路：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
过程图解：
如上图所示，经过第一轮划分以后，数组以32位界限被分成了两部分，左边的都比32小，右边的都比32大，接下来只要对两个分区重复上述步骤，直到每个分区都只有一个数据位置。
代码实现：
/**
* @param s
* @param l
* @param r
*/
static void quickSort(int s[], int l, int r) {
if (l < r) {
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;
quickSort(s, l, i - 1); // 递归调用
quickSort(s, i + 1, r);
}
}
总结：
时间复杂度：O（n*lgn）
最坏：O（n^2）
空间复杂度：O（n*lgn）
稳定性：不稳定。
快速排序是一种排序算法，对包含n个数的输入数组，平均时间为O（nlgn），最坏情况是O（n^2）。
通常是用于排序的最佳选择。因为，基于比较的排序，最快也只能达到O（nlgn）。
