快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
基本思想
1.在一列数组中取一个数作为基数
2.分区过程，先从右边开始小于这个基数的值放在左边，在从左边开始把大于基数的值放入右边
3.递归基数左边和右边区间重复第二部，直到只有一个值结束
图解
初始值
image
右边找小于基数的数值
- 挖坑，因为我们要交换位置所以要挖一个坑出来
image
-
把基数放入到坑中我们这里选6位基数，然后在右边找数填左边的坑。
image 右边开始找找到3比基数6小，交换它们的位置。
image
左边找大于基数的数值
- 左边开始找到了7大于基数的数字，交换位置后的值。
image
重复以上步骤，知道i和j相等的时候结束第一次排序
- 分区排序完后的值
image
static void quick(int s[], int l, int r) {
//保证区间起码有一位数
if (l < r) {
int i = l;
int j = r;
int x = s[l];
//i<j保证 left的i和right的j不会重合
while (i < j) {
//找小于等于x的数,如果是大于就j--继续往前走。
while (i < j && s[j] >= x) {
j--;
}
if (i < j) {
s[i] = s[j];
}
//找大于等于x的数，如果小于就i++继续往前走
while (i < j && s[i] <= x) {
i++;
}
if (i < j) {
s[j] = s[i];
}
}
s[i] = x;
quick(s, l, i - 1);
quick(s, i + 1, r);
}
}
public static void main(String[] args) {
int[] array = new int[]{9, 6, 8, 7, 1, 100, 3, 2, 0, 14};
quick(array, 0, array.length - 1);
for (int i : array) {
System.out.println(i);
}
}
