912 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]

Solution 1: QuickSort¶

Time complexity: O(nlogn) ~ O(n^2) Space complexity: O(logn) ~ O(n)

QuickSort - js

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

Solution 2: HeapSort¶

HeapSort - js

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

class Solution {
public:
  vector<int> sortArray(vector<int>& nums) {
    priority_queue<int> q(begin(nums), end(nums));
    int i = nums.size();
    while (!q.empty()) {
      nums[--i] = q.top();
      q.pop();
    }
    return nums;
  }
};

Solution 3: MergeSort¶

MergeSort - js

Time complexity: O(nlogn) Space complexity: O(logn + n)

class Solution {
public:
  vector<int> sortArray(vector<int>& nums) {
    vector<int> t(nums.size());
    function<void(int, int)> mergeSort = [&](int l, int r) {
      if (l + 1 >= r) return;
      int m = l + (r - l) / 2;
      mergeSort(l, m);
      mergeSort(m, r);
      int i1 = l;
      int i2 = m;
      int index = 0;
      while (i1 < m || i2 < r)
        if (i2 == r || (i1 < m && nums[i1] < nums[i2]))
          t[index++] = nums[i1++];
        else
          t[index++] = nums[i2++];
      std::copy(begin(t), begin(t) + index, begin(nums) + l);
    };

    mergeSort(0, nums.size());
    return nums;
  }
};