快速排序是一种分治策略的排序算法，关键过程是对数组进行划分。选择一个基准值（pivot element），围绕着这个基准值划分子数组，对子数组递归调用快速排序，直到数组有序。
1、选取基准元素。将最后一个元素（随机值、三数中值） 作为基准值 pivot。
2、划分子数组。遍历数组，将小于基准值的元素交换到左边，大于基准值的元素交换到右边，将基准值交换到正确的位置，并返回其索引作为分区点。经过这一步骤之后，数组被划分成小于和大于基准值的2个子数组。
3、递归调用。递归地对这2个子数组进行快速排序，直到整个数组有序。
- 一次快速排序的过程
- 快速排序全过程
- 数组变化
- 时间复杂度：O(n log n)
快速排序的时间复杂度可以通过递归树来分析。在每一层中，我们选择一个主元素并将数组划分为两个子数组，时间复杂度为O(n)。如果我们将递归树表示为二叉树，则总共有 log n 层，并且每层的时间复杂度为 O(n)，因此整个算法的时间复杂度为 O(n log n)。
以下情况快速排序的时间复杂度将退化为 O(n^2)：
1、数组已经有序。在待排序数组已经有序的情况下，每次划分只能减少一个元素，时间复杂度将退化为 O(n^2)。
2、基准值有问题。选择的基准值不能把数组分区成均衡的两部分，基准值都是最小或最大的元素，导致每次分区后，一个子数组为空，而另一个子数组包含剩余的所有元素，时间复杂度将退化为O(n^2)。
- 空间复杂度：O(log n)
快速排序的空间复杂度主要由递归调用栈决定。在最好的情况下（即每次分区都非常平衡），递归深度为 log n，因此空间复杂度为 O(log n)。
在最坏的情况下（即每次分区都极度不平衡），递归深度可以达到 n，空间复杂度将退化为 O(n)。
快速排序是不稳定的排序算法，因为在排序过程中会涉及到交换操作，可能导致相同元素的相对顺序发生变化。