912 排序数组

本文最后更新于：2021年3月25日 晚上

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

示例 1：

1
2
输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

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

提示：

  1. 1 <= nums.length <= 50000
  2. -50000 <= nums[i] <= 50000

Solution

  • 快速排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// @lc code=start
class Solution {
public:
    void quickSort(vector<int>& nums, int l, int r) {
        if (l >= r)
            return;
        
        swap(nums[l], nums[rand()%(r-l+1)+l]);
        int pivot = nums[l];
        int p = l;
        for (int i = l+1; i <= r; ++i) {
            if (nums[i] < pivot) {
                ++p;
                swap(nums[i], nums[p]);
            }
        }
        swap(nums[l], nums[p]);

        quickSort(nums, l, p-1);
        quickSort(nums, p+1, r);
    }

    vector<int> sortArray(vector<int>& nums) {
        quickSort(nums, 0, nums.size()-1);
        return nums;
    }
};
// @lc code=end
algo leetcode 算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！