# 912. Sort an Array

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

Example 1:

``````Input: [5,2,3,1]
Output: [1,2,3,5]
``````

Example 2:

``````Input: [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
``````

Note:

1. `1 <= A.length <= 10000`
2. `-50000 <= A[i] <= 50000`

``````class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
int n = nums.size(), j = 0;
vector<int> res(n), count(100001);
for (int num : nums) ++count[num + 50000];
for (int i = 0; i < count.size(); ++i) {
while (count[i]-- > 0) {
res[j++] = i - 50000;
}
}
return res;
}
};
``````

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

``````class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
mergeSort(nums, 0, (int)nums.size() - 1);
return nums;
}
void mergeSort(vector<int>& nums, int start, int end) {
if (start >= end) return;
int mid = (start + end) / 2;
mergeSort(nums, start, mid);
mergeSort(nums, mid + 1, end);
merge(nums, start, mid, end);
}
void merge(vector<int>& nums, int start, int mid, int end) {
vector<int> tmp(end - start + 1);
int i = start, j = mid + 1, k = 0;
while (i <= mid && j <= end) {
if (nums[i] < nums[j]) tmp[k++] = nums[i++];
else tmp[k++] = nums[j++];
}
while (i <= mid) tmp[k++] = nums[i++];
while (j <= end) tmp[k++] = nums[j++];
for (int idx = 0; idx < tmp.size(); ++idx) {
nums[idx + start] = tmp[idx];
}
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/912

Kth Largest Element in an Array

Sort Colors

Count of Range Sum

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

https://leetcode.com/problems/sort-an-array/discuss/319326/Java-merge-sort-implementation

https://leetcode.com/problems/sort-an-array/discuss/293820/Easiest-and-fastest-solution.-O(10n)

https://leetcode.com/problems/sort-an-array/discuss/280903/C%2B%2B-QuickSort-and-CountingSort-solutions

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation