【算法学习】快速排序(原地分区)

最近重新学习算法,先从几个排序算法开始。快速排序是比较有名的一个排序算法,基本原理我明白,但是之前只会筛选构造新序列分区的方式,现在要学的是原地分区的方式。
成果代码如下,使用Java编写(C/C++的数组和指针操作忘得差不多了)。

说明一下自己在学习原地分区核心算法时候的理解,也就是上面partition方法的逻辑。
众所周知,快速排序基于一个基准点pivot,这也就是前两行代码做的事情。

接下来就是正式的分区。分区的目地是把小于基准点的数筛选到基准点左边去,大于的到右边去(以升序序列为例)。
为此,设置一个小于基准点的数字的索引index,初始为开始位置begin。找到任何一个小于基准点的数之后都需要和这个索引位置的数字做交换,以便把小于基准点的数集中起来。
其次,在筛选之前,为了避免基准点对于分区的影响,把基准点放到最后去。
执行具体举例:

对比代码

个人认为,理解了这一快,理论上快速排序基本的东西就差不多了。