LeetCode 912. 排序数组

题目

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

详见：912. 排序数组

思路

排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序，若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。

排序算法就是指通过特定的算法因式将一组或多组数据按照既定模式进行重新排序，这种新序列遵循着一定的规则，体现出一定的规律，因此，经处理后的数据便于筛选和计算，大大提高了计算效率。

1. 冒泡排序：多次遍历数组，每次比较相邻的两个元素，如果顺序错误则交换。排序过程中，大的元素会移动到数组的末尾
2. 选择排序：多次遍历数组，每次在未排序的子数组中找到最小元素，将其与该子数组中的首个元素交换。如果未排序的子数组中的最小元素与首个元素相等，则不执行交换操作
3. 快速排序：随机选择一个中间值pivot作为比较的基准，因此比这个基准小的放到左边，比这个基准大的放到右边
4. Arrays.sort()方法：使用时间复杂度为O(nlogn)的API排序

代码

方法一：冒泡排序

class Solution {
    public int[] sortArray(int[] nums) {
        boolean needNextPass = true;
        int length = nums.length;
        for (int i = 1; i < length && needNextPass; i++) {
            needNextPass = false;
            for (int j = 0; j < length - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                    needNextPass = true;
                }
            }
        }
        return nums;
    }
}

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

方法二：选择排序

class Solution {
    public int[] sortArray(int[] nums) {
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            int currMinIndex = i;
            for (int j = i + 1; j < length; j++) {
                if (nums[j] < nums[currMinIndex]) {
                    currMinIndex = j;
                }
            }
            if (currMinIndex != i) {
                int temp = nums[i];
                nums[i] = nums[currMinIndex];
                nums[currMinIndex] = temp;
            }
        }
        return nums;
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)

方法三：快速排序

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

    private void quickSort(int[] nums, int low, int high){
        if(low < high){
            int mid = partition(nums, low, high);
            quickSort(nums, low, mid - 1);
            quickSort(nums, mid + 1, high);
        }
    }

    private int partition(int[] nums, int low, int high){
        int pivot = low + (int) (Math.random() * (high - low + 1));
        swap(nums, pivot, low);
        int i = low, j = low + 1;
        while (j <= high){
            if(nums[j] < nums[low]){
                swap(nums, j, ++i);
            }
            j++;
        }
        swap(nums, low, i);
        return i;
    }

    private void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

• 时间复杂度：O(nlogn)
• 空间复杂度：O(logn)

方法四：Arrays.sort()

class Solution {
    public int[] sortArray(int[] nums) {
        Arrays.sort(nums);
        return nums;
    }
}

• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)