33. java快速排序

1. 前言

排序算法是数据结构中最基础的算法，快速排序则是面试中最常见的排序算法。无论是校招面试还是社招面试，快速排序算法的出现频率远高于其他算法，而且经常会要求候选人白板手写实现算法。快速排序算法的核心是分治处理，重点是分析时间复杂度。

2. 快速排序算法

面试官提问：快速排序算法是怎么实现的？能手写实现一个快排算法吗？

题目解析：

为了实现bug free（基本没有逻辑缺陷）的白板编程，候选人可以将解决这个题目的过程分为两个步骤：

（1）分析快速排序算法的步骤，并且编码实现；
（2）完成编码后，使用一个小规模的数据作为测试样例，模拟算法流程验证代码逻辑是否符合预期。

2.1 快速排序步骤

快速排序算法的核心是分治算法，所谓分治（Divide and Conquer）就是将一个复杂的问题分成两个或者多个相同或者相似的子问题，再把这些子问题分成多个相同或者相似的子问题，直到子问题能够被简单求解&