# 912. Sort an Array 排序数组

@TOC

## # 题目描述

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) {
sort(nums.begin(), nums.end());
return nums;
}
};
``````

### # 桶排序

C++代码如下：

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

### # 红黑树排序

C++的map使用了红黑树结构，也可以达到统计各个元素出现的次数，而且遍历是按照Key有序的。

``````class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
map<int, int> m;
for (int num : nums) {
m[num]++;
}
vector<int> res;
auto it = m.begin();
while(it != m.end()) {
res.insert(res.end(), it->second, it->first);
it ++;
}
return res;
}
};
``````

### # 归并排序

merge sort是把数组的左右两半部分都排序，然后做一个merge two sorted array的操作。

``````class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
return mergeSort(nums, 0, nums.size());
}
// sort nums[start, end)
vector<int> mergeSort(vector<int>& nums, int start, int end) {
if (start + 1 == end) return vector<int>(1, nums[start]);
int L = end - start;
vector<int> A = mergeSort(nums, start, start + L / 2);
vector<int> B = mergeSort(nums, start + L / 2, end);
return merge(A, B);
}
// merge two sorted array
vector<int> merge(vector<int>& A, vector<int>& B) {
int M = A.size(), N = B.size();
if (M == 0) return B;
if (N == 0) return A;
vector<int> res;
auto ita = A.begin();
auto itb = B.begin();
while (ita != A.end() && itb != B.end()) {
if (*ita < *itb) {
res.push_back(*ita);
++ita;
} else {
res.push_back(*itb);
++itb;
}
}
if (ita != A.end())
res.insert(res.end(), ita, A.end());
if (itb != B.end())
res.insert(res.end(), itb, B.end());
return res;
}
};
``````

### # 快速排序

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

## # 日期

2019 年 9 月 16 日 —— 秋高气爽