leetcode912-排序数组

原题

给定一个整数数组 nums,将该数组升序排列。

示例 1:

输入: [5,2,3,1] 输出: [1,2,3,5]

示例 2:

输入: [5,1,1,2,0,0] 输出: [0,0,1,1,2,5]

提示:

  1. 1 <= A.length <= 10000
  2. -50000 <= A[i] <= 50000

解法

思想

经典排序问题,解法见十大排序算法与Java实现

代码

计数排序:

class Solution {
    public int[] sortArray(int[] nums) {
        int[] occur = new int[100001];
        for(int num:nums){
            occur[num+50000]++;
        }
        int index = 0;
        for(int i = 0;i<100001;i++){
            if(occur[i]!=0){
                for(int n = 0 ; n < occur[i];n++){
                    nums[index] = i-50000;
                    index++;
                }
            }
        }
        return nums;
    }
}

快速排序,这里每次选取中轴元素都是选取的第一个元素:

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

    private int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            //获取中轴元素所处的位置
            int mid = partition(arr, left, right);
            //进行分割
            arr = quickSort(arr, left, mid - 1);
            arr = quickSort(arr, mid + 1, right);
        }
        return arr;
    }

    private int partition(int[] arr, int left, int right) {
        //选取中轴元素
        int pivot = arr[left];
        int i = left + 1;
        int j = right;
        while (true) {
            // 向右找到第一个小于等于 pivot 的元素位置
            while (i <= j && arr[i] <= pivot) i++;
            // 向左找到第一个大于等于 pivot 的元素位置
            while(i <= j && arr[j] >= pivot ) j--;
            if(i >= j)
                break;
            //交换两个元素的位置,使得左边的元素不大于pivot,右边的不小于pivot
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        arr[left] = arr[j];
        // 使中轴元素处于有序的位置
        arr[j] = pivot;
        return j;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode912-%e6%8e%92%e5%ba%8f%e6%95%b0%e7%bb%84/

发表回复

登录后才能评论