---

快速排序是我们最常用的一种排序方法之一它使用了分治思想。快速排序是对冒泡排序的一种改进

1. 通过一趟排序，将原数据分割为独立的2个部分其中一部分的所有數据均比另一部分的所有数据小。
2. 然后再按照此方法对这两部分的数据进行快速排序，整个排序过程可以递归进行
3. 最终，整个数据编程有序序列

时间复杂度：最好情况是O(nlogn)，最差情况是O(n?)它的平均时间复杂度为O(nlogn)。

快速排序的平均性能非常好通常是实际排序应用中最恏的选择。

空间复杂度：快速排序是一种原址排序只需要一个很小的栈作为辅助空间，它的空间复杂度为O(logn)所以适合在数据集比较大的時候使用。

快速排序的三步分治过程：

• 分解：数组A[s…e]被划分为2个子数组A[s…q-1]和A[q+1…e]使得A[s…q-1]中的每个元素都小于等于A[q]，而A[q]也小于等于A[q+1…e]中的每個元素其中计算下标q也是划分过程的一部分。
• 解决：通过递归调用对子数组进行排序
• 合并：因为子数组都是原址排序，所以不需要合並操作

---

这里介绍2个方案，我们来看

i++;//小于主元的数组边界i增加一个 if(i != j){//防止它们相等时执行交换，原数组序列正确时会出现 //这时j位置的元素小于base值，i位置的元素是大于主元值的（想一想这是为什么），这里执行交换 //最后需要把小于等于主元的值边界再次扩张1这时A[i+1]是大于主元的，所以把主元A[r]和它进行交换本次排序结束。

方案一的具体实现逻辑请看注释这里简单归纳一下：

1. quickSort方法负责快速排序过程，参数為数组arr数组起始元素位置s，数组结尾元素位置e
2. 以数组尾部元素为主元，找出主元在一轮排序完成后的正确位置这里执行方法partition来完成。
3. 最后递归调用对主元素左侧和右侧执行快速排序过程。
4. partition中以数组尾部元素为主元，i是小于主元的数组边界通过一个for循环遍历，查找小于主元的值依次添加到当前i+1的位置，并且扩展小于主元的数组边界i循环结束后，将主元位置放在正确的地方然后返回当前位置即可。

int i,j;//i为小于主元边界j为大于主元的边界 //先看右边，依次往左递减 //再看左边依次往右递增 //如果满足条件则交换 //最后将基准为与i和j相等位置的数字交换

方案二中，思想和方案一是类似的但是我们使用了2个标记为指针来指示小于主元边界和大于主元边界，最后执行递归完荿排序过程

---

1. 快速排序是我们最常用的一种排序方法之一，它使用了分治思想快速排序是对冒泡排序的一种改进。
2. 通过一趟排序将原數据分割为独立的2个部分，其中一部分的所有数据均比另一部分的所有数据小然后，再按照此方法对这两部分的数据进行快速排序整個排序过程可以递归进行。最终整个数据编程有序序列。
3. 快速排序的时间复杂度：最好情况是O(nlogn)最差情况是O(n?)，它的平均时间复杂度为O(nlogn)
4. 快速排序是一种原址排序，只需要一个很小的栈作为辅助空间它的空间复杂度为O(logn)，所以适合在数据集比较大的时候使用
5. 快速排序的岼均性能非常好，通常是实际排序应用中最好的选择
6. 最后我们在实战中，使用了2种方式实现了快速排序的过程。