原理

对于给定的一组记录，选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分，直到序列中的所有记录均有序为止。

复杂度分析

最坏时间复杂度

最坏情况是指每次区间划分的结果都是基准关键字的左边（或右边）的序列为空，而另一边区间的记录仅比排序前少了一项，即选择的关键字是待排序记录的最小值或最大值。此时的时间复杂度为O(n2)。

最好时间复杂度

最好情况是指每次区间划分的结果都是基准关键字的左右两边长度相等或者相差为1，即选择的基准关键字为待排序的记录的中间值。此时进行比较次数总共为nlogn，所以最好情况下快速排序的时间复杂度为O(nlogn)。

平均时间复杂度

为O(nlogn)。在所有平均复杂度为O(nlogn)的算法中，快速排序的平均性能是最好的。

空间复杂度

快速排序的过程中需要一个栈空间来实现递归。最好情况，递归树的深度为log2n，其空间复杂度也就是O(nlogn)；最坏情况下，需要进行n-1次递归，其空间复杂度为O(n)；平均情况，空间复杂度为O(nlogn)。

案例代码

  1. void quickSort(int[] nums, int l, int r) {
  2.     if (l >= r) {
  3.         return;
  4.     }
  5.     int i = l, j = r;
  6.     int tmp = nums[i];
  7.     while (i < j) {
  8.         // 从右往左找出比基准数字小的
  9.         while (nums[j] >= nums[l] && i < j) {
  10.             j--;
  11.         }
  12.         // 从左往右找出比基准数字大的
  13.         while (nums[i] <= nums[l] && i < j) {
  14.             i++;
  15.         }
  16.         // 交换两个数字
  17.         tmp = nums[i];
  18.         nums[i] = nums[j];
  19.         nums[j] = tmp;
  20.     }
  21.     // 移动基准数字
  22.     nums[i] = nums[l];
  23.     nums[l] = tmp;
  24.     // 分割两部分继续排序
  25.     quickSort(nums, l, i - 1);
  26.     quickSort(nums, i + 1, r);
  27. }