一.partition操作
代码语言：javascript复制private void swap(int[] array,int i ,int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public void partition(int [] array,int left ,int right,int num){
int less = left - 1;
int more = right 1;
int cur = left;
while (cur < more){
if (array[cur] < num){
swap(array,cur , less);
}else if (array[cur] > num){
swap(array,cur,--more);
}else {
cur ;
}
}
}小于区域推着等于区域往右跑，但是等于区域与大于区域之间有一个待定的区域，所以array[cur]< num时候cur ，所以array[cur] > num时候cur不用加一。
初始状态：
执行状态：
二.经典快速排序和随机快排
代码语言：javascript复制public void quickSort(int[] array,int left ,int right){
if (right <= left) return;
// 让数组中的一个随机位置的数字与数组中的最后的一个数字交换，这一个语句就是随机快排的核心，可以有效的加速
//近似有序的数组的排序
swap(array,left new Random().nextInt(right - left 1) ,right);
int[] p = partition(array,left,right);
quickSort(array,left,p[0]-1);
quickSort(array,p[1] 1,right);
}
public int [] partition(int [] array,int left ,int right){
int less = left - 1;
// 因为这里的数组中的最后一个数字作为了num，所以这里的more初始化应该为right，而不再是right 1;
int more = right;
int cur = left;
while (cur < more){
if (array[cur] < array[right]){
swap(array,cur , less);
}else if (array[cur] > array[right]){
swap(array,cur,--more);
}else {
cur ;
}
}
//这里选择数组中的最后一个数字作为比较的num,所以在最后需要将这个数字与more位置的数字交换。
swap(array,more,right);
//由于more与最后一个数字交换，说明more是等于num的最后一个数字，因此，等于num的下标范围是 less 1 .. more
// 这就是为什么不是more-1的原因
return new int[]{less 1,more};
}这里选择数组中的最后一个数字作为比较的num,所在最后需要将这个数字与more位置的数字交换。
每次返回的是等于这个数字的的起始和终点的位置。
