今天来用Java简单实现一个快速排序，首先，针对快速排序里最重要的一个知识：
为什么哨兵位置与初始扫描位置一定要分居左右两侧？
，我们给出形象化的说明
首先，我们正向推导，也就是当哨兵位置为数组最左侧start，两个扫描指针分别是left和right，为什么从right开始可行？
一次快排递归的while循环的退出条件是
l
e
f
t
=
=
r
i
g
h
t
left == right
l
e
f
t
==
r
i
g
h
t
，如果优先进行
n
u
m
s
r
i
g
h
t
>
=
n
u
m
s
s
t
a
r
t
nums_{right}>=nums_{start}
n
u
m
s
r
i
g
h
t
>=
n
u
m
s
s
t
a
r
t
的判断，在达成退出条件时，退出位置一定仅包含以下两种情形：
-
由
ri
g
h
t
right
r
i
g
h
t
向左扫描至
le
f
t
=
=
r
i
g
h
t
left == right
l
e
f
t
==
r
i
g
h
t
，由于未移动的
nu
m
s
l
e
f
t
nums_{left}
n
u
m
s
l
e
f
t
一定满足
nu
m
s
l
e
f
t
<
=
n
u
m
s
s
t
a
r
t
nums_{left}<=nums_{start}
n
u
m
s
l
e
f
t
<=
n
u
m
s
s
t
a
r
t
，因此我们可断言此时终止位置一定小于等于哨兵位置 -
由
le
f
t
left
l
e
f
t
向右扫描至
le
f
t
=
=
r
i
g
h
t
left == right
l
e
f
t
==
r
i
g
h
t
，此时由于
ri
g
h
t
right
r
i
g
h
t
优先扫描，因此
nu
m
s
r
i
g
h
t
nums_{right}
n
u
m
s
r
i
g
h
t
的状态一定满足
nu
m
s
r
i
g
h
t
<
n
u
m
s
s
t
a
r
t
nums_{right}<nums_{start}
n
u
m
s
r
i
g
h
t
<
n
u
m
s
s
t
a
r
t
，我们可断言此时终止位置一定小于哨兵位置
因此，从正向推导的角度，我们可说明哨兵位置与初始扫描位置分居两侧可保证终止位置小于等于哨兵位置。
为证必要性，也可反向推导当位于同一侧时，是无法保证终止位置小于等于哨兵位置的，从而也就无法交换两者
我们给出一个快排的Java实现例：
public void fastSort(int[] nums, int start, int end){//左闭右闭
if(start >= end) return;
int flag = nums[start];
int left = start;
int right = end;
while(left < right){
while(nums[right] >= flag && left < right) {
right--;
}
while(nums[left] <= flag && left < right){
left++;
}
if(left < right){
int[] tmp = nums[right];
nums[right] = nums[left];
nums[left] = tmp;
}
}
int[] tmp = nums[start];
nums[start] = nums[left];
nums[left] = tmp;
fastSort(nums, start, left - 1);
fastSort(nums, left + 1, end);
}
对于二维数组的快排，其原理和上述是一致的，但仍然有一个更好的方法去简单的实践它，即调用Arrays.sort()接口方法，下面给出一种对二维数组进行升序排列**（自定义比较维度）**的写法（假定二维数组的第二维大小为2，首先比较int[0]，相等时比较int[1]）
//int[][] points;
Arrays.sort(points, new Comparator<int[]>(){
@Override //可不带Override，带上更为标准
public int compare(int[]o1, int[] o2){
if(o1[0] == o2[0]) return o1[1] - o2[1];
else return o1[0] - o2[0];
}
});
compare函数的返回值分为以下五类：
return 0:不交换位置，不排序
return 1:交换位置
return -1:不交换位置
return o1-o2:升序排列
return o2-o1:降序排列
PS1: 在使用(1,-1)这一类返回值进行排序时，如果未声明相等时返回0，则会因为比较器无法逆向执行而形成
Comparison method violates its general contract
异常
PS2：在使用o1-o2/o2-o1这一类返回值进行排序时，无需特殊声明大小关系，但可能出现因
超出int类型范围
而产生的值计算错误，从而影响排序结果
这里再分享一个总结较为全面的博客：
Java中实现自定义排序的多种写法