# 排序数组
给你一个整数数组 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
以下错误的选项是？
## aop
### before
```cpp
#include
using namespace std;
```
### after
```cpp
int main()
{
Solution sol;
vector res;
vector nums = {5, 1, 1, 2, 0, 0};
res = sol.sortArray(nums);
for (auto i : res)
cout << i << " ";
return 0;
}
```
## 答案
```cpp
class Solution
{
public:
void make_max_heap(vector &nums, int len)
{
for (int i = (len / 2); i >= 0; --i)
max_heap_fixed(nums, i, len);
}
void max_heap_fixed(vector &nums, int cur_idx, int len)
{
int lchild = (cur_idx << 1) + 1, rchild = (cur_idx << 1) + 2;
while (lchild < len)
{
int large = cur_idx;
if (lchild <= len && nums[lchild] > nums[cur_idx])
{
large = lchild;
}
if (rchild <= len && nums[rchild] > nums[large])
{
large = rchild;
}
if (large != cur_idx)
{
swap(nums[cur_idx], nums[large]);
cur_idx = large;
lchild = cur_idx << 1;
rchild = cur_idx << 2;
}
else
break;
}
}
vector sortArray(vector &nums)
{
int length = nums.size() - 1;
make_max_heap(nums, length);
for (int i = length; i > 0; --i)
{
swap(nums[0], nums[i]);
max_heap_fixed(nums, 0, i - 1);
}
return nums;
}
};
```
## 选项
### A
```cpp
class Solution
{
public:
vector sortArray(vector &nums)
{
if (nums.size() == 1)
return nums;
for (int i = 1; i < nums.size(); ++i)
{
int preIdx = i - 1;
int curVal = nums[i];
while (preIdx >= 0 && curVal > nums[preIdx])
{
nums[preIdx + 1] = nums[preIdx];
preIdx--;
}
nums[preIdx + 1] = curVal;
}
reverse(nums.begin(), nums.end());
return nums;
}
};
```
### B
```cpp
class Solution
{
public:
void swap(int &a, int &b)
{
int tmp = a;
a = b;
b = tmp;
}
vector sortArray(vector &nums)
{
if (nums.size() == 1)
return nums;
for (int i = 0; i < nums.size() - 1; ++i)
{
int minIndex = i;
for (int j = i + 1; j < nums.size(); ++j)
{
if (nums[i] > nums[j])
{
minIndex = j;
}
}
if (minIndex != i)
{
swap(nums[minIndex], nums[i]);
}
}
return nums;
}
};
```
### C
```cpp
class Solution
{
public:
vector sortArray(vector &nums)
{
if (nums.size() == 1)
return nums;
int tmp;
bool sorted = true;
for (int i = 0; i < nums.size() - 1; ++i)
{
for (int j = nums.size() - 1; j > i; --j)
{
if (nums[j - 1] > nums[j])
{
tmp = nums[j - 1];
nums[j - 1] = nums[j];
nums[j] = tmp;
sorted = false;
}
}
if (sorted)
return nums;
}
return nums;
}
};
```
### D
```cpp
class Solution
{
public:
vector sortArray(vector &nums)
{
int length = nums.size();
if (length == 1)
return nums;
int inc = length;
while (true)
{
inc /= 2;
for (int k = 0; k < inc; ++k)
for (int i = k + inc; i < length; i += inc)
{
int preIdx = i - inc;
int curVal = nums[i];
while (preIdx >= 0 && curVal < nums[preIdx])
{
nums[preIdx + inc] = nums[preIdx];
preIdx -= inc;
}
nums[preIdx + inc] = curVal;
}
if (inc == 1)
break;
}
return nums;
}
};
```
### E
```cpp
class Solution
{
vector nums;
public:
void merge(int left, int right)
{
if (left >= right)
{
return;
}
int mid = (left + right) / 2;
merge(left, mid);
merge(mid + 1, right);
int i = left, j = mid + 1;
vector tmp;
while (i <= mid && j <= right)
{
if (nums[i] < nums[j])
{
tmp.push_back(nums[i]);
i++;
}
else
{
tmp.push_back(nums[j]);
j++;
}
}
while (i <= mid)
{
tmp.push_back(nums[i]);
i++;
}
while (j <= right)
{
tmp.push_back(nums[j]);
j++;
}
for (i = 0; i < right - left + 1; ++i)
nums[i + left] = tmp[i];
}
vector sortArray(vector &nums)
{
this->nums = nums;
int length = nums.size();
if (length == 1)
return nums;
merge(0, nums.size() - 1);
return this->nums;
}
};
```
### F
```cpp
class Solution
{
public:
int partion(vector &nums, int left, int right)
{
int pivot = nums[right];
int i = left, j;
for (j = left; j < right; ++j)
{
if (nums[j] <= pivot)
{
swap(nums[i], nums[j]);
i++;
}
}
swap(nums[i], nums[right]);
return i;
}
int random_partion(vector &nums, int left, int right)
{
int randIdx = rand() % (right - left + 1) + left;
swap(nums[randIdx], nums[right]);
return partion(nums, left, right);
}
void random_quick_sort(vector &nums, int left, int right)
{
if (left < right)
{
int pivot = random_partion(nums, left, right);
random_quick_sort(nums, left, pivot - 1);
random_quick_sort(nums, pivot + 1, right);
}
}
vector sortArray(vector &nums)
{
int length = nums.size();
if (length == 1)
return nums;
srand(time(NULL));
random_quick_sort(nums, 0, length - 1);
return nums;
}
};
```