快速排序 几种划分方法讨论

最近在复习数据结构与算法，聊聊快速排序的几种划分算法。

快速排序思路

快速排序是一种基于分治策略的排序算法。

对于待排序数组，其核心操作是：

1. 选取一个基准数pivot
2. 将数组分为两块，一块小于等于基准数，另一块大于等于基准数（注意 基准数作为分界点）
3. 递归地对于分出来的两个数字再次进行快速排序

不断地进行划分，递归，最后能保证整个数组有序。

基准数的选取

一般来说，基准数有几种选取方法：

1. 选取第一个数或者最后一个数：这样做，如果数组已经排好序，则每次划分都是基准数和剩余数，时间复杂度升至O(n^2)
2. 随机选择一个数
3. 选取中位数：这样做始终能对原数组进行等分，寻找中位数是线性时间的。

下面以最无脑的方法1...