LC912. 排序数组

[HealUP]

理论基础：快速排序是一种常见的排序算法，使用分治的思想来排序一个数组或列表。它的基本思想是选择一个基准数，将数组分成两个部分，一部分是小于基准数的，另一部分是大于等于基准数的，然后再对这两部分递归地进行排序。

好的情况：时间复杂度：nlogn

具体步骤如下：

1. 选择一个基准数（pivot），可以选择第一个数、最后一个数、中间的数或者随机数。
2. 将数组中小于等于基准数的元素放在基准数的左边，大于基准数的元素放在基准数的右边，这一步称为**“划分**”（partition）操作。
3. 对基准数左边的子数组进行递归排序，对基准数右边的子数组进行递归排序，直到每个子数组的长度为 0 或 1，排序完成。

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }
    // 快速排序函数
    public static int[] quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return null;
        }
        int partition = partition(nums, left, right);
        quickSort(nums, left, partition - 1);//在划分位置的左边子区域再划分，直到不可划分left >= right不能进循环条件
        quickSort(nums, partition + 1, right); //在划分位置的右边子区域再划分，直到不可划分left >= right不能进循环条件
        return nums;
    }

    public static int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= pivot) {
                right--;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = pivot; //当前left，right 指向同一个位置了 nums[right] = pivot也行
        return left;// 返回划分的位置
    }
}

缺点：如果输入的数组是基本有序的，快速排序的效率会受到影响，因为快速排序的时间复杂度在最坏情况下是 O(n^2)，即每次划分都只划分出一个子区间。如果输入的数组基本有序，每次划分可能都会划分出极度不平衡的子区间，使得快排退化成冒泡排序。

双轴快排

分析：双轴快排是一种改进的快速排序算法，其基本思想是将待排序数组划分成三个区域：小于基准元素的区域、等于基准元素的区域和大于基准元素的区域。与传统快排相比，双轴快排使用两个轴值，分别从两端扫描数组，将数组划分成三个区域。具体流程如下：

1. 选取两个轴值p和q，p<q，将数组分成左、中、右三个部分，左部分中所有元素均小于p，右部分中所有元素均大于q，中部分中所有元素均介于p和q之间。

2. 对中部分进行递归排序。

3. 对左、右部分进行递归排序。

由于双轴快排采用两个轴值进行划分，因此每次划分可以减少更多的无用比较，从而提高了排序效率。同时，由于其采用了三路划分的思想，可以处理包含大量重复元素的数组。

双轴快排的时间复杂度为O(nlogn)，与传统快排相同，但是实际运行效率更高，尤其是在处理包含大量重复元素的数组时。

class Solution {
    public int[] sortArray(int[] nums) {
        dualPivotQuickSort(nums, 0, nums.length - 1);
        return nums;
    }
    
    private void dualPivotQuickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        if (nums[left] > nums[right]) {
            swap(nums, left, right);
        }
        int pivot1 = nums[left], pivot2 = nums[right];
        int i = left + 1, lt = left + 1, gt = right - 1;
        while (i <= gt) {
            if (nums[i] < pivot1) {
                swap(nums, i++, lt++);
            } else if (nums[i] > pivot2) {
                swap(nums, i, gt--);
            } else {
                i++;
            }
        }
        swap(nums, left, --lt);
        swap(nums, right, ++gt);
        dualPivotQuickSort(nums, left, lt - 1);
        dualPivotQuickSort(nums, lt + 1, gt - 1);
        dualPivotQuickSort(nums, gt + 1, right);
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}