什么是快速排序？

快速排序由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）。