快速排序
快速排序（Quick Sort）是改进的冒泡排序，本质上利用了分治思想。
基本思想
取待排序列中的某个对象（通常选最左端元素）为轴（pivot），以该关键字为基准将序列分为左右两个子序列。比轴小的交换到左侧，比轴大的交换到右侧，轴最终位于正确位置。
分区过程
算法步骤：
- 选最左端元素为轴
- 分配两个指针，起初在两端
- 先对右指针判断，如果大于轴则左移，直到遇到小于轴的，与左指针互换
- 再对左指针判断，如果小于轴则右移，直到遇到大于轴的，与右指针互换
- 重复直到两指针相遇，该位置即轴的位置
递归排序
对轴左右两侧序列分别进行同样的快速排序操作，直到只有一个元素。
算法分析
- 平均时间复杂度：O(n log n)
- 最坏时间复杂度：O(n²)
- 空间复杂度：O(log n)（递归栈）
- 稳定性：不稳定
链接到
- 上一个知识点：6.5 冒泡排序
- 下一个知识点：6.7 简单选择排序