solution.md

# 排序数组

<p>给你一个整数数组&nbsp;<code>nums</code>，请你将该数组升序排列。</p>

<p>&nbsp;</p>

<ol>
</ol>

<p><strong>示例 1：</strong></p>

<pre><strong>输入：</strong>nums = [5,2,3,1]

<strong>输出：</strong>[1,2,3,5]
</pre>

<p><strong>示例 2：</strong></p>

<pre><strong>输入：</strong>nums = [5,1,1,2,0,0]

<strong>输出：</strong>[0,0,1,1,2,5]
</pre>

<p>&nbsp;</p>

<p><strong>提示：</strong></p>

<ol>
	<li><code>1 &lt;= nums.length &lt;= 50000</code></li>
	<li><code>-50000 &lt;= nums[i] &lt;= 50000</code></li>
</ol>
<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```c
#include <bits/stdc++.h>
using namespace std;
```

### after

```c
int main()
{
    Solution sol;
    vector<int> res;
    vector<int> nums = {5, 1, 1, 2, 0, 0};
    res = sol.sortArray(nums);
    for (auto i : res)
        cout << i << " ";
    return 0;
}
```

## 答案

```c
class Solution
{
public:
    void make_max_heap(vector<int> &nums, int len)
    {
        for (int i = (len / 2); i >= 0; --i)
            max_heap_fixed(nums, i, len);
    }
    void max_heap_fixed(vector<int> &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<int> sortArray(vector<int> &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

```c
class Solution
{
public:
    vector<int> sortArray(vector<int> &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

```c
class Solution
{
public:
    void swap(int &a, int &b)
    {
        int tmp = a;
        a = b;
        b = tmp;
    }
    vector<int> sortArray(vector<int> &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

```c
class Solution
{
public:
    vector<int> sortArray(vector<int> &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

```c
class Solution
{
public:
    vector<int> sortArray(vector<int> &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

```c
class Solution
{
    vector<int> 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<int> 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<int> sortArray(vector<int> &nums)
    {
        this->nums = nums;
        int length = nums.size();
        if (length == 1)
            return nums;
        merge(0, nums.size() - 1);
        return this->nums;
    }
};
```


### F

```c
class Solution
{
public:
    int partion(vector<int> &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<int> &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<int> &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<int> sortArray(vector<int> &nums)
    {
        int length = nums.size();
        if (length == 1)
            return nums;
        srand(time(NULL));
        random_quick_sort(nums, 0, length - 1);
        return nums;
    }
};
```