快速排序

快速排序属于交换排序，基于分治思想：选择一个基准（枢轴）元素，将序列划分为左右两部分，左边都小于基准，右边都大于基准，再对左右子序列递归排序。

基本思想

1. 选取枢轴元素
2. 划分（Partition）：将小于枢轴的放左边，大于的放右边
3. 对左右两部分递归执行

复杂度

• 最好情况（每次划分均匀）：$O(n\log n)$
• 最坏情况（序列基本有序）：$O(n^2)$
• 平均情况：$O(n\log n)$
• 稳定性：不稳定
• 空间复杂度：$O(\log n)$（递归栈）

特点

• 是所有内部排序中平均性能最优的排序算法
• 待排序序列宜采用顺序存储
• 最坏情况发生在序列基本有序时，可通过随机选取枢轴优化