快速排序（Quick sort）是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1960年提出。

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

1、首先设定一个分界值，通过该分界值将数组分成左右两部分。

2、将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

3、然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

4、重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

概括来说为 挖坑填数 + 分治法。

快速排序主要有三个参数，left 为区间的开始地址，right 为区间的结束地址，Key 为当前的开始的值。

我们从待排序的记录序列中选取一个记录（通常第一个）作为基准元素（称为key）key=arr[left]，然后设置两个变量，left指向数列的最左部，right 指向数据的最右部。

key 首先与 arr[right] 进行比较，如果 arr[right]key则我们只需要将right--，right--之后，再拿arr[right]与key进行比较，直到arr[right] 6 ,所以停止移动当左右标记停止时，更改标记的数字因此，左标记 的作用是找到一个大于 pivot 的数字，右标记 的作用是找到一个小于 pivot 的数字通过交换数字，可以在数列的左边收集小于 pivot 的数字集合，右边收集大于 pivot 的数字集合交换之后，继续移动 左标记在这里，9 > 6 ,所以停止移动然后将右边的标记向左移动当 右标记 碰撞到 左标记 时也停止移动如果左右侧的标记停止时，并且都在同一个位置，将这个数字和 pivot 的数字交换这就完成了第一次操作小于 6 的都在 6 的左侧，大于 6 的都在 6 的右侧然后递归对这分成的两部分都执行同样的操作完成 快速排序 算法性能 时间复杂度 理想情况

如果足够理想，那我们期望每次都把数组都分成平均的两个部分，如果按照这样的理想情况分下去，我们最终能得到一个完全二叉树。如果排序 n 个数字，那么这个树的深度就是，如果我们将比较 n 个数的耗时设置为 T(n)，那我们可以得到如下的公式

而在最坏的情况下，这个树是一个完全的斜树，只有左半边或者右半边。这时候我们的比较次数就变为

原地快排的空间占用是递归造成的栈空间的使用，最好情况下是递归次，所以空间复杂度为，最坏情况下是递归 n-1 次，所以空间复杂度是。

对于非原地排序，每次递归都要声明一个总数为n的额外空间，所以空间复杂度变为原地排序的n倍，即最好情况下，最差情况下。

不稳定。