【Day 36 】2023-03-21 - 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

[jmaStella]

思路

quickSort

代码

    public int[] sortArray(int[] nums) {
        // quick sort
        quickSort(nums,0, nums.length-1);
        return nums;
    }
    public void quickSort(int[] nums, int start, int end){
        if(start >= end){
            return;
        }
        int pivot = partition(nums, start, end);
        quickSort(nums, start, pivot-1);
        quickSort(nums, pivot+1, end);
    }
    public int partition(int[] nums, int start, int end){
        //number greater than or equal to 0.0 and less than 1.0.
        int index = (int) (Math.random() *(end - start+1)) + start;
        swap(nums, index, end);
        int count = start;
        for(int i=start; i < end; i++){
            if(nums[i] < nums[end]){
                swap(nums, i, count);
                count++;
            }
        }
        swap(nums, count, end);
        return count;

    }
    public void swap(int[] nums, int x, int y){
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }

复杂度

时间 O(nlogn) 空间 O(1)

[JiangyanLiNEU]

• Merge Sort
• T = O(NLogN)
• S = O(N)

  class Solution(object):
  def sortArray(self, nums):
      if len(nums)<=1:
          return nums
      res = []
      middle = len(nums)//2
      left = self.sortArray(nums[:middle])
      right = self.sortArray(nums[middle:])
      while left and right:
          if left[0] < right[0]:
              res.append(left.pop(0))
          else:
              res.append(right.pop(0))
      return res+left if left else res+right

[huifeng248]

from collections import deque
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums) == 1:
            return nums

        mid = len(nums)//2
        left = self.sortArray(nums[:mid])
        right = self.sortArray(nums[mid:])

        res = self.merge(left, right)
        return res

    def merge(self, left, right):
        left = deque(left)
        right = deque(right)
        res = []
        while left and right:
            if left[0] <= right[0]:
                res.append(left[0])
                left.popleft()
            else:
                res.append(right[0])
                right.popleft()
        if left:
            res += left
        if right: 
            res += right
        return res

# time complexity: O(nlog(n))
# spece complexity: tbd

```python 

[lp1506947671]

class Solution:
    def max_heapify(self, heap, root, heap_len):
        p = root
        while p * 2 + 1 < heap_len:
            l, r = p * 2 + 1, p * 2 + 2
            if heap_len <= r or heap[r] < heap[l]:
                nex = l
            else:
                nex = r
            if heap[p] < heap[nex]:
                heap[p], heap[nex] = heap[nex], heap[p]
                p = nex
            else:
                break

    def build_heap(self, heap):
        for i in range(len(heap) - 1, -1, -1):
            self.max_heapify(heap, i, len(heap))

    def heap_sort(self, nums):
        self.build_heap(nums)
        for i in range(len(nums) - 1, -1, -1):
            nums[i], nums[0] = nums[0], nums[i]
            self.max_heapify(nums, 0, i)

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

时间复杂度:O(nlogn)

空间复杂度：O(1)

[NorthSeacoder]

/**归并
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    if (nums.length === 1) return nums;
    const mid = Math.floor(nums.length / 2);
    //slice不包括 end
    return merge(sortArray(nums.slice(0, mid)), sortArray(nums.slice(mid)));
};
const merge = (arr1, arr2) => {
    const res = [];
    while (arr1.length && arr2.length) {
        if (arr1[0] < arr2[0]) {
            res.push(arr1.shift());
        } else {
            res.push(arr2.shift());
        }
    }

    if (arr1.length) res.push(...arr1);
    if (arr2.length) res.push(...arr2);
    return res;
};

• TC:O(nlogn)
• SC:O(n)

[LIMBO42]

class Solution {
public:
    /* 快排
    void randomnum(vector<int> &nums, int l, int r) {
        int x = rand() % (r - l + 1) + l;
        swap(nums[r], nums[x]);
    }
    int partition(vector<int> &nums, int l, int r) {
        randomnum(nums, l, r);
        int &num = nums[r];
        while(l < r) {
            while(l < r && nums[l] <= num) l++;
            while(l < r && nums[r] >= num) r--;
            swap(nums[l], nums[r]);
        }
        swap(nums[l], num);
        return l;
    }
    void quicksort(vector<int> &nums, int l, int r) {
        if(l >= r) return;
        int pivot = partition(nums, l, r);
        quicksort(nums, l, pivot - 1);
        quicksort(nums, pivot + 1, r);
    }*/

    // 归并排序
    void mergesort(vector<int> &nums, int l, int r) {
        if(l >= r) return;
        int mid = (r - l) / 2 + l;
        mergesort(nums, l, mid);
        mergesort(nums, mid + 1, r);
        // 合并
        vector<int> tmp(r - l + 1);
        int i = l; int j = mid + 1;
        int count = 0;
        while(i <= mid && j <= r) {
            if(nums[i] <= nums[j]) {
                tmp[count++] = nums[i];
                i++;
            } else {
                tmp[count++] = nums[j];
                j++;
            }
        }
        while(i <= mid) {
            tmp[count++] = nums[i++];
        }
        while(j <= r) {
            tmp[count++] = nums[j++];
        }
        for(int k = 0; k < r - l + 1; ++k) {
            nums[l + k] = tmp[k];
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        // 写个快排
        // srand(time(0));
        // quicksort(nums, 0, nums.size() - 1);
        mergesort(nums, 0, nums.size() - 1);
        return nums;
    }
};

[kofzhang]

思路：各种排序（该死的官方针对我的快速排序，Python过不了）

归并排序

复杂度

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

代码

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums)<=1:
            return nums
        mid = len(nums)>>1
        left = self.sortArray(nums[:mid])
        right = self.sortArray(nums[mid:])
        l = 0
        r = 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
        while l<len(left):
            res.append(left[l])
            l += 1
        while r<len(right):
            res.append(right[r])
            r += 1
        return res

[aswrise]

class Solution:
    def sortArray(self, nums):
        def merge(nums, p, mid, r):
            temp = []
            left, right = p, mid + 1

            while left <= mid and right <= r:
                if nums[left] <= nums[right]: 
                    temp += [nums[left]]
                    left += 1
                else:
                    temp += [nums[right]]
                    right += 1
            if left <= mid:temp += nums[left:mid+1]
            elif right <= r: temp += nums[right:r+1]
            nums[p:r+1] = temp

        def sort(nums, p, r):
            if p >= r: return 
            mid = (p + r)//2
            sort(nums, p, mid)
            sort(nums, mid + 1, r)
            merge(nums, p, mid, r)

        n = len(nums)
        sort(nums, 0, n-1)
        return nums

[bookyue]

TC: O(nlogn)
SC: O(logn)

    public int[] sortArray(int[] nums) {
        quicksort(nums);
        return nums;
    }

    // median of 3
    private void quicksort(int[] nums) {
        quicksort(nums, 0, nums.length - 1);
    }

    private void quicksort(int[] nums, int left, int right) {
        if (left + 7 >= right) {
            insertionSort(nums, left, right);
            return;
        }

        int pivot = partition(nums, left, right);
        quicksort(nums, left, pivot - 1);
        quicksort(nums, pivot + 1, right);
    }

    private void insertionSort(int[] nums, int left, int right) {
        for (int i = left; i <= right; i++) {
            int tmp = nums[i];
            int j;
            for (j = i; j > left && nums[j - 1] > tmp; j--) 
                nums[j] = nums[j - 1];

            nums[j] = tmp;
        }
    }

    private int partition(int[] nums, int left, int right) {
        int mid = (left + right) >>> 1;
        if (nums[left] > nums[mid]) swap(nums, left, mid);
        if (nums[left] > nums[right]) swap(nums, left, right);
        if (nums[mid] > nums[right]) swap(nums, mid, right);
        swap(nums, left, mid);

        int pivot = nums[left];
        int lo = left + 1;
        int hi = right;
        while (true) {
            while (nums[lo] < pivot) lo++;
            while (nums[hi] > pivot) hi--;

            if (lo >= hi) break;
            swap(nums, lo, hi);
            lo++;
            hi--;
        }

        swap(nums, left, hi);
        return hi;
    }

    private void swap(int[] nums, int a, int b) {
        if (a == b) return;

        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

[linlizzz]

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

        def merge_sort(nums, l, r):
            if l == r:
                return
            mid = (l + r) // 2
            merge_sort(nums, l, mid)
            merge_sort(nums, mid + 1, r)
            tmp = []
            i, j = l, mid + 1
            while i <= mid or j <= r:
                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

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

[ZhuMengCheng]

var sortArray = function(nums) {
  const n = nums.length;
  for (let i = 0; i < n - 1; ++i) {
    let minIndex = i;
    for (let j = i + 1; j < n; ++j) {
      if (nums[minIndex] > nums[j]) {
        minIndex = j;
      }
    }
    [nums[i], nums[minIndex]] = [nums[minIndex], nums[i]];
  }
  return nums;
};

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

[Meisgithub]

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

[Abby-xu]

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        # Runtime: O(nlogn) expected, O(n^2) worst case
        # Space: O(n) expected, O(n^2) worst case
        if len(nums) <= 1: return nums

        pivot = random.choice(nums)
        lt = [v for v in nums if v < pivot]
        eq = [v for v in nums if v == pivot]
        gt = [v for v in nums if v > pivot]

        return self.sortArray(lt) + eq + self.sortArray(gt)

[Zoeyzyzyzy]

class Solution {
    // quick sort
    int[] nums1;

    public int[] sortArray(int[] nums) {
        this.nums1 = nums;
        quicksort(0, nums.length - 1);
        return nums1;
    }

    private void quicksort(int left, int right) {
        if (left >= right)
            return;
        int pivot = partition(left, right);
        quicksort(left, pivot - 1);
        quicksort(pivot + 1, right);
    }

    private int partition(int left, int right) {
        Random random = new Random();
        int pivot = left + random.nextInt(right - left + 1);
        swap(right, pivot);
        int i = left;
        for (int j = left; j < right; j++) {
            if (nums1[j] < nums1[right]) {
                if (i == j)
                    i++;
                else {
                    swap(i, j);
                    i++;
                }
            }
        }
        swap(right, i);
        return i;
    }

    private void swap(int a, int b) {
        int temp = nums1[a];
        nums1[a] = nums1[b];
        nums1[b] = temp;
    }
}

[Horace7]

var sortArray = function(nums) {
    return nums.sort((a, b) => a - b)
};

[wangqianqian202301]

思路

merge sort, 不能用快排， 在有序状态下时间复杂度变为O(n2)

代码

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

    def mergeSort(self, nums):
        def recur(left, right):
            nonlocal tmp
            if left >= right: return

            mid = (left + right) // 2
            recur(left, mid)
            recur(mid + 1, right)

            pl, pr, pt = left, mid + 1, left
            while pl <= mid and pr <= right:
                if nums[pl] <= nums[pr]:
                    tmp[pt] = nums[pl]
                    pl += 1
                else:
                    tmp[pt] = nums[pr]
                    pr += 1
                pt += 1
            if pl < mid + 1:
                tmp[pt:right + 1] = nums[pl:mid + 1]
            elif pr < right + 1:
                tmp[pt:right + 1] = nums[pr:right + 1]
            nums[left:right + 1] = tmp[left:right + 1]

        l = len(nums)
        tmp = [None] * l
        recur(0, l - 1)
        return nums

复杂度

[X1AOX1A]

from math import floor, ceil

class Solution:

    def Merge(self, L, R, nums):
        p, q = len(L), len(R)
        i, j, k = 0, 0, 0
        while (i<p) and (j<q):
            if L[i]<=R[j]:
                nums[k] = L[i]
                i+=1
            else:
                nums[k] = R[j]
                j+=1
            k+=1

        nums[k:p+q] = R[j:q] if i==p else L[i:p]
        return nums

    def sortArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        if len(nums)>1:
            L = nums[:ceil(n/2)]
            R = nums[ceil(n/2):]
            L = self.sortArray(L)
            R = self.sortArray(R)
            nums = self.Merge(L, R, nums)
        return nums

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

[FireHaoSky]

思路：

"""
快速排序超时了，全是2.改用归并排序，先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 """

代码：python

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def mergeSort(arr, low, high):
            if low >= high:
                return

            mid = low + (high-low)//2
            mergeSort(arr,low,mid)
            mergeSort(arr,mid+1, high)

            left, right = low, mid+1
            tmp = []
            while left <= mid and right <= high:
                if arr[left] <= arr[right]:
                    tmp.append(arr[left])
                    left += 1
                else:
                    tmp.append(arr[right])
                    right += 1

            while left <= mid:
                tmp.append(arr[left])
                left += 1

            while right <= high:
                tmp.append(arr[right])
                right += 1

            arr[low:high+1] = tmp

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

复杂度分析

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

[snmyj]

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        quicksort(nums,0,nums.size()-1);
        return nums;
    }
    void quicksort(vector<int>& nums,int l,int r){
        if(l>=r) return;
        int i=l-1,j=r+1;
        int partval=nums[(i+j)>>1];
        while(i<j){
            do i++;while(nums[i]<partval);
            do j--;while(nums[j]>partval);
            if(i<j) swap(nums[i],nums[j]);
        }

        quicksort(nums,l,j);
        quicksort(nums,j+1,r);
    }
};

[tzuikuo]

思路

写了一个好像很复杂的归并

代码

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n=nums.size();
        vector<int> re;
        re=merge(nums,0,n-1);

        return re;
    }
    vector<int> merge(vector<int>& nums,int left,int right){
        int mid,ii,jj;
        vector<int> temp;
        if(left==right){
            temp.push_back(nums[left]);
            return temp;
        }
        if(right==left+1){
            if(nums[left]>nums[right]){
                temp.push_back(nums[right]);
                temp.push_back(nums[left]);
            }
            else{
                temp.push_back(nums[left]);
                temp.push_back(nums[right]);
            }
        }
        else{
            mid=(left+right)/2+1;
            vector<int> vecleft,vecright;
            vecleft=merge(nums,left,mid-1);
            vecright=merge(nums,mid,right);
            ii=0;
            jj=0;
            while(ii<vecleft.size()||jj<vecright.size()){
                if(ii<vecleft.size()&&jj<vecright.size()){
                    if(vecleft[ii]<vecright[jj]){
                        temp.push_back(vecleft[ii]);
                        ii++;
                    }
                    else{
                        temp.push_back(vecright[jj]);
                        jj++;
                    }
                }
                else if(ii>=vecleft.size()){
                    temp.push_back(vecright[jj]);
                    jj++;
                }
                else{
                    temp.push_back(vecleft[ii]);
                    ii++;
                }
            }
        }
        return temp;
    }
};

复杂度分析

• 时间O(nlogn)
• 空间O(n)

[wangzh0114]

思路

• 归并排序

  代码

  class Solution{
  vector<int> tmp;
  void mergeSort(vector<int>& nums, int l, int r) {
      if (l >= r) return;
      int mid = (l + r) >> 1;
      mergeSort(nums, l, mid);
      mergeSort(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 i = 0; i < r - l + 1; ++i) {
          nums[i + l] = tmp[i];
      }
  }
  public:
  vector<int> sortArray(vector<int>& nums) {
     tmp.resize((int)nums.size(), 0);
      mergeSort(nums, 0, (int)nums.size() - 1);
      return nums;
  }
  };

  ---

  复杂度分析

• TC:O(nlogn)
• SC:O(n)

[harperz24]

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        # convert arr to a max heap
        for i in range(n // 2, -1, -1):
            self.heapify(nums, n, i)
        # extract the maximum element and place it at the end of arr
        for i in range(n - 1, 0, -1):
            nums[i], nums[0] = nums[0], nums[i]
            self.heapify(nums, i, 0)
        return nums

    def heapify(self, arr, n, i):
        # assume the current node i is the largest
        largest = i
        # find the left and right child nodes of the current nod
        left = 2 * i + 1
        right = 2 * i + 2

        # if the left child is larger than the current node,
        # update the largest index
        if left < n and arr[i] < arr[left]:
            largest = left
        # if the right child is larger than the current node or the left child,
        # update the largest index
        if right < n and arr[largest] < arr[right]:
            largest = right
        # if the largest index is not the current node,
        # recusively heapify the subtree rooted at the largest index
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            self.heapify(arr, n, largest)

    # heap sort
    # time: O(nlogn)
    # space: O(1)

[GuitarYs]

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        quicksort(nums,0,nums.size()-1);
        return nums;
    }
    void quicksort(vector<int>& nums,int l,int r){
        if(l>=r) return;
        int i=l-1,j=r+1;
        int partval=nums[(i+j)>>1];
        while(i<j){
            do i++;while(nums[i]<partval);
            do j--;while(nums[j]>partval);
            if(i<j) swap(nums[i],nums[j]);
        }

        quicksort(nums,l,j);
        quicksort(nums,j+1,r);
    }
};

[JasonQiu]

• Top-down merge sort

  class Solution:
  def sortArray(self, nums: List[int]) -> List[int]:
      if len(nums) <= 1:
          return nums
      result = []
      mid = len(nums) // 2
      left = self.sortArray(nums[:mid])
      right = self.sortArray(nums[mid:])
      while left and right:
          result.append(left.pop(0) if left[0] < right[0] else right.pop(0))
      return result + left if left else result + right

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

[Elsa-zhang]

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

        def merge(nums, l, mid, r):
            i, j, temp = l, mid+1, []
            while i<=mid and j<=r:
                if nums[i]<nums[j]:
                    temp.append(nums[i])
                    i+=1
                else:
                    temp.append(nums[j])
                    j+=1
            while i<=mid:
                temp.append(nums[i])
                i+=1
            while j<=r:
                temp.append(nums[j])
                j+=1
            for i in range(len(temp)):
                nums[l+i] = temp[i]

        def sort(nums, l, r):
            if l>=r:
                return 
            mid = (l+r)//2
            sort(nums, l, mid)
            sort(nums, mid+1, r)
            merge(nums, l, mid, r)

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

[JadeLiu13]

快排

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

    def quickSort(self, nums, low, high):
        if low >= high:
            return nums
        q = self.partition(nums, low, high)
        self.quickSort(nums, low, q-1)
        self.quickSort(nums, q+1, high)
        return nums

    def partition(self, nums, low, high):
        pivot = nums[high]
        i = low
        for j in range(low, high+1):
            if nums[j] < pivot:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1

        nums[i], nums[high] = nums[high], nums[i]

        return i

[Hughlin07]

class Solution {

public int[] sortArray(int[] nums) {

    HashMap<Integer, Integer> counts = new HashMap<>();
    int minVal = nums[0], maxVal = nums[0];

    for(int i = 0; i < nums.length; i++){
        minVal = Math.min(minVal, nums[i]);
        maxVal = Math.max(maxVal, nums[i]);
        counts.put(nums[i], counts.getOrDefault(nums[i], 0) + 1);
    }

    int index = 0;
    for(int i = minVal; i <= maxVal;i++){
        while(counts.getOrDefault(i, 0) > 0){
            nums[index] = i;
            index++;
            counts.put(i, counts.get(i)-1);
        }
    }

    return nums;
}

}

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

[yingchehu]

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

    def sort(self, nums, left, right):
        if right <= left:
            return

        i, j = left, right
        pivot = nums[left]
        while i != j:
            while nums[j] > pivot and i < j:
                j -= 1
            while nums[i] <= pivot and i < j:
                i += 1
            if i < j:
                nums[i], nums[j] = nums[j], nums[i]
        nums[left], nums[i] = nums[i], nums[left]

        self.sort(nums, left, i-1)
        self.sort(nums, i+1, right)

[jiujingxukong]

解题思路

这道题则简单粗暴，直接让你排序。 并且这道题目的难度是Medium，题目的限制条件是有两个，第一是元素个数不超过 10k，这个不算大。 另外一个是数组中的每一项范围都是-50k到50k（包含左右区间）。 看到这里，基本排除了时间复杂度为 O(n^2)的算法。剩下的就是基于比较的nlogn算法，以及基于特定条件的 O(n)算法。由于平时很少用到计数排序等 O(n)的排序算法，一方面是空间复杂度不是常量，另一方面是其要求数据范围不是很大才行，不然会浪费很多空间。

计数排序

1. 时间复杂度 O(n)空间复杂度 O(m) m 为数组中值的取值范围，在这道题就是50000 * 2 + 1。
2. 我们只需要准备一个数组取值范围的数字，然后遍历一遍，将每一个元素放到这个数组对应位置就好了， 放的规则是索引为数字的值，value为出现的次数。
3. 这样一次遍历，我们统计出了所有的数字出现的位置和次数。 我们再来一次遍历，将其输出到即可。

快速排序

1. 快速排序和归并排序都是分支思想来进行排序的算法， 并且二者都非常流行。 快速排序的核心点在于选择轴元素。
2. 每次我们将数组分成两部分，一部分是比 pivot（轴元素）大的，另一部分是不比 pivot 大的。 我们不断重复这个过程， 直到问题的规模缩小的寻常（即只有一个元素的情况）。

快排的核心点在于如何选择轴元素，一般而言，选择轴元素有四种策略：

• 数组最左边的元素
• 数组最右边的元素
• 数组中间的元素（我采用的是这种，大家可以尝试下别的）
• 数组随机一项元素

代码

计数排序

/**
 * @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;
};

快速排序

//快速排序是在原数组上交换两项数字大小
function swap(nums, a, b) {
  const temp = nums[a];
  nums[a] = nums[b];
  nums[b] = temp;
}

function helper(nums, start, end) {
 // while循环中，j可能会减到比start更小，再递归helper，就会start>end，如排序[0,1]
  if (start >= end) return;
  const pivotIndex = start + ((end - start) >>> 1);
  const pivot = nums[pivotIndex];
  let i = start;
  let j = end;
  while (i <= j) {
    while (nums[i] < pivot) i++;
    while (nums[j] > pivot) j--;
    if (i <= j) {
      swap(nums, i, j);
      i++;
      j--;
    }
  }
  helper(nums, start, j);
  helper(nums, i, end);
}

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  helper(nums, 0, nums.length - 1);
  return nums;
};

复杂度分析

n为数组长度

计数排序

TC：O（n） SC：O（m）m为数据范围长度

快速排序

TC：O（nlogn）由于算法一共有 logn 层， 每次的操作数都是 n，因此总的时间复杂度就是 nlogn。 SC: O(logn)算法一共有 logn 层

[AstrKing]

思路

直接上快速排序

代码

class Solution {

    private static final Random random = new Random();

    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 RandomIndex = left + random.nextInt(right - left + 1);
        swap(nums, left, RandomIndex);

        int pivot = nums[left];
        int less = left;
        int more = right + 1;
        // 循环不变量：这里是左闭右闭区间
        // 小于nums[pivot]区间：[left + 1, less]
        // 等于nums[pivot]区间：[less + 1, i]
        // 大于nums[pivot]区间：[more, right]
        int i = left + 1;
        while (i < more) {
            if (nums[i] < pivot) {
                less++;
                swap(nums, i, less);
                i++;
            } else if (nums[i] == pivot) {
                i++;
            } else {
                //这里不i++很重要！因为我们无法确定从尾部换来的元素是否小于nums[pivot]
                more--;
                swap(nums, i, more);
            }
        }
        //less最后指向的一定是小于nums[pivot]的元素
        swap(nums, left, less);
        //同理more指向大于nums[pivot]的元素
        quickSort(nums, left, less - 1);
        quickSort(nums, more, right);
    }

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

复杂度分析

时间复杂度：O(nlogn)

空间复杂度：O(logn)

[xiaoq777]

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

    public void sort(int[] arr, int l, int r) {
        if(l >= r) {
            return;
        }
        int a = arr[r];
        int i = l-1, j = r, k = l;
        while(k < j) {
            if(arr[k] < a) {
                swap(arr, i+1, k);
                i++;
                k++;
            }else if(arr[k] == a) {
                k++;
            }else if(arr[k] > a) {
                swap(arr, k, j-1);
                j--;
            }
        }
        swap(arr, j, r);
        sort(arr, l, i);
        sort(arr, j, r);
    }

    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

[kangliqi1]

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

public void sort(int[] arr, int l, int r) {
    if(l >= r) {
        return;
    }
    int a = arr[r];
    int i = l-1, j = r, k = l;
    while(k < j) {
        if(arr[k] < a) {
            swap(arr, i+1, k);
            i++;
            k++;
        }else if(arr[k] == a) {
            k++;
        }else if(arr[k] > a) {
            swap(arr, k, j-1);
            j--;
        }
    }
    swap(arr, j, r);
    sort(arr, l, i);
    sort(arr, j, r);
}

public void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

}

[zpbc007]

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

    public 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);
        }
    }

    public int randomizedPartition(int[] nums, int l, int r) {
        int i = new Random().nextInt(r - l + 1) + l; // 随机选一个作为我们的主元
        swap(nums, r, i);
        return partition(nums, l, r);
    }

    public int partition(int[] nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, r);
        return i + 1;
    }

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

[Lydia61]

912. 排序数组

思路

归并排序

代码

class Solution {
    vector<int> tmp;
    void mergeSort(vector<int>& nums, int l, int r) {
        if (l >= r) return;
        int mid = (l + r) >> 1;
        mergeSort(nums, l, mid);
        mergeSort(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 i = 0; i < r - l + 1; ++i) {
            nums[i + l] = tmp[i];
        }
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        tmp.resize((int)nums.size(), 0);
        mergeSort(nums, 0, (int)nums.size() - 1);
        return nums;
    }
};

复杂度分析

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

[RestlessBreeze]

code

class Solution {
public:

    void Merge(vector<int>&nums, vector<int>& temp, int lefts, int rights, int righte)
    {
        int lefte = rights - 1;
        int len = righte - lefts + 1;
        int flag = lefts;
        while (lefts <= lefte && rights <= righte)
        {
            if (nums[lefts] <= nums[rights])
                temp[flag++] = nums[lefts++];
            else
                temp[flag++] = nums[rights++];
        }
        while (lefts <= lefte)
        {
                temp[flag++] = nums[lefts++];
        }
        while (rights <= righte)
        {
                temp[flag++] = nums[rights++];
        }
        for (int i = 0; i < len; i++, righte--)
            nums[righte] = temp[righte];
    }

    void Merge_sort(vector<int>& nums, vector<int>& temp, int left, int right)
    {
        if (left < right)
        {
            int mid = left + (right - left) / 2;
            Merge_sort(nums, temp, left, mid);
            Merge_sort(nums, temp, mid + 1, right);
            Merge(nums, temp, left, mid + 1, right);
        }
    }

    vector<int> sortArray(vector<int>& nums) 
    {
        int size = nums.size();
        vector<int> temp(size);
        Merge_sort(nums, temp, 0, size - 1);
        return nums;
    }
};

[bingzxy]

思路

归并排序

代码

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

    private void mergeSort(int[] nums, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = l + (r - l) / 2;
        mergeSort(nums, l, mid);
        mergeSort(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];
            cnt++;
            i++;
        }
        while (j <= r) {
            tmp[cnt] = nums[j];
            cnt++;
            j++;
        }
        for (int k = 0; k < r - l + 1; k++) {
            nums[l + k] = tmp[k];
        }
    }
}

复杂度分析

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

[sye9286]

思路

计数排序

代码

var sortArray = function(nums) {
  countingSort(nums);
  return nums;
};
function countingSort(nums) {
  const n = nums.length;
  let min = nums[0];
  let max = nums[0];
  for (const num of nums) {
    if (num < min) {
      min = num;
    }
    if (num > max) {
      max = num;
    }
  }
  const range = max - min + 1;
  const counting = new Array(range).fill(0);
  for (const num of nums) {
    counting[num - min]++;
  }
  counting[0]--;
  for (let i = 1; i < range; i++) {
    counting[i] += counting[i - 1];
  }
  const ans = new Array(n);
  for (let i = n - 1; i >= 0; i--) {
    ans[counting[nums[i] - min]] = nums[i];
    counting[nums[i] - min]--;
  }
  for (let i = 0; i < n; i++) {
    nums[i] = ans[i];
  }
}

复杂度分析

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

[duke-github]

思路

堆排序

复杂度

时间复杂度O(n logn) 空间复杂度O（n）

代码

class Solution {
    public int[] sortArray(int[] nums) {
        heapSort(nums);
        return nums;
    }

    public void heapSort(int[] nums) {
        int len = nums.length - 1;
        buildMaxHeap(nums, len);
        for (int i = len; i >= 1; --i) {
            swap(nums, i, 0);
            len -= 1;
            maxHeapify(nums, 0, len);
        }
    }

    public void buildMaxHeap(int[] nums, int len) {
        for (int i = len / 2; i >= 0; --i) {
            maxHeapify(nums, i, len);
        }
    }

    public void maxHeapify(int[] nums, int i, int len) {
        for (; (i << 1) + 1 <= len;) {
            int lson = (i << 1) + 1;
            int rson = (i << 1) + 2;
            int large;
            if (lson <= len && nums[lson] > nums[i]) {
                large = lson;
            } else {
                large = i;
            }
            if (rson <= len && nums[rson] > nums[large]) {
                large = rson;
            }
            if (large != i) {
                swap(nums, i, large);
                i = large;
            } else {
                break;
            }
        }
    }

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

[Fuku-L]

思路

堆排序

代码

class Solution {
    public int[] sortArray(int[] nums) {
        heapSort(nums);
        return nums;
    }

    public void heapSort(int[] nums) {
        int len = nums.length - 1;
        buildMaxHeap(nums, len);
        for (int i = len; i >= 1; --i) {
            swap(nums, i, 0);
            len -= 1;
            maxHeapify(nums, 0, len);
        }
    }

    public void buildMaxHeap(int[] nums, int len) {
        for (int i = len / 2; i >= 0; --i) {
            maxHeapify(nums, i, len);
        }
    }

    public void maxHeapify(int[] nums, int i, int len) {
        for (; (i << 1) + 1 <= len;) {
            int lson = (i << 1) + 1;
            int rson = (i << 1) + 2;
            int large;
            if (lson <= len && nums[lson] > nums[i]) {
                large = lson;
            } else {
                large = i;
            }
            if (rson <= len && nums[rson] > nums[large]) {
                large = rson;
            }
            if (large != i) {
                swap(nums, i, large);
                i = large;
            } else {
                break;
            }
        }
    }

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

复杂度分析

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

[Jetery]

class Solution {
public:

    void merge(vector<int> &nums, vector<int> &temp, int l, int r) {
        if (l >= r) return;
        int mid = (l + r) >> 1;
        merge(nums, temp, l, mid); merge(nums, temp, mid + 1, r);
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) temp[k++] = nums[i++];
            else temp[k++] = nums[j++];
        }
        while (i <= mid) temp[k++] = nums[i++];
        while (j <= r) temp[k++] = nums[j++];
        for (i = l, k = 0; i <= r; i++, k++) nums[i] = temp[k];
    }

    vector<int> sortArray(vector<int>& nums) {
        vector<int> temp(nums.size());
        merge(nums, temp, 0, nums.size() - 1);
        return nums;
    }
};

[joemonkeylee]

思路

快速排序

代码

        public int[] SortArray(int[] nums)
        {
            randomizedQuicksort(nums, 0, nums.Length - 1);
            return nums;
        }

        public 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);
            }
        }

        public int randomizedPartition(int[] nums, int l, int r)
        {
            int i = new Random().Next(r - l + 1) + l; 
            swap(nums, r, i);
            return partition(nums, l, r);
        }

        public int partition(int[] nums, int l, int r)
        {
            int pivot = nums[r];
            int i = l - 1;
            for (int j = l; j <= r - 1; ++j)
            {
                if (nums[j] <= pivot)
                {
                    i = i + 1;
                    swap(nums, i, j);
                }
            }
            swap(nums, i + 1, r);
            return i + 1;
        }

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

复杂度分析

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

[DrinkMorekaik]

const sortArray = function(nums, start = 0, end = nums.length - 1) {
  const len = nums.length
  if (len <= 1) return nums
  const index = device(nums, start, end)
  if (start < index - 1) sortArray(nums, start, index - 1)
  if (end > index) sortArray(nums, index, end)
  return nums
};

const device = (nums, start, end) => {
  let left = start,
      right = end;
  const provide = nums[parseInt((left + right) / 2)]
  while(left <= right) {
    while(nums[left] < provide) left++
    while(nums[right] > provide) right--
    if (left <= right) {
      [nums[left], nums[right]] = [nums[right], nums[left]]
      left++
      right--
    }
  }
  return left
}

[aoxiangw]

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def merge(arr, L, M, R):
            left, right = arr[L:M+1], arr[M+1:R+1]
            i, j, k = L, 0, 0

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

        def mergeSort(arr, l, r):
            if l == r:
                return arr
            m = (l + r) // 2
            mergeSort(arr, l, m)
            mergeSort(arr, m + 1, r)
            merge(arr, l, m, r)
            return arr
        return mergeSort(nums, 0, len(nums) - 1)

O(nlogn), O(n)

[chocolate-emperor]

class Solution {
public:
    void fastSort(vector<int>&nums,int l, int r){
        if(l>=r)    return;
        int bar = nums[(l+r)>>1];

        int left = l-1 ,right = r+1;
        while(left<right){
            do(left++); while(nums[left]<bar);
            do(right--); while(nums[right]>bar);

            if(left<right)  swap(nums[left],nums[right]);
        }
        fastSort(nums,l,left);
        fastSort(nums,left+1,r);
    }
    vector<int> sortArray(vector<int>& nums) {
        int l = 0 , r = nums.size()-1;
        fastSort(nums,l,r);
        return nums;
    }
};

[SoSo1105]

class Solution: def max_heapify(self, heap, root, heap_len): p = root while p 2 + 1 < heap_len: l, r = p 2 + 1, p * 2 + 2 if heap_len <= r or heap[r] < heap[l]: nex = l else: nex = r if heap[p] < heap[nex]: heap[p], heap[nex] = heap[nex], heap[p] p = nex else: break

def build_heap(self, heap):
    for i in range(len(heap) - 1, -1, -1):
        self.max_heapify(heap, i, len(heap))

def heap_sort(self, nums):
    self.build_heap(nums)
    for i in range(len(nums) - 1, -1, -1):
        nums[i], nums[0] = nums[0], nums[i]
        self.max_heapify(nums, 0, i)

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

[csthaha]

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

[chanceyliu]

思路

插入排序

代码

function sortArray(nums: number[]): number[] {
  const n = nums.length;
  for (let i = 1; i < n; ++i) {
    let j = i - 1;
    const tmp = nums[i];
    while (j >= 0 && tmp < nums[j]) {
      nums[j + 1] = nums[j];
      --j;
    }
    nums[j + 1] = tmp;
  }
  return nums;
}

复杂度分析

• 时间复杂度：平均 O(n²)、最好 O(n)、最坏 O(n²)
• 空间复杂度：O(1)