数据结构与算法之排序算法

如你所知，排序算法是学习数据结构与算法中非常重要的一个模块。一般衡量一个排序算法会从时间复杂度，空间复杂度，排序方式，排序稳定性等方面进行分析。

快速排序（简称快排）为一种非常经典的排序算法，是一种比较的，综合时间复杂度 O(nlogn)，空间复杂度 O(logn) 的不稳定性算法。

快排是基于分治算法思想的经典应用，更是常年来在考研升学，求职面试中的老朋友。因此掌握好快排可以说是我们程序员的必备技能之一。并且快排可以衍生出更多的技巧和知识，如随机优化，快速选择等技巧。

分治算法

什么是分治算法？

分治即分而治之。分治是一种“并行”算法，通过将大问题分解为一个个小问题逐个击破。这种思路天然的适合使用递归表示。

一般分治算法可以分为三个步骤：

• 分解：把问题分解成独立的子问题
• 解决：递归的解决子问题
• 合并：将子问题的结果合并成原来问题的结果