博客

1. 双指针写法

1.1. 我一开始使用的，l = start + 1，

力扣上的提交结果：

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

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

    public static int partition(int[] nums, int start, int end){
        // 经过大量提交测试，发现当l = start + 1
        int l = start + 1, r = end, pivot = nums[start];
        while(l < r){
            while(l < r && nums[r] > pivot) r--;    
            while(l < r && nums[l] <= pivot) l++;
            
            if(l < r) swap(nums, l++, r--);   //这里给l++和r--能够提高效率，如果都没有
            // 则必须给18行或者19行把大于或小于改成大于等于或者小于等于（四选一就能保证算法正常运行）
        }
        if(l == r && nums[r] > pivot) r--;
        swap(nums, start, r);
        return r;
    }

    public static void swap(int[] nums, int i, int j) {
        if(i >= j) return;
        nums[i] += nums[j];
        nums[j] = nums[i] - nums[j];
        nums[i] = nums[i] - nums[j];
    }
}

存疑的话，可以在力扣上测试


https://leetcode-cn.com/leetbook/read/sort-algorithms/eta44r/

1.2 或者下面这个，l = start，一般写法

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

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

    public static int partition(int[] nums, int start, int end){
        int l = start, r = end, pivot = nums[start];
        while(l < r){
            while(l < r && nums[r] >= pivot) r--;
            while(l < r && nums[l] <= pivot) l++;
            
            if(l < r) swap(nums, l, r);
        }
        // if(l == r && nums[r] > pivot) r--;
        swap(nums, start, r);
        return r;
    }

    public static void swap(int[] nums, int i, int j) {
        if(i >= j) return;
        nums[i] += nums[j];
        nums[j] = nums[i] - nums[j];
        nums[i] = nums[i] - nums[j];
    }
}

2. 最简单的分区算法

分区思路：从 left 开始，遇到比基数大的数，就交换到数组最后，并将 right 减一，直到 left 和 right 相遇，此时数组就被分成了左右两个区域。再将基数和中间的数交换，返回中间值的下标即可。

力扣上提交结果显示该算法：

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

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

    public static int partition(int[] nums, int start, int end){
        int l = start + 1, r = end, pivot = nums[start];
        while(l < r){
            while(l < r && nums[l] <= pivot) l++;
            if(l != r) swap(nums, l, r--);
        }
        if(l == r && nums[r] > pivot) r--;
        if(start != r) swap(nums, start, r);
        return r;
    }

    public static void swap(int[] nums, int i, int j) {
        if(i == j) return;
        nums[i] += nums[j];
        nums[j] = nums[i] - nums[j];
        nums[i] = nums[i] - nums[j];
    }
}

当然，快排还有很多优化后的方法，读者可以自行搜索并实现。抛砖喽！