【Day 36 】2021-10-15 - 912. 排序数组

[azl397985856]

912. 排序数组

入选理由

暂无

题目地址

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

前置知识

• 数组
• 排序

  题目描述

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

 

示例 1：

输入：nums = [5,2,3,1] 输出：[1,2,3,5] 示例 2：

输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5]  

提示：

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

[last-Battle]

思路

关键点

• 先写一个插入排序

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        for (int i = 1; i < nums.size(); ++i) {
            int j = i;
            auto tmp = nums[j];
            for (; j > 0 && tmp < nums[j - 1]; --j) {
                nums[j] = nums[j - 1];
            }
            nums[j] = tmp;
        }

        return nums;
    }
};

复杂度分析

令 n 为数组长度。

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

[yanglr]

思路

需要用排序方法解决, 就当是复习各种排序算法吧。

O(n^2)复杂度的算法就不写了, 应该是无法AC的。下面主要实现时间复杂度为O(N logN) 和 O(N)的。

方法1: 调用sort函数

代码

实现语言: C++

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums;
    }
};

复杂度分析

• 时间复杂度：O(N logN), 其中N为数组长度
• 空间复杂度：O(1)

方法2: 快速排序

代码

实现语言: C++

const int N = 2e5 + 10;   
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        const int len = nums.size();
        quickSort(nums, 0, len - 1);
        return nums;
    }
    void quickSort(vector<int>& A, int l, int r)
    {
        if (l >= r) return;
        int x = A[(l+r)/2];  // 分界点取中间点比较保险, 因为有时会遇到最坏的情形(极度散乱, 熵最大时)~
        int i = l - 1, j = r + 1;  /* 每次交换完之后, 向中间一定1位 */
        // 双指针
        while (i < j)
        {
            i++;
            while (A[i] < x) i++;
            j--;
            while (A[j] > x) j--;
            if (i < j) swap(A[i], A[j]);
        }
        // 递归处理左侧
        quickSort(A, l, j);
        // 递归处理右侧
        quickSort(A, j+1, r);
    }    
};

复杂度分析

• 时间复杂度：O(N logN), 其中N为数组长度
• 空间复杂度：O(1)

方法3: 归并排序

代码

实现语言: C++

const int N = 2e5 + 10;
int A[N], tmp[N];   
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        const int len = nums.size();
        mergeSort(nums, 0, len - 1);
        return nums;
    }
    void mergeSort(vector<int>& A, int l, int r)
    {
        if (l >= r) return;

        int mid = (l+r)/2;
        mergeSort(A, l, mid);
        mergeSort(A, mid+1, r);
        int i = l, j = mid+1, k=0;
        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 i=l, j=0; i <= r; i++, j++) A[i] = tmp[j];
    }    
};

复杂度分析

• 时间复杂度：O(N logN), 其中N为数组长度
• 空间复杂度：O(N)

方法4: 计数排序

数组模拟计数的哈希表: 分桶计数, 空间换时间。

代码

实现语言: C++

const int N = 5e4;   
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        vector<int> dict(2*N + 1, 0); // dict[id]: value -> count
        vector<int> res;
        for (auto& num : nums)
            dict[num + N]++;
        for (int i = 0; i < dict.size(); i++)
        {
            while (dict[i] > 0)
            {
                res.push_back(i - N);
                dict[i]--;
            }
        }
        return res;
    }    
};

复杂度分析

• 时间复杂度：O(N), 其中N为数组长度
• 空间复杂度：O(N)

[yachtcoder]

Merge sort. O(nlgn), O(n)

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def merge(l1, l2):
            p1, p2, ret = 0, 0, []
            while p1 < len(l1) and p2 < len(l2):
                if l1[p1] <= l2[p2]:
                    ret.append(l1[p1])
                    p1 += 1
                else:
                    ret.append(l2[p2])
                    p2 += 1
            if p1 < len(l1): ret += l1[p1:]
            if p2 < len(l2): ret += l2[p2:]
            return ret

        def merge_sort(arr, l, r):
            if l == r: return [arr[l]]
            if l + 1 == r:
                return [min(arr[l], arr[r]), max(arr[l], arr[r])]
            half = (l+r)//2
            l1 = merge_sort(arr, l, half)
            l2 = merge_sort(arr, half+1, r)
            ret = merge(l1, l2)
            return ret
        return merge_sort(nums, 0, len(nums)-1)

[wangcn111]

var rotateRight = function (head, k) {
  if (!head || !head.next) return head;
  let count = 0,
    now = head;
  while (now) {
    now = now.next;
    count++;
  }
  k = k % count;
  let slow = (fast = head);
  while (fast.next) {
    if (k-- <= 0) {
      slow = slow.next;
    }
    fast = fast.next;
  }
  fast.next = head;
  let res = slow.next;
  slow.next = null;
  return res;
};

[JiangyanLiNEU]

Merge Sort

• Runtime = O(nlogn), space = O(n)

  var sortArray = function(nums) {
  
  if (nums.length <= 1) return nums
  
  let mid = Math.floor((1+nums.length) / 2);
  let arr1 = sortArray(nums.slice(0, mid));
  let arr2 = sortArray(nums.slice(mid));
  
  let result = [];
  while (arr1 || arr2){
      if (!arr1){
          result.push(arr2.shift());
      }else if (!arr2){
          result.push(arr1.shift());
      }else{
          if (arr1[0]<=arr2[0]){
              result.push(arr1.shift());
          }else{
              result.push(arr2.shift());
          };
      };
  };
  return result;
  };

[leo173701]

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

[cicihou]

merge sort

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

        def merge_sort(l):
            if len(l) <= 1:
                return l
            i = len(l) // 2
            left = merge_sort(l[:i])
            right = merge_sort(l[i:])
            return merge(left, right)

        def merge(left, right):
            l, r = 0, 0
            res = []
            while l < len(left) and r < len(right):
                if left[l] <= right[r]:
                    res.append(left[l])
                    l += 1
                else:
                    res.append(right[r])
                    r += 1
            res += left[l:] or right[r:]
            return res

        return merge_sort(nums)

[james20141606]

Day 36: 912. Sort an Array (sort, array, divide and conquer, heap(priority queue), merge sort, bucket sort, radix sort, counting sort)

• Problem Link

  • 912. Sort an Array

• Ideas

  • We recursively use merge sort to sort the divided subarray. And then we could linearly merge the two subarray using two pointers. Time complexity: $T(n)=2 T\left(\frac{n}{2}\right)+O(n)$, we have O(NlogN). Space complexity: O(logN+N)

• Complexity: hash table and bucket

  • Time: O(NlogN)
  • Space: O(logN+N)

• Code

class Solution:
    def merge_sort(self, nums, l, r):
        if l == r:
            return
        mid = (l + r) // 2
        self.merge_sort(nums, l, mid)
        self.merge_sort(nums, mid + 1, r)
        tmp = []
        i, j = l, mid + 1 #i,j in the first and second half
        while i <= mid or j <= r:
            #append the smaller value of nums[j] and nums[i], move pointers to the next position
            if i > mid or (j <= r and nums[j] < nums[i]):
                tmp.append(nums[j])
                j += 1
            else:
                tmp.append(nums[i])
                i += 1
        nums[l: r + 1] = tmp
        #we modifiy the l:r+1 region in nums, replace by tmp

    def sortArray(self, nums: List[int]) -> List[int]:
        self.merge_sort(nums, 0, len(nums) - 1)
        return nums

• other resources:
  • https://leetcode-cn.com/problems/sort-an-array/solution/pai-xu-shu-zu-by-leetcode-solution/

[jiabin123]

思路：MergeSort

class Solution {
    public int[] sortArray(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        sortIt(nums,left,right);
        return nums;
    }
    private void sortIt(int arr[],int left, int right){

        if (left<right){
        int middle = left + (right-left)/2;

        sortIt(arr,left,middle);
        sortIt(arr,middle+1,right);

        merge(arr,left,middle,right);
        }
    }

    private void merge(int[] arr, int left , int middle, int right){
        int n1 = middle-left+1;
        int n2 = right - middle;

        int[] L = new int[n1];
        int[] R = new int[n2];
        for (int i = 0; i < n1; i++){
        L[i] = arr[left+i];
        }
        for (int j = 0; j < n2; j++){
        R[j] = arr[middle+j+1];
        }

        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2){
        if (L[i] <= R[j]){
            arr[k] = L[i];
            i++;
        }else{
            arr[k] = R[j];
            j++;
        }
        k++;
        }

        while (i < n1){
        arr[k] = L[i];
        i++;
        k++;
        }
        while (j<n2){
        arr[k] = R[j];
        j++;
        k++;
        }

    }

}

时间复杂度: O(NlogN)

空间复杂度: O(N)

[RonghuanYou]

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if nums is None or len(nums) == 0:
            return

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

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

        left = start
        right = end

        pivot = nums[(start + end) // 2]

        while left <= right:
            while left <= right and nums[left] < pivot:
                left += 1
            while left <= right and nums[right] > pivot:
                right -= 1

            if left <= right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
        self.quickSort(nums, start, right)
        self.quickSort(nums, left, end)

[comst007]

912. 排序数组

---

思路

快排

代码

• C++

class Solution {
public:
    void qsort(vector<int>& nums, int ll, int rr){
        if(ll >= rr) return;

         int ii, jj;
         int pivot;
         ii = ll - 1; 
         jj = rr + 1;
         pivot = nums[ll + rr >> 1];
         while(ii < jj){
            while(nums[++ii] < pivot) ;
            while(nums[--jj] > pivot) ;
            if(ii < jj){
                swap(nums[ii], nums[jj]);
            }

        }
        qsort(nums, ll, jj);
        qsort(nums, jj + 1, rr);
    }
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        if(n < 2) return nums;

        qsort(nums, 0, n - 1);

        return nums;

    }
};

---

复杂度分析

n数组长度

• 时间复杂度 O(nlogn)。
• 空间复杂度 取决去递归深度， 平均O(logn) 最坏O(n)。

[nonevsnull]

思路

• 拿到题的直觉解法
  • 解法很多
  • 第一个选择MergeSort，有不错时间复杂度
  • 先拆分，再合并，Divide and Conquer
  • 第二个选择分桶，因为题目给的数字有限，直接给建一个array装起来再排序

AC

代码

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

    public void mergeSort(int[] nums, int start, int end){
        if(end - start == 0) return;
        if(end - start == 1) {
            if(nums[end] >= nums[start]) {
                return;
            } else {
                int temp = nums[end];
                nums[end] = nums[start];
                nums[start] = temp;
                return;
            }
        }
        int mid = start + (end - start) / 2;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid+1, end);
        merge(nums, start, mid, end);
    }

    public void merge(int[] nums, int start, int mid, int end){
        int[] temp = new int[end - start + 1];
        int left = mid, right = end;
        for(int i = temp.length - 1;i >= 0;i--){
            if(left < start || (right > mid && nums[right] >= nums[left])){
                temp[i] = nums[right--];
            } else {
                temp[i] = nums[left--];
            }
        }
        System.arraycopy(temp, 0, nums, start, temp.length);
    }
}

//bucket
class Solution {
    public int[] sortArray(int[] nums) {
        int[] temp = new int[50000*2+1];
        for(int i = 0;i < nums.length;i++){
            temp[nums[i]+50000] += 1;
        }
        int p = 0;
        for(int i = 0;i < temp.length;i++){
            while(temp[i] > 0){
                nums[p++] = i-50000;
                temp[i]--;
            }
        }
        return nums;

    }
}

复杂度

//merge sort time: O(NlogN),因为二分了，因此有logN次，每次，合并两个片段最多n个数，O(N)，因此加起来就是O(NlogN) space: O(N),再合并时，需要一个辅助的数组帮助合并，而不是在数组本身操作。

//bucket time: O(N) space: O(N)

[xj-yan]

Merge Sort

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

    private void mergeSort(int[] nums, int start, int end){
        if (start >= end) return;

        int mid = (end - start) / 2 + start;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid + 1, end);
        merge(nums, start, mid + 1, end);
    }

    private void merge(int[] nums, int leftStart, int rightStart, int end){
        int[] tmp = new int[end - leftStart + 1];
        int index = 0, leftIndex = leftStart, rightIndex = rightStart;
        while (leftIndex < rightStart && rightIndex <= end){
            if (nums[leftIndex] <= nums[rightIndex]){
                tmp[index++] = nums[leftIndex++];
            }else {
                tmp[index++] = nums[rightIndex++];
            }
        }
        while (leftIndex < rightStart) tmp[index++] = nums[leftIndex++];
        while (rightIndex <= end) tmp[index++] = nums[rightIndex++];

        for (int i = 0; i < tmp.length; i++){
            nums[i + leftStart] = tmp[i];
        }
    }
}

Time Complexity: O(nlogn), Space Complexity: O(n)

[thinkfurther]

思路

以前没有尝试过使用计数排序

代码

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        count_sort = [0] * (5*10**4 *2 +1)

        for i in nums:
            count_sort[i + 5*10**4] += 1

        result = []
        for idx,val in enumerate(count_sort):
            if val == 0:
                continue

            result += [idx - 5*10**4] * val

        return result

复杂度

时间复杂度 ：O(N)

空间复杂度：O(N)

[heyqz]

merge sort

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def mergeSort(nums):
            if len(nums) == 1:
                return nums
            mid = len(nums) // 2
            L, R = nums[:mid], nums[mid:]
            return merge(mergeSort(L), mergeSort(R))

        def merge(L, R):
            lenL, lenR = len(L), len(R)
            arr, i, j = [], 0, 0
            while i < lenL and j < lenR:
                if L[i] < R[j]:
                    arr.append(L[i])
                    i += 1
                else:
                    arr.append(R[j])
                    j += 1               
            if i < lenL:
                arr.extend(L[i:]) 
            if j < lenR:
                arr.extend(R[j:])
            return arr

        return mergeSort(nums)

quick sort

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def qsort(arr, lo, hi):
            if lo < hi:
                p = partition(arr, lo, hi)
                qsort(arr, lo, p-1)
                qsort(arr, p+1, hi)

        def partition(arr, lo, hi):
            pivot_idx = random.randint(lo, hi) 
            arr[pivot_idx], arr[hi] = arr[hi], arr[pivot_idx]
            pivot = arr[hi] 
            i = lo
            for j in range(lo, hi):
                if arr[j] < pivot:
                    arr[i], arr[j] = arr[j], arr[i]
                    i += 1
            arr[i], arr[hi] = arr[hi], arr[i]
            return i

        qsort(nums, 0, len(nums) - 1)
        return nums

[yyangeee]

912

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  const counts = Array(50000 * 2 + 1).fill(0);
  const res = [];
  for (const num of nums) counts[50000 + num] += 1;
  for (let i in counts) {
    while (counts[i]--) {
      res.push(i - 50000);
    }
  }
  return res;
};

解法

来自官方题解

[zhangzz2015]

思路

• 使用排序算法，了解各种排序方法的优缺点，以及最坏情况，使用quick sort实现。如果不使用random调整pivot，由于最坏情况会有o(N^2)，不能pass。空间复杂度，由于使用递归为O(logN)，时间复杂度一般为O(nlogn)，最坏为 O(n^2).

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
      /// quick sort. 

        quickSort(nums, 0, nums.size()-1, true);

        return nums; 
    }

    void quickSort(vector<int>& nums, int left, int right, bool randomize)
    {
        if(left>=right)
            return; 
       if (randomize) swap(nums[left + rand() % (right - left + 1)], nums[left]);        
        int index = sortNum(nums, left, right); 

        quickSort(nums, left, index-1, randomize); 
        quickSort(nums, index+1, right, randomize); 

    }

    int sortNum(vector<int>& nums, int left, int right)
    {
        int pivot = nums[left];

        while(left<right)
        {

            while(left<right && nums[right]>=pivot)
            {
                right--; 
            }

            swap(nums[right], nums[left]); 

            while(left< right&& nums[left]<pivot)
            {
                left++; 
            }

            swap(nums[left], nums[right]); 

        }

        nums[left] = pivot;   

        return left; 
    }
};

[wangzehan123]

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

    public void test(int[] nums,int start,int end){
        if(start>end){
            return;
        }
        int num = nums[start];
        int i = start;
        int j = end;
        while(i<j){
            while(i<j && nums[j]>=num){
                j--;
            }
            while(i<j && nums[i]<=num){
                i++;
            }
            if(i<j){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }  
        }
        nums[start] = nums[i];
        nums[i] = num;
        test(nums,start,i-1);
        test(nums,i+1,end);
    }
}

复杂度分析

令 n 为数组长度。

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

[hwpanda]

思路：Merge sort

function merge(left, right) {
    let arr = [];
    // Break out of loop if any one of the array gets empty
    while (left.length && right.length) {
        // Pick the smaller among the smallest element of left and right sub arrays
        if (left[0] < right[0]) {
            arr.push(left.shift());
        } else {
            arr.push(right.shift());
        }
    }
    // (in case we didn't go through the entire left or right array)
    return [...arr, ...left, ...right];
}

function sortArray(nums) {
    if (nums.length < 2) {
        return nums;
    }
    const middle = Math.floor(nums.length / 2);
    const left = nums.slice(0, middle);
    const right = nums.slice(middle);

    return merge(sortArray(left), sortArray(right));
}

[biancaone]

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        self.quick_sort(nums, 0, len(nums) - 1)
        return nums

    def quick_sort(self, nums, left, right):
        if left >= right:
            return

        start, end = left, right

        pivot = nums[(start + end) // 2]
        while start <= end:
            while start <= end and nums[start] < pivot:
                start += 1
            while start <= end and nums[end] > pivot:
                end -= 1

            if start <= end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1

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

[CoreJa]

思路

这题就是做排序，最近刚写了归并排序，再换个py的切片写法吧。归并排序，经典分治法，把数组分成两部分，对每一部分进行递归调用，最后将这两部分进行归并。

归并的过程需要两个指针，选最小的放到临时空间中，指针后移。返回临时空间得到归并后的结果。

代码

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def merge(left, right):
            tmp = []
            i = j = 0
            while i < len(left) and j < len(right):
                if left[i] < right[j]:
                    tmp.append(left[i])
                    i += 1
                else:
                    tmp.append(right[j])
                    j += 1
            if i < len(left):
                tmp.extend(left[i:])
            elif j < len(right):
                tmp.extend(right[j:])
            return tmp

        def merge_sort(nums):
            if len(nums) == 1:
                return nums
            elif len(nums) == 2:
                return nums if nums[0] < nums[1] else [nums[1], nums[0]]
            else:
                mid = len(nums) // 2
                return merge(merge_sort(nums[:mid]), merge_sort(nums[mid:]))

        return merge_sort(nums)

复杂度

时间复杂度O(nlogn) 空间复杂度O(n)

[qyw-wqy]

class Solution {
    Random r;
    public int[] sortArray(int[] nums) {
        this.r = new Random();
        qs(nums, 0, nums.length-1);
        return nums;
    }

    private void qs(int[] nums, int left, int right) {
        if (left >= right) return;
        int i = left + r.nextInt(right - left + 1);
        int peak = nums[i];
        nums[i] = nums[left];
        nums[left] = peak;
        int l = left;
        int r = right;
        while (l < r) {
            while (l < r && nums[r] >= peak) r--;
            nums[l] = nums[r];
            while (l < r && nums[l] <= peak) l++;
            nums[r] = nums[l];
        }
        nums[l] = peak;
        qs(nums, left, l-1);
        qs(nums, l+1, right);
    }
}

Time: O(NlogN)\ Space: O(N)

[florenzliu]

Explanation

• use mergeSort
• divide and conquer: merge sort left, merge sort right, then merge the sorted left and right into one sorted array
• T(n) = 2T(n/2) + θ(n)

Python

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def mergeSort(start, end, arr): 
            if start < end:
                mid = start + (end - start) // 2
                mergeSort(start, mid, arr)
                mergeSort(mid+1, end, arr)
                merge(start, mid, end, arr)

        def merge(start, mid, end, arr):
            temp = [0 for _ in range(end - start + 1)]
            leftIndex, rightIndex = start, mid+1
            curr = 0
            while leftIndex < mid+1 and rightIndex < end+1:
                if arr[leftIndex] <= arr[rightIndex]:
                    temp[curr] = arr[leftIndex]
                    leftIndex += 1
                else:
                    temp[curr] = arr[rightIndex]
                    rightIndex += 1
                curr += 1

            while leftIndex < mid+1:
                temp[curr] = arr[leftIndex]
                leftIndex += 1
                curr += 1

            while rightIndex < end+1:
                temp[curr] = arr[rightIndex]
                rightIndex += 1
                curr += 1

            # copy temp to arr
            for i in range(start, end+1):
                arr[i] = temp[i-start]

        mergeSort(0, len(nums)-1, nums)
        return nums

Complexity:

• Time Complexity: O(NlogN)
• Space Complexity: O(N)

[chen445]

思路

Using merge sort

代码

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def partition(nums:List[int],low:int,high:int):
            mid=(low + high) // 2
            nums[low], nums[mid] = nums[mid], nums[low] 
            i=low+1
            pivot=nums[low]
            for j in range(low+1,high):
                if nums[j]<=pivot:
                    nums[i],nums[j]=nums[j],nums[i]
                    i+=1
            nums[low],nums[i-1]=nums[i-1],nums[low]
            return i-1
        def quicksort(nums, low, high):
            if low < high:
                p=partition(nums,low,high)
                quicksort(nums,low,p-1)
                quicksort(nums,p+1,high)
        quicksort(nums,0,len(nums))
        return nums

复杂度

Time: O(nlogn)

Space: O(n)

[ZacheryCao]

Idea:

MergeSort

Code:

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def mergeSort(n):
            if len(n)<2:
                return
            mid = len(n)//2
            L = n[:mid]
            R = n[mid:]
            mergeSort(L)
            mergeSort(R)
            i, j, k = 0, 0, 0
            while i < len(L) and j < len(R):
                if L[i] < R[j]:
                    n[k]=L[i]
                    i += 1
                else:
                    n[k] = R[j]
                    j += 1
                k += 1
            while i < len(L):
                n[k] = L[i]
                i += 1
                k += 1
            while j < len(R):
                n[k] = R[j]
                j += 1
                k += 1
        mergeSort(nums)
        return nums

Complexity:

Time: O(nlogn) Space: O(n)

[laofuWF]

# merge sort: divide and conquer, merge 2 pre-sorted arrays
# to merge 2 sorted arrays use 3 pointers i, j, k
# insert lowest element to nums and move pointers

# time: O(NlogN)
# space: O(N)

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums) > 1:
            mid = len(nums) // 2
            left = nums[:mid]
            right = nums[mid:]

            self.sortArray(left)
            self.sortArray(right)

            i = j = k = 0

            while i < len(left) and j < len(right):
                if left[i] < right[j]:
                    nums[k] = left[i]
                    i += 1
                else:
                    nums[k] = right[j]
                    j += 1
                k += 1

            while i < len(left):
                nums[k] = left[i]
                i += 1
                k += 1
            while j < len(right):
                nums[k] = right[j]
                j += 1
                k += 1

        return nums

[chang-you]

class Solution {
    public int[] sortArray(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        quickSort(nums, l, r);

        return nums;
    }

    public void quickSort(int[] nums, int l, int r){
        if (l >= r)
            return;
        int i = l-1, j = r+1, x = nums[r];
        while(i < j){
            do i++; while(nums[i] < x);
            do j--; while(nums[j] > x);

            if (i < j){
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }

        }
        quickSort(nums, l, i-1);
        quickSort(nums, i, r);
    }
}

[pan-qin]

idea

merge sort

Complexity:

Time: O(nlogn) Space: O(n)

code:

class Solution {
    public int[] sortArray(int[] nums) {
        return mergeSort(nums,0,nums.length-1);
    }
    public int[] mergeSort(int[] nums, int left, int right) {
        if(left==right) {
            return new int[]{nums[left]};
        }
        int mid = left+ (right-left)/2;
        int[] leftHalf=mergeSort(nums,left,mid);
        int[] rightHalf=mergeSort(nums,mid+1,right);
        int[] res= new int[right-left+1];
        int i=0,j=0,k=0;
        while(i<leftHalf.length && j<rightHalf.length) {
            if(leftHalf[i]<rightHalf[j]) {
                    res[k++]=leftHalf[i++];
            }
            else 
                res[k++]=rightHalf[j++];
        }
        while(i<leftHalf.length) 
            res[k++]=leftHalf[i++];
        while(j<rightHalf.length)
            res[k++]=rightHalf[j++];
        return res;
    }
}

[sxr000511]

var sortArray = function (nums) { const counts = Array(50000 * 2 + 1).fill(0); const res = []; for (const num of nums) counts[50000 + num] += 1; for (let i in counts) { while (counts[i]--) { res.push(i - 50000); } } return res; };

[SunnyYuJF]

思路

Quick sort

代码 Python

def sortArray(self, nums: List[int]) -> List[int]:         

        def partition(nums,low,high):
            pivot = (low+high)//2
            nums[pivot],nums[high] = nums[high],nums[pivot]

            for j in range(low,high):
                if nums[j] < nums[high]:
                    nums[low],nums[j] = nums[j],nums[low]
                    low += 1
            nums[low],nums[high] = nums[high],nums[low]
            return low

        def quicksort(nums,low,high):
            if low >= high:
                return
            pivot = partition(nums,low,high)
            quicksort(nums,low,pivot-1)
            quicksort(nums,pivot+1,high)

        quicksort(nums,low=0,high=len(nums)-1)
        return nums

复杂度分析

时间复杂度： O(NlogN)
空间复杂度： O(1)

[freesan44]

思路

快速排序，pivot随机主元通过，固定位置容易超时

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        # # 超时
        # if len(nums) <= 1:
        #     return nums
        # pivot = nums[0]
        # right,left = [],[]
        # for each in nums[1:]:
        #     if each <= pivot:
        #         left.append(each)
        #     else:
        #         right.append(each)
        # return self.sortArray(left) + [pivot] + self.sortArray(right)
        # 快速排序，采用随机pivot
        from random import randint
        if len(nums) <= 1:
            return nums
        randNum = randint(0,len(nums)-1)
        pivot = nums[randNum]
        right, left = [], []
        for index,each in enumerate(nums):
            if index == randNum:continue
            if each <= pivot:
                left.append(each)
            else:
                right.append(each)
        return self.sortArray(left) + [pivot] + self.sortArray(right)

    #     #快速排序
    #     self.quickSort(nums,0,len(nums)-1)
    #     return nums
    #
    # def quickSort(self, nums, left, right):
    #     from random import randint
    #     pivot = nums[randint(left,right)]
    #     i,j = left, right
    #     while i<=j:
    #         # print(i,j,nums)
    #         while nums[i]<pivot:
    #             i += 1
    #         while nums[j]>pivot:
    #             j -= 1
    #         if i<=j:
    #             nums[i],nums[j] = nums[j],nums[i]
    #             i += 1
    #             j -= 1
    #     if i < right:
    #         self.quickSort(nums, i, right)
    #     if j > left:
    #         self.quickSort(nums,left, j)

if __name__ == '__main__':
    nums = [5,1,1,2,0,0]
    ret = Solution().sortArray(nums)
    print(ret)

复杂度分析

令 n 为数组长度。

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

[MonkofEast]

912. Sort an Array

Click Me

Algo

1. I think mergeSort is better.
2. quickSort also does

Code

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        # insertion OT
        # quick sort basic idea

        #[Code below can RUN!]
        if len(nums) <= 1: return nums

        pivot = random.choice(nums)
        sL = [n for n in nums if n < pivot]
        eL = [n for n in nums if n == pivot]
        bL = [n for n in nums if n > pivot]
        return self.sortArray(sL) + eL + self.sortArray(bL)

        """
        # quick sort implement
        def quickSort(head, tail):
            if head < tail:
                # partition
                pivot = head
                partIdx = head + 1
                i = partIdx
                while i <= tail:
                    if nums[i] < nums[pivot]:
                        nums[i], nums[partIdx] = nums[partIdx], nums[i]
                        partIdx += 1
                    i += 1
                # put pivot to the mid
                partIdx -= 1
                nums[pivot], nums[partIdx] = nums[partIdx], nums[pivot]
                # quicksort arr on t lft/rgt of pivot
                quickSort(head, partIdx - 1)
                quickSort(partIdx + 1, tail)
        quickSort(0, len(nums) - 1)
        return nums
        """

Comp

T: O(N^2), O(NlogN)

[Francis-xsc]

思路

快速排序

代码

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        quickSort(nums,0,nums.size()-1);
        return nums;
    }
    void quickSort(vector<int>&a,int begin,int end)
    {
        if(begin>=end)
            return;
        int flag=a[begin];
        int i=begin,j=end;
        while(i<j)
        {
            while(i<j&&a[j]>=flag)
                j--;
            while(i<j&&a[i]<=flag)
                i++;
            if(i<j)
            {
                int t=a[i];
                a[i]=a[j];
                a[j]=t;
            }
        }
        a[begin]=a[i];
        a[i]=flag;
        quickSort(a,begin,i-1);
        quickSort(a,i+1,end);
    }
};

复杂度分析

• 时间复杂度：O(nlogn)，其中 N 为数组长度。
• 空间复杂度：O(nlogn)

[Bochengwan]

思路

quicksort

代码

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

        def quickSort(nums,start,end):
            if start<end:
                left,right = start,end
                pivot = nums[(left+right)//2]
                while left<=right:
                    while left<=right and nums[left]<pivot:
                        left+=1
                    while left<=right and nums[right]>pivot:
                        right-=1
                    if left<=right:
                        nums[left],nums[right]=nums[right],nums[left]
                        left+=1
                        right-=1
                        print(nums,left,right,pivot)
                quickSort(nums,start,right)
                quickSort(nums,left,end)
        quickSort(nums,0,len(nums)-1)
        return nums

复杂度分析

• 时间复杂度：O(NLOGN)，其中 N 为数组长度。
• 空间复杂度：O(LOGN)

[BadCoderChou]

class Solution {
    public int[] sortArray(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        quickSort(nums, l, r);

        return nums;
    }

    public void quickSort(int[] nums, int l, int r){
        if (l >= r)
            return;
        int i = l-1, j = r+1, x = nums[r];
        while(i < j){
            do i++; while(nums[i] < x);
            do j--; while(nums[j] > x);

            if (i < j){
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }

        }
        quickSort(nums, l, i-1);
        quickSort(nums, i, r);
    }
}

[chenming-cao]

解题思路

快速排序，其中pivot是随机选择的。

代码

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

    private void randomizedQuickSort(int[] nums, int l, int r) {
        if (l < r) {
            int pos = randomizedPartition(nums, l, r);
            randomizedQuickSort(nums, l, pos - 1);
            randomizedQuickSort(nums, pos + 1, r);
        }
    }

    private int randomizedPartition(int[] nums, int l, int r) {
        int i = new Random().nextInt(r - l + 1) + l; // random index for pivot
        swap(nums, i, r); // move the pivot to the right
        return partition(nums, l, r);
    }

    private int partition(int[] nums, int l, int r) {
        int i = l - 1;
        int pivot = nums[r];
        for (int j = l; j < r; j++) {
            if (nums[j] > pivot) continue;
            else {
                i++; // i used to point to the position storing the value less than pivot
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, r);
        return i + 1; // pivot is at the correct position
    }

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

复杂度分析

• 时间复杂度：平均O(nlogn)；最坏O(n^2)，当原数组倒序排列
• 空间复杂度：O(h)，h为快速排序调用的层数

[pophy]

思路

• quick sort

Java Code

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

    private int[] sort(int[] nums, int start, int end) {
        int k = partition(nums, start, end);
        if (k - 1 > start) {
            sort(nums, start, k - 1);
        }
        if (k + 1 < end) {
            sort(nums, k + 1, end);
        }
        return nums;
    }

    private int partition(int[] nums, int start, int end) {
        int random = getRandom(start, end);
        swap(nums, random, start);
        int pivot = nums[start];
        int l = start + 1, r = end;
        while (l <= r) {
            if (nums[l] > pivot && nums[r] < pivot) {
                swap(nums, l++, r--);
            } else if (nums[l] <= pivot) {
                l++;
            } else if (nums[r] >= pivot) {
                r--;
            }
        }
        swap(nums, r, start);
        return r;
    }

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

    public int getRandom(int min, int max) {
        if (min == max) {
            return min;
        }        
        Random random = new Random();
        return random.nextInt(max - min) + min;
    }
}

时间&空间

• 时间 O(nlog(n)) 使用随机数作为pivot
• 空间 O(1)

[chun1hao]

var sortArray = function (nums) {
  let len = nums.length;
  if (len < 2) return nums;
  let mid = Math.floor(len / 2);
  let left = nums.slice(0, mid);
  let right = nums.slice(mid);
  return merge(sortArray(left), sortArray(right));
};
function merge(left, right) {
  let leftLen = left.length;
  let rightLen = right.length;
  let leftIdx = 0;
  let rightIdx = 0;
  let ans = [];
  while (leftIdx < leftLen && rightIdx < rightLen) {
    if (left[leftIdx] <= right[rightIdx]) {
      ans[ans.length] = left[leftIdx++];
    } else {
      ans[ans.length] = right[rightIdx++];
    }
  }
  while (leftIdx < leftLen) {
    ans[ans.length] = left[leftIdx++];
  }
  while (rightIdx < rightLen) {
    ans[ans.length] = right[rightIdx++];
  }
  return ans;
}

[wangyifan2018]

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        self.randomized_quicksort(nums, 0, len(nums) - 1)
        return nums

    def randomized_quicksort(self, nums, l, r):
        if r - l <= 0:
            return 
        mid = self.randomized_partition(nums, l, r)
        self.randomized_quicksort(nums, l, mid - 1)
        self.randomized_quicksort(nums, mid + 1, r)

    def randomized_partition(self, nums, l, r):
        pivot = random.randint(l, r)
        nums[pivot], nums[r] = nums[r], nums[pivot]
        i = l - 1
        for j in range(l, r):
            if nums[j] < nums[r]:
                i += 1
                nums[j], nums[i] = nums[i], nums[j]
        i += 1
        nums[i], nums[r] = nums[r], nums[i]
        return i

[user1689]

题目

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

思路

quickSort, mergeSort

python3

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

        def partition(low, high):
            pivot = random.randint(low, high)
            swap(pivot, low)
            i, j = low, low + 1
            while j <= high:
                if nums[j] < nums[low]:
                    swap(j, i + 1)
                    i += 1
                j += 1
            swap(low, i)
            return i

        def swap(i, j):
            nums[i], nums[j] = nums[j], nums[i]

        def quickSort(low, high):
            if low < high:
                mid = partition(low, high)
                quickSort(low, mid - 1)
                quickSort(mid + 1, high)

        quickSort(0, len(nums) - 1)
        return nums

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def divide(low, high):
            if low < high:
                mid = low + (high - low) // 2
                divide(low, mid)
                divide(mid + 1, high)
                merge(low, mid, high)

        def merge(low, mid, high):
            tmp = [0] * (high - low + 1)
            i, j = low, mid + 1
            k = 0
            while i <= mid and j <= high:
                if nums[i] <= nums[j]:
                    tmp[k] = nums[i]
                    k += 1
                    i += 1

                # elif nums[i] > nums[j]:
                else:
                    tmp[k] = nums[j]
                    k += 1
                    j += 1

            while i <= mid:
                tmp[k] = nums[i]
                k += 1
                i += 1

            while j <= high:
                tmp[k] = nums[j]
                k += 1
                j += 1

            for i in range(len(tmp)):
                nums[low + i] = tmp[i]

        divide(0, len(nums) - 1)
        return nums

时间复杂度

• time nlogn
• space logn

相关题目

1. 待补充

[BlueRui]

Problem 912. Sort an Array

Algorithm

• We will use quick sort and merge sort to solve this problem. Both sorting methods use divide-and-conquer and are recursive.
• The difference is in quick sort, all work happens in the divide step. The combine step does nothing. Whereas in merge sort, sorting happens in the combine step.

Quick Sort

Complexity

• Time Complexity: Amortized O(NlogN).
• Space Complexity: O(logN), depth of recursion call stack.

Code

Language: Java

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

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

private int partition(int[] nums, int left, int right) {
    // Return pivot index after partition
    int pivotInd = getPivotIndex(left, right);
    int pivotVal = nums[pivotInd];
    // Move pivot to the right end
    swap(nums, pivotInd, right);
    int leftBound = left;
    int rightBound = right - 1;
    while (leftBound <= rightBound) {
        if (nums[leftBound] < pivotVal) {
            leftBound++;
        } else if (nums[rightBound] >= pivotVal) {
            rightBound--;
        } else {
            swap(nums, leftBound++, rightBound--);
        }
    }
    swap(nums, leftBound, right);
    return leftBound;
}

private int getPivotIndex(int left, int right) {
    return left + (int) (Math.random() * (right - left + 1));
}

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

Merge Sort

Complexity

• Time Complexity: O(NlogN).
  • There are log(N) divide layers and log(N) merge layers.
  • For the divide layers, divide time complexity is the time for random access on an array. Total is 1 + 2 + 4 + 8 + ... + n = 2n. Time: O(N)
  • For each merge layer, the time complexity is O(N). Each element is operated once. There are log(N) layers.
• Space Complexity: O(N). Space for the extra array.

Code

Language: Java

public int[] sortArray(int[] nums) {
    int[] helper = new int[nums.length];
    mergeSort(nums, helper, 0, nums.length - 1);
    return nums;
}

private void mergeSort(int[] nums, int[] helper, int left, int right) {
    if (left >= right) {
        return;
    }
    int mid = left + (right - left) / 2;
    mergeSort(nums, helper, left, mid);
    mergeSort(nums, helper, mid + 1, right);
    merge(nums, helper, left, mid, right);
}

private void merge(int[] nums, int[] helper, int left, int mid, int right) {
    for (int i = left; i <= right; i++) {
        helper[i] = nums[i];
    }
    int p1 = left;
    int p2 = mid + 1;
    while (p1 <= mid && p2 <= right) {
        if (helper[p1] <= helper[p2]) {
            nums[left++] = helper[p1++];
        } else {
            nums[left++] = helper[p2++];
        }
    }
    while (p1 <= mid) {
        nums[left++] = helper[p1++];
    }
}

[xieyj17]

import random
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums) < 2:
            return nums
        pivot = random.choice(nums)
        left = [i for i in nums if i< pivot]
        middle = [i for i in nums if i == pivot]
        right = [i for i in nums if i > pivot]

        return self.sortArray(left)+middle+self.sortArray(right)

Implementation of quicksort

Space: O(N)

Time: Worst O(N^2) Avg O(NlogN)

[Tao-Mao]

Idea

Quicksort

Code

class Solution {
    // int cnt = 0;
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);
        // System.out.println(cnt);
        return nums;
    }
    public void quickSort(int[] nums, int left, int right) {
        int i = left;
        int j = right;
        if (left >= right) return;
        int index = right;
        while (left < right) {                
            while (right > left && nums[left] < nums[index]) {
                ++left;
            }
            // swap(nums, left,right);
            while (right > left && nums[right] >= nums[index]) {
                --right;
            }
            if (left == right) {
                swap(nums,left,index);
            }
            else {
                swap(nums, left,right);
            }

        }
        quickSort(nums,i,left-1);
        quickSort(nums,right+1,j);
    }
    public void swap (int[] nums, int i, int j) {
        // cnt++;
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Complexity

• Time: nlogn
• Space: logn

[ziyue08]

var sortArray = function (nums) {
    sort(nums);
    return nums;
};

//稳定排序，之后小于才会引起移动，等于不会引起移动
//时间复杂度O(n2)
//折半插入排序
function sort(arr) {
    //先用折半查找的方式，找到待插入的位置，然后直接后移
    let i, j, low, high, mid;
    for (i = 1; i < arr.length; i++) {
        let temp = arr[i] //哨兵暂存
        low = 0; //默认i之前的所有元素已经是有序的
        high = i - 1;
        while (low <= high) {
            mid = ((high - low) > 2) + low;
            if (arr[mid] > temp) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        for(j = i-1;j >=high+1;j--){
            arr[j+1] = arr[j];
        }
        arr[high+1] = temp;
    }

[RocJeMaintiendrai]

题目

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

思路

快排

代码

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

    private void quickSort(int[] nums, int start, int end) {
        if(start >= end) {
            return;
        }
        int pivot = sort(nums, start, end);
        quickSort(nums, start, pivot - 1);
        quickSort(nums, pivot + 1, end);
    }

    private int sort(int[] nums, int left, int right) {
        int idx = random.nextInt(right - left + 1) + left;
        swap(nums,left, idx);
        int j = left;
        for(int i = left + 1; i <= right; i++) {
            if(nums[i] < nums[left]) {
                j++;
                swap(nums, i, j);
            }
        }
        swap(nums, left, j);
        return j;
    }

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

复杂度分析

时间复杂度

O(nlogn)

空间复杂度

O(logn)

[yingliucreates]

link:

https://leetcode.com/problems/sort-an-array/

代码 Javascript

const sortArray = function (nums) {
  if (nums.length < 2) return nums;
  let mid = Math.floor(nums.length) / 2;
  let left = sortArray(nums.slice(0, mid));
  let right = sortArray(nums.slice(mid));
  return merge(left, right);
};

const merge = function (left, right) {
  const merged = [];
  let ind1 = 0;
  let ind2 = 0;
  while (left[ind1] !== undefined || right[ind2] !== undefined) {
    if (left[ind1] < right[ind2]) merged.push(left[ind1++]);
    else if (left[ind1] >= right[ind2]) merged.push(right[ind2++]);
    else {
      left[ind1] === undefined
        ? merged.push(right[ind2++])
        : merged.push(left[ind1++]);
    }
  }
  return merged;
};

time/space O(logn)

[ZJP1483469269]

题目地址(912. 排序数组)

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

题目描述

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

 

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

 

提示：

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

前置知识

公司

• 暂无

思路

归并排序

关键点

代码

• 语言支持：Java

Java Code:

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

    }
}

复杂度分析

令 n 为数组长度。

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

[okbug]

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    return nums.sort((a, b) => a - b);
};

[lilixikun]

冒泡排序

var sortArray = function(nums) {
    // 冒泡排序
    let len = nums.length
    for(let i=0;i<len;i++){
        for(let j=0;j<len-1-i;j++){
            if(nums[j]>nums[j+1]){
                [nums[j+1],nums[j]]=[nums[j],nums[j+1]]
            }
        }
    }
    return nums
};

插入排序

var sortArray = function(nums) {
    let len = nums.length
    for(let i=0;i<len;i++){
        let j = i
        let tem = nums[i]
        while(j>0&&nums[j-1]>tem){
            nums[j]=nums[j-1]
            j--
        }
        nums[j]=tem
    }
    return nums
};

[xiezhengyun]

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  //  选择排序
  // 假定一个数组长度n，每次取第i个数据，在后面[i, n-1]，中取最小的一个数据，移到当前i的位置。
  // 时间复杂度 O(n^2)
  for (let i = 0; i < nums.length; i++) {
    let minIndex = i

    for (let j = i; j < nums.length; j++) {
      if (nums[j] - nums[minIndex] < 0) minIndex = j;
    }

    [nums[i], nums[minIndex]] = [nums[minIndex], nums[i]];
  }
  return nums;
};

// 插入排序
// 假定一个数组长度n，从左边开始，取第i个数据，在[0, i-1]中移动它应该呆的位置
// 从右边无序的区间，插入左边有序的区间，第i个元素，如果它比左边的数字小，那就把左边的数字右移一位
// 复杂度 O(n^2), 但是越有序的数组越快，完全有序就是O(n)
var sortArray = function (arr) {
  for (let i = 1; i < arr.length; i++) {
    let temp = arr[i];
    let j;
    for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
      arr[j + 1] = arr[j];
    }
    arr[j + 1] = temp;
  }
  return arr;
}