LeetCode——912. 排序数组

• 一、题目描述
• • 1.1 示例
  • • 示例1
    • 示例2
  • 1.2 提示
• 二、题目分析
• • 2.1 题目标签：快速排序，分治
  • 2.2 解题思路—分治思想
• 三、题解——Java

给你一个整数数组 nums，请你将该数组升序排列。

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

• 1 <= nums.length <= 50000
• -50000 <= nums[i] <= 50000

• 分支的三个步骤：Divide(分割)、Conquer(求解)、Combine(组合)；
• 利用分治的思想，每一趟排序将待排序列分割成两部分，通过选取基准 pivot 使得一部分的值都不大于另一部分的值，之后再分别递归处理这两个部分，以达到整个序列有序；

1. 选取基准 pivot 的方式有很多种，对于分治算法，若每次划分的两个子序列长度相等时，那么分治算法效率会达到最大。也就是说，基准 pivot 的选择是很重要的，选择基准的方式决定了分割后两个子序列的长度，进而对整个算法的效率产生决定性影响。可以选取位于序列中间的元素 arrays[left + (right - left) / 2] 作为基准；
2. 通过 while 循环进行一趟划分，利用双指针依次从左至右、从右至左遍历，直至 nums[i] >= nums[pivot] 以及 nums[j] <= nums[pivot] 为止。若nums[i] >= nums[j] 则互换二者的位置，从而保证本趟划分的有序性，继续循环上述操作直至 i >= j 为止；
3. 通过递归调用排序函数处理左、右子区间 nums[l, j] 和 nums[j+1, r]；
4. 因为当“求解”步骤中的两个递归调用结束时，其左、右两个子区间已经有序。对快速排序而言，"组合"步骤无须任何操作；

• 时间复杂度：O(nlog₂ⁿ)。

class Solution {
    public int[] sortArray(int[] nums) {
        quick_sort(nums, 0, nums.length-1);
        return nums;
    }
    void quick_sort(int[] nums, int l, int r) {
        if(l >= r) return;
		
        int i = l - 1, j = r + 1, x = nums[l + (r - l) / 2];
        while(i < j) {
            do i++; while(nums[i] < x);
            do j--; while(nums[j] > x);
            if(i < j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        quick_sort(nums, l, j);
        quick_sort(nums, j + 1, r);
    }
}