基本思想：（分治）
- 先从数列中取出一个数作为key值；
- 将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
- 对左右两个小数列重复第二步，直至各区间只有1个数。
时间复杂度nlogn，不稳定
实现
快排的实现我们一般习惯分为主函数Sort和partition函数。partition函数将选取一个key，并将数组中小于key的和大于key的以key分割开来，并返回key的下标。
Sort函数
public static void sort(int[] arr, int begin, int end) {
if (end <= begin) return;
int middle = partition(arr, begin, end); //
sort(arr, begin, middle - 1);
sort(arr, middle + 1, end);
}
以下是三种partition策略：
一趟Partition 这是三种partition策略最方便的，类似于插入排序，将小于key的插入，记录小于key的最后一个值的下标，最后将key插入进去。
// 一趟插入法
public static int partition(int[] arr, int begin, int end) {
int key = arr[end]; // 将最后一个元素做为KEY
int location = begin; //指向小于key的末尾
for (int i = begin; i < end; i++) {
if (arr[i] < key)
swap(arr, location++, i);
}
swap(arr, location, end);
return location;
}
填坑法 可以理解为begin和end向中间靠拢填坑，最后空出来的坑用key填
// 挖坑法
public static int partition(int[] arr, int begin, int end) {
int key = arr[begin]; // 轴，此时begin位置是一个坑
while (begin < end) {
while (begin < end && key < arr[end]) end--;
arr[begin] = arr[end]; //填begin坑,此时end出现新的坑
while (begin < end && key > arr[begin]) begin++;
arr[end] = arr[begin]; // 填end坑，此时begin出现新的坑
}
// begin == end ,用key来填坑
arr[begin] = key;
return begin;
}
左右互搏（置换）法 从前向后找一个大于key的，从后先前找一个小于key的，置换一下。最后将key放进去
// 相互置换法
public static int partition(int[] arr, int begin, int end) {
int index = begin;// 记录begin初始值
int key = arr[begin++]; // 轴
while (begin < end) {
while (begin < end && arr[begin] < key) begin++;
while (begin < end && arr[end] > key) end--;
if (begin < end)
swap(arr, begin, end);// 置换
}
// 这里存在一个问题，最后begin和end指向的内容和key的大小关系需要判断一下。
if (arr[begin] < key) swap(arr, index, begin);
else swap(arr, index, --begin);
return begin;
}
