912.sort_an_array.md

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 <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104

相关企业

字节跳动|7

亚马逊 Amazon|6

微软 Microsoft|2

苹果 Apple|2

百度|2

相关标签

• Array
• Divide and Conquer
• Bucket Sort
• Counting Sort
• Radix Sort
• Sorting
• Heap (Priority Queue)
• Merge Sort

note

check ../note/quick_sort_merge_sort_note.md

solution - quick sort

• 三个要注意的点 看三个注释的地方：
• pivot建议选中点
• left和right比较是总是<=。 一共四个地方。
• A[]和pivot比较时总是<。一共两个地方。

class Solution {
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length == 0){
            return nums;
        }

        return quicksort(nums, 0, nums.length-1);
    }

    private int[] quicksort(int[] A, int start, int end){
        if (start >= end){
            return A;
        }

        int left = start;
        int right = end;
        int pivot = A[(start + end) / 2]; // is better than A[start] or A[end]; is worse than random() but expensive

        // not < (stackoverflow), but <=
        while (left <= right){
            while (left <= right && A[left] < pivot){ // must < cannot <=. bc those are for swap, == don't need swap.
                left ++;
            }
            while (left <= right && A[right] > pivot){ // must > cannot >=
                right --;
            }

            if (left <= right){
                int temp = A[left];
                A[left] = A[right];
                A[right] = temp;
                left ++;
                right --;
            }
        }

        quicksort(A, start, right);
        quicksort(A, left, end);

        return A;
    }
}

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if not nums:
            return nums
        

        return self.quicksort(nums, 0, len(nums)-1)

    def quicksort(self, nums, start: int, end: int):
        if start >= end:
            return nums


        
        left, right = start, end
        pivotvalue = nums[int((start + end) / 2)]

        while (left <= right):
            while left <= right and nums[left] < pivotvalue:
                left += 1
            while left <= right and nums[right] > pivotvalue:
                right -= 1

            if left <= right:
                temp = nums[left]
                nums[left] = nums[right]
                nums[right]= temp
                left += 1
                right -= 1


        self.quicksort(nums, start, right)
        self.quicksort(nums, left, end)

        return nums

solution - merge sort

class Solution {
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length == 0){
            return nums;
        }

        int[] temp = new int[nums.length];
        return mergesort(nums, 0, nums.length-1, temp); 
    }

    private int[] mergesort(int[] A, int start, int end, int[] temp){
        if (start >= end){
            return A;
        }

        mergesort(A, start, (start + end) / 2, temp);
        mergesort(A, (start + end) / 2 + 1, end, temp);
        merge(A, start, end, temp);
        return A;
    } 

    private void merge(int[] A, int start, int end, int[] temp){
        int middle = (start + end) / 2;
        int leftindex = start;
        int rightindex = middle + 1;
        int tempindex = leftindex;

        while (leftindex <= middle && rightindex <= end){
            if (A[leftindex] < A[rightindex]){
                temp[tempindex++] = A[leftindex++];
            }else{
                temp[tempindex++] = A[rightindex++];
            }
        }

        while (leftindex <= middle){
            temp[tempindex++] = A[leftindex++];
        }
        while (rightindex <= end){
            temp[tempindex++] = A[rightindex++];
        }

        for (int i = 0; i <= end; i++){
            A[i] = temp[i];
        }
    }
}