快速排序

复习一下快速排序

双指针快排

public int[] sortArray(int[] nums){
    int len = nums.length;
    quickSort(nums,0,len-1);
    return nums;
}

private void quickSort(int[] nums,int start,int end){
    if(start >= end)
        return;
    int index = partition(nums,start,end);
    quickSort(nums,start,index-1);
    quickSort(nums,index+1,end);
}

private int partition(int[] nums, int start, int end) {
    //随机选取一个数作为划分点
    int random = new Random().nextInt(end - start + 1) + start;
    swap(nums,start,random);

    int pivot = nums[start];  //基准值
    int left = start+1,right = end;
    while(true){
        while (left <= end && nums[left] <= pivot)
            left++;
        while (start <= right && nums[right] > pivot)
            right--;
        if(left >= right)
            break;
        swap(nums,left,right);  //交换左右两个指针
        left++;
        right--;
    }
    nums[start] = nums[right];
    nums[right] = pivot;
    return right;
}

private void swap(int[] nums, int index1, int index2) {
    int temp = nums[index1];
    nums[index1] = nums[index2];
    nums[index2] = temp;
}

三指针

来源weiwei

private static final Random RANDOM = new Random();

public int[] sortArray(int[] nums) {
    int len = nums.length;
    quickSort(nums, 0, len - 1);
    return nums;
}

private void quickSort(int[] nums, int left, int right) {

    if(left >= right)
        return;

    int randomIndex = left + RANDOM.nextInt(right - left + 1);
    swap(nums, randomIndex, left);

    // 循环不变量：
    // all in [left + 1, lt] < pivot
    // all in [lt + 1, i) = pivot
    // all in [gt, right] > pivot
    int pivot = nums[left];
    int lt = left;
    int gt = right + 1;

    int i = left + 1;
    while (i < gt) {
        if (nums[i] < pivot) {
            lt++;
            swap(nums, i, lt);
            i++;
        } else if (nums[i] == pivot) {
            i++;
        } else {
            gt--;
            swap(nums, i, gt);
        }
    }
    swap(nums, left, lt);
    // 注意这里，大大减少了两侧分治的区间
    quickSort(nums, left, lt - 1);
    quickSort(nums, gt, right);
}


private void swap(int[] nums, int index1, int index2) {
    int temp = nums[index1];
    nums[index1] = nums[index2];
    nums[index2] = temp;
}