概念
1. 在序列中选择一个元素（如何选择并不重要，记为 pivot），通过遍历的方式，比较给定 元素和区间内其他元素的大小关系
2. 在遍历期间，通过算法的设计，将序列排成如下图序列
注意：<= pivot 和 >= pivot 区间内顺序无法保证
pivot 也很大可能不在中间
3. 此时认为 pivot 就处于序列有序后其应该在的位置，最后对左右两个区间分别排序
排序过程中的小细节
1. 如果区间内元素个数 <= 1，则不用做任何处理，因为天然有序
2. 从区间中（这个区间不代表整个数组，需要用 [from, to] 来限定）中挑选一个 pivot ，方式 随意
3. 遍历区间，将每个元素都和 pivot 进行比较，并且进行必要的位置移动，使得遍历完成 后，满足上图所示区间
把这个处理区间的过程称为 partition
注意：partition 的过程只是快速排序中的一个小步骤，并非全部过程
4.大区间处理完成后，继续对两个小区间按照同样的方法进行处理（算法可使用递归）
具体的 partition 的方法
partitionMethodA
从 array[left] 开始与 pivot 进行比较，当出现 array[left] > pivot 时，left++ 停止，array[right] 再与 pivot 比较，出现array[right] < pivot 时，right-- 停止，随后交换array[left] 和 array[right] ,重复此操作直到 [left, right) 区间内没有元素了（即 left ==right），最后再将 array[to] 和array[left](或 array[right] )的值交换（即将 pivot 的值放在序列中间），至此第一次 partition 完成
partitionMethodB
最开始 to == right
取 array[to] = pivot ,从array[left++] 开始依此与 pivot 进行比较，若遇到 > pivot 的元素，将array[left] 赋值给array[right] ,随后再从array[right--] 开始与 pivot 比较，若遇到 < pivot 的元素 ,将array[right] 赋值给 array[left] ,重复此步骤直至 left == right , 再将 pivot 的值赋给array[left],至此第一次 partition 完成
代码参考
private static int partitionMethodA(long[] array, int from, int to) { long pivot = array[to]; int left = from; int right = to; while (left < right) { while (left < right && array[left] <= pivot) { left++; } while (left < right && array[right] >= pivot) { right--; } long t = array[left]; array[left] = array[right]; array[right] = t; } long t = array[to]; array[to] = array[left]; array[left] = t; return left; } private static int partitionMethodB(long[] array, int from, int to) { long pivot = array[to]; int left = from; int right = to; while (left < right) { while (left < right && array[left] <= pivot) { right--; } array[right] = array[left]; while (left < right && array[right] >= pivot) { left++; } array[left] = array[right]; } array[left] = pivot; return left; }
