leetcode - [912] Sort an Array

2020/07/15

问题描述

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

将数组升序排列。

举个例子:

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

拿这道题来复习下Y总快排归并的板子。

解法1 - 快速排序

来看下实现:

class Solution {
    
    private void quickSort(int[] a, int l, int r){
        if (l >= r) return;
        
        int t = a[(l + r) >>> 1];
        int i = l - 1;
        int j = r + 1;
        while (i < j){
            while (a[++i] < t);
            while (a[--j] > t);
            if (i < j) {
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        }
        quickSort(a, l, j);
        quickSort(a, j + 1, r);
    }
    
    public int[] sortArray(int[] nums) {        
        int n = nums.length;
        quickSort(nums, 0, n - 1);
        return nums;
    }
}

Enjoy it !

解法2 - 归并排序

来看下实现:

class Solution {
    
    private void mergeSort(int[] a, int l, int r){
        if (l >= r) return;
        
        int mid = (l + r) >>> 1;
        mergeSort(a, l, mid);
        mergeSort(a, mid + 1, r);
        
        int k = 0, i = l, j = mid + 1;
        int[] tmp = new int[r - l + 1];
        while (i <= mid && j <= r){
            if (a[i] <= a[j]) tmp[k++] = a[i++];
            else tmp[k++] = a[j++];
        }
        while (i <= mid) tmp[k++] = a[i++];
        while (j <= r)   tmp[k++] = a[j++];
        for (int m = l, n = 0; m <= r; m++, n++){
            a[m] = tmp[n];
        }
    }
    
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        mergeSort(nums, 0, n - 1);
        return nums;
    }
}

Enjoy it !


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory