快速排序.gif
原理
通常是以第一个元素为基准元素开始，然后从头部和尾部开始遍历，左边都是比基准元素小，右边是比基准元素大。
其中一次快排的过程：
- 设置两个变量begin、end，将第一个元素作为基准值。
- 由end开始向前搜索(j--)，遇到arr[j] < 基准值，将arr[j]和此时的a[i] 替换
- 由begin开始向后搜索(i++)，遇到arr[i] > 基准值，将a[i]和a[j]替换
- 重试2、3步骤，直到i = j。
缺点
不稳定。 快速排序的执行时间与排列顺序及基准值的选取有关。例如，
int[] arr = new int[]{1,2,3,4,5,6,7,8} 。按照快速排列的算法来，必须要经过
n-1趟才能完成，也就是T(n)=n(n-1)/2约等 O(n2/2)。
最好的情况，是每趟排序将数组分成长度相近的两个子数组，时间复杂度为O(n*logn).
空间复杂度O(logn),最坏的空间复杂度O(n),平均O(logn)。
代码实现
public static void quickSort(int[] arr, int begin, int end) {
int i = begin, j = end;
int vot = arr[i]; //第一个值作为基准值
while (i < j) {
while (i < j && vot < arr[j]) {
//从后向前寻找比基准值小的元素
j--;
}
while (i < j && arr[i] < vot) {
//从前向后寻找比基准值大的元素
i++;
}
//如果前后指针碰撞
if (arr[i] == arr[j] && i < j) {
i++;
} else {
//替换元素
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
//遍历替换完成后，左边为比基准小的元素，右边为比基准大的元素，然后递归
if (i - 1 > begin) {
quickSort(arr, begin, i - 1);
}
if (j + 1 < end) {
quickSort(arr, j + 1, end);
}
}
