912. 排序数组#

1
给你一个整数数组 nums，请你将该数组升序排列。
2

3

4

5
示例 1：
6

7
输入：nums = [5,2,3,1]
8
输出：[1,2,3,5]
9
示例 2：
10

11
输入：nums = [5,1,1,2,0,0]
12
输出：[0,0,1,1,2,5]
13

14

15
提示：
16

17
1 <= nums.length <= 50000
18
-50000 <= nums[i] <= 50000

1
class Solution {
2
public:
3
    vector<int> sortArray(vector<int>& nums) {
4
        //sort(nums.begin(), nums.end());
5
        //return nums;
6
        int n = nums.size();
7

8
        //冒泡排序 超时
9
        /* for(int i = 0; i < n; i++)
10
        {
11
            bool flag = false;
12
            for(int j = n - 2; j >= i; j--)
13
            {
14
                if(nums[j] > nums[j + 1])
15
                {
16
                    swap(nums[j], nums[j + 1]);
17
                    flag = true;
18
                }
19
            }
20
            if(flag == false)break;
21
        } */
22

23
        //插入排序 超时
24
        /* for(int i = 0; i < n - 1; i++)
25
        {
26
            int min = i;
27
            for(int j = i + 1; j < n; j++)
28
            {
29
                if(nums[min] > nums[j]) min = j;
30
            }
31
            if(min != i) swap(nums[i], nums[min]);
32
        } */
33

34
        //快排 失败
35
        /* dfs(0, n - 1, nums); */
36

37
        //堆排序
38
        /* for(int i = 0; i < n; i++)
39
        {
40
            int pos = i;
41
            int mid = (pos - 1)/2;
42
            while(nums[pos] > nums[mid])
43
            {
44
                swap(nums[pos], nums[mid]);
45
                pos = mid;
46
                mid = (pos - 1) / 2;
47
            }
48
        }
49
        for(int j = n - 1; j >= 0; j--)
50
        {
51
            swap(nums[0], nums[j]);
52
            heapsort(nums,0,j);
53
        } */
54

55
        //计数排序
56
        int minn = *min_element(nums.begin(), nums.end());
57
        int maxn = *max_element(nums.begin(), nums.end());
58
        vector<int> ans(maxn - minn + 1);
59
        for(auto i : nums)
60
        {
61
            ans[i - minn]++;
62
        }
63
        int j = 0, i = 0;
64
        while(i < ans.size())
65
        {
66
            while(ans[i] > 0)
67
            {
68
                nums[j++] = i + minn;
69
                ans[i]--;
70
            }
71
            i++;
72
        }
73
        return nums;
74
    }
75

76
    /* void dfs(int start, int end, vector<int>& nums) {
77
        if(start > end) return;
78
        int i = start, j = end;
79
        while(i < j)
80
        {
81
            while(nums[j] >= nums[start] && i < j) j--;
82
            while(nums[i] <= nums[start] && i < j) i++;
83
            if(i < j) swap(nums[i], nums[j]);
84
        }
85
        swap(nums[start], nums[i]);
86
        dfs(start, i - 1, nums);
87
        dfs(i + 1, end, nums);
88
    } */
89

90
   /*  void heapsort(vector<int>& nums, int pos, int n)
91
    {
92
        int l = pos * 2 + 1, r = pos * 2 + 2;
93
        while(l < n)
94
        {
95
            int big = pos;
96
            if(l < n && nums[l] > nums[big]) big = l;
97
            if(r < n && nums[r] > nums[big]) big = r;
98
            if(big == pos) break;
99
            swap(nums[pos], nums[big]);
100
            pos = big;
101
            l = pos * 2 + 1, r = pos * 2 + 2;
102
        }
103
    } */
104
};