<>快速排序&&荷兰国旗&&

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++;
        }
    }
}

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};
}