LeetCode.912.Sort an Array 排序数组

题目描述

912 Sort an Array
https://leetcode-cn.com/problems/sort-an-array/

Given an array of integers nums, sort the array in ascending order.

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

Constraints:
1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000

---

解题过程

这道题的目的应该是让系统的复习排序算法。

快速排序

写了下快速排序，实现了3中枢轴选择策略：
1、每次选择最左边的
2、随机
3、left, mid ,right 三者选中

根据提交OJ运行的结果，还是最简单的选最左边第一个元素做枢轴速度最快。

快速排序平均时间复杂度 O(nlogn)，空间复杂度 log(n)，不稳定

private static class SolutionV2020 {
    public int[] sortArray(int[] nums) {
        if (null == nums || nums.length < 2) {
            return nums;
        }
        qsort(nums, 0, nums.length - 1);
        return nums;
    }

    private void qsort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int location = partition(nums, left, right);
        qsort(nums, left, location - 1);
        qsort(nums, location + 1, right);
    }

    private int partition(int[] nums, int left, int right) {
        // 从nums[left,...,right]中随机找一个数放到 left 下标的位置
//            randomFirst(nums, left, right);
        // 找 left,mid,right 中间的数放到 left 下标的位置
        middleFirst(nums, left, 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;
        return left;
    }

    // 从nums[left,...,right]中随机找一个数放到 left 下标的位置
    private void randomFirst(int[] nums, int left, int right) {
        int randomIndex = left + (int)(Math.random() * (right - left));
        int temp = nums[randomIndex];
        nums[randomIndex] = nums[left];
        nums[left] = temp;
    }

    // 找 left,mid,right 中间的数放到 left 下标的位置
    private void middleFirst(int[] nums, int left, int right) {
        if (right - left < 2) { // 小于3个元素
            return;
        }
        int mid = (left + right) / 2;
        int min = Math.min(nums[left], Math.min(nums[mid], nums[right]));
        int max = Math.max(nums[left], Math.max(nums[mid], nums[right]));
        if (nums[left] != max && nums[left] != min) {
            // nums[left] 就是中间元素
            return;
        }
        int midIndex; // 中间值的下标
        if (nums[left] == min) {
            midIndex = nums[mid] < nums[right] ? mid : right;
        } else { // nums[left]==max
            midIndex = nums[mid] > nums[right] ? mid : right;
        }
        int temp = nums[midIndex];
        nums[midIndex] = nums[left];
        nums[left] = temp;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_912_SortAnArray.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_912_SortAnArray.java

---