整理定义

中文名称：快速排序

英文名称：quicksort

复述展开

快速排序 (Quick Sort) 快速排序用到了分治思想，同样的还有归并排序。乍看起来快速排序和归并排序非常相似，都是将问题变小，先排序子串，最后合并。 不同的是快速排序在划分子问题的时候经过多一步处理，将划分的两组数据划分为一大一小，这样在最后合并的时候就不必像归并排序那样再进行比较。但也正因为如此，划分的不定性使得快速排序的时间复杂度并不稳定。

快速排序的基本思想： 通过一趟排序将待排序列分隔成独立的两部分，其中一部分记录的元素均比另一部分的元素小，则可分别对这两部分子序列继续进行排序，以达到整个序列有序。

📌 算法步骤 快速排序使用分治法（Divide and conquer）策略来把一个序列分为较小和较大的 2 个子序列，然后递回地排序两个子序列。具体算法描述如下：

📌 算法分析

代码

理解体会

1、快速排序的最差情况分析，时间复杂度应该是O(n^2)。【此时作为基准的选择基本上都是选择左侧或者右侧第一位】

最差情况下，逆序情况，每次选择基准都是将两部分分为0，N，导致最终的时间复杂度退化到O(n^2)

对于上述的情况，可以通过随机选择基准来避免上述的情况。

所以，在上面，使用策略之后，最坏的情况也能达到 O(nlogn)