三分钟学会快速排序

快速排序是对冒泡排序的一种改进。

快速排序的原理是一趟排序后划分为两个区间，左区间元素比右区间的小。

然后再分别对两个区间进行排序，可以发现这个过程是递归的。

getMid方法是核心的代码，先是找到分界值，再对范围内的数据进行比较交换，将小的值移动到分界值左边，大的移动到右边。

先找到分界值，把它移到到数组开始的位置。

使用temp存储分界值，因为后面要将分界值回填数组。

接下来从右开始扫描，找到小于等于分界值的元素，则退出右边扫描，转向左边扫描。

循环更替扫描直到start和end指针碰撞了，退出循环。

将分界值填入碰撞处，此时分界值左边的元素比右边的元素小。

快速排序的最好时间复杂度是O(nlogn)，前提条件是划分的左右区间比较均匀。

当每次划分的结果是只有一个区间，快速排序的最坏时间复杂度是O(n2)。

所以扫描阶段，判断和分界值的关系时，建议等于分界值的元素也是符合移动条件的。

举个比较极端的例子，当数组内元素相等时，每一次的区间划分都只是划分为一个区间。