精选力扣500题第6题 LeetCode 912. 排序数组【c++详细题解】

秒速五厘米 2021-09-07 19:54 414阅读 0赞

### 1、题目 ###

给你一个整数数组 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

### 2、思路 ###

[图解快速排序][Link 1]

### 3、代码 ###

class Solution { 
    public:
        vector<int> sortArray(vector<int>& nums) { 
            quick_sort(nums,0,nums.size()-1);
            return nums;
        }
        void quick_sort(vector<int>& nums,int l,int r)
        { 
            if(l >= r) return ;
            int i = l - 1,j = r + 1,x = nums[(l+r)/2];
            while(i < j)
            { 
                do i++; while(nums[i] < x);
                do j--; while(nums[j] > x);
                if(i < j) swap(nums[i],nums[j]);
            }
            quick_sort(nums,l,j);
            quick_sort(nums,j+1,r);
        }
    };

**原题链接：**[912. 排序数组][912.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

[Link 1]: https://blog.csdn.net/weixin_45629285/article/details/110742830?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162134343816780255245685%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=162134343816780255245685&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_v2~rank_v29-3-110742830.nonecase&utm_term=%E5%BF%AB%E9%80%9F&spm=1018.2226.3001.4450
[912.]: https://leetcode-cn.com/problems/sort-an-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/460d8a6802144969a222d686a5d955d6.png