快排的3种实现方式

本文循序渐进的总结一下：单路、双路和三路，三种快排实现方式。大家可以去912. 排序数组验证自己代码的正确性。

单路快排

思路：以p = arr[right]作为基准值，指针i = left表示第一个大于等于基准值的下标，指针j = left

• 如果arr[j] < p，交换index和p处的值，i++且j++
• 否则j++，i不变
• 跳出循环后，交换right和i处的值即可。

注：这里选择arr[right]作为基准值很重要，如果选择arr[left]作为基准值，当所有元素都小于基准值时就比较麻烦。

下面是java的简单实现：

public void quickSort(int[] nums, int left, int right){
    if(left >= right) return;
    //终点和随机位置交换值
    int temp = rand.nextInt(left, right+1);
    swap(nums, right, temp);
    int i = left, j = left, p = nums[right];
    while(j < right){
        if(nums[j] < p){
            swap(nums, i, j);
            i++;
        }
        j++;
    }
    //交换i和right处的值，这样[left, i-1]都是小于p的值，[i+1, right]都是大于等于p的值
    swap(nums, i, right);
    quickSort(nums, left, i-1);
    quickSort(nums, i+1, right);
}

双路快排

思路：以p=arr[left]作为基准值，i = left， j= right

• 如果i < j && arr[j] >= p，重复j--

  注：第一步必须先让j走，否则如果所有元素都小于等于p，就会出错。

• 如果i < j && arr[i] <= p，重复i++

• 交换i和j处的值，重复上述步骤

• 跳出循环后，交换left和i处的值即可。

注：上面第1、2步中都带等号，即<=和>=，这样可以让基准值在两边分布均匀。

下面是java的简单实现：

public void quickSort(int[] nums, int left, int right){
    if(left >= right) return;
    //起点和随机位置交换值
    int temp = rand.nextInt(left, right+1);
    swap(nums, left, temp);
    int i = left, j = right, p = nums[left];
    while(i < j){
        //先让j走
        while(i < j && nums[j] >= p) --j;
        while(i < j && nums[i] <= p) ++i;
        swap(nums, i, j);
    }
    //交换i和left处的值，这样[left, i-1]都是小于p的值，[i+1, right]都是大于等于p的值
    swap(nums, i, left);
    quickSort(nums, left, i-1);
    quickSort(nums, i+1, right);
}

三路快排

思路：以p = arr[left]作为基准值，i = left作为左侧存放小于基准值元素的位置，j = right + 1作为右侧存放大于基准值元素的位置，index = left + 1遍历所有元素。

• 如果arr[index] < p，交换i+1和index处的值，i++，index++

• 如果arr[index] > p，交换j-1和index处的值，j--

• 否则，index++

• 跳出循环后，交换left和i处的值即可

下面是java的简单实现：

public void quickSort(int[] nums, int left, int right){
    if(left >= right) return;
    //起点和随机位置交换值
    int temp = rand.nextInt(left, right);
    swap(nums, left, temp);
    int i = left, j = right+1, index = left + 1, p = nums[left];
    while(index < j){
        if(nums[index] < p){
            swap(nums, i + 1, index);
            i++;
            index++;
        }else if(nums[index] > p){
            swap(nums, j - 1, index);
            j--;
        }else{
            index++;
        }
    }
    //交换i和left处的值，这样[left, i-1]都是小于p的值，[j, right]都是大于p的值
    swap(nums, i, left);
    quickSort(nums, left, i-1);
    quickSort(nums, j, right);
}

打赏